字符串

剑指offer所有的题目总结

牛客

1. 正则表达式的匹配

leetcode的题目，解析描述更加全面

https://leetcode-cn.com/problems/regular-expression-matching/

请实现一个函数用来匹配包括'.'和''的正则表达式。模式中的字符'.'表示任意一个字符，而''表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"ab*a"均不匹配。

/*
当模式中的第二个字符不是“*”时：
  1、如果字符串第一个字符和模式中的第一个字符相匹配，
  那么字符串和模式都后移一个字符，然后匹配剩余的。 
  2、如果字符串第一个字符和模式中的第一个字符相不匹配，直接返回false。
  而当模式中的第二个字符是“*”时：
  如果字符串第一个字符跟模式第一个字符不匹配，则模式后移2个字符，继续匹配。
  如果字符串第一个字符跟模式第一个字符匹配，可以有3种匹配方式： 
  1、模式后移2字符，相当于x*被忽略； 
  2、字符串后移1字符，模式后移2字符； 相当于x*算一次
  3、字符串后移1字符，模式不变，即继续匹配字符下一位，因为*可以匹配多位，相当于算多次
  这里需要注意的是：Java里，要时刻检验数组是否越界。*/
public class Zhengze {
    public boolean match(char[] str, char[] pattern) {
        if (str == null || pattern == null) {
            return false;
        }
        int strIndex = 0;
        int patternIndex = 0;
        return matchCore(str, strIndex, pattern, patternIndex);
    }
 
    public boolean matchCore(char[] str, int strIndex, char[] pattern, int patternIndex) {
        // 有效性检验：str到尾，pattern到尾，匹配成功
        if (strIndex == str.length && patternIndex == pattern.length)
            return true;
        // pattern先到尾，匹配失败
        if (strIndex != str.length && patternIndex == pattern.length)
            return false;
        // 模式第2个是*，且字符串第1个跟模式第1个匹配,分3种匹配模式；如不匹配，模式后移2位
        if (patternIndex + 1 < pattern.length && pattern[patternIndex + 1] == '*') {
            if ((strIndex != str.length && pattern[patternIndex] == str[strIndex])
                    || (pattern[patternIndex] == '.' && strIndex != str.length)) {
                return // 模式后移2，视为x*匹配0个字符
                matchCore(str, strIndex, pattern, patternIndex + 2)
                        // 视为模式匹配1个字符
                        || matchCore(str, strIndex + 1, pattern, patternIndex + 2)
                        // *匹配1个，再匹配str中的下一个
                        || matchCore(str, strIndex + 1, pattern, patternIndex);
 
            } else {
                return matchCore(str, strIndex, pattern, patternIndex + 2);
            }
        } // 模式第2个不是*，且字符串第1个跟模式第1个匹配，则都后移1位，否则直接返回false
        if ((strIndex != str.length && pattern[patternIndex] == str[strIndex])
                || (pattern[patternIndex] == '.' && strIndex != str.length)) {
            return matchCore(str, strIndex + 1, pattern, patternIndex + 1);
        }
        return false;
    }
}

2. 表示数值的字符串

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。

正则表达式解法：

[+-]? 表示+或者-出现0次或1次。[0-9]{0,}表示0到9出现0次或者更多次。()表示这个分组作为一个整体。 \.?表示.出现0次或1次。[0-9]{1,}表示0到9出现1次或者多次。()表示一个分组。如果把两个分组去掉进行判断是不准确的。100匹配到[0-9]{1,}出错。

 public boolean isNumeric(char[] str) {
        String res = String.valueOf(str);
        return res.matches("[+-]?[0-9]{0,}(\\.?[0-9]{1,})?([Ee][+-]?[0-9]{1,})?");
    }

逻辑思路：

思路:按照一定的规则，如果第一位是+或-，就后移一位。

如果是数字，索引后移，数字表示1.

如果是点，要判断至此点的数量和e的数量是否已经有了，因为java 中e要求后面为整数，如果有了肯定false。索引后移，dotnum增加。

如果是e，判断是否重复e，或者前面没有数字返回false。enum++， 索引++，此时还要判断最后一位是不是e或者+或者-，如果是false。

public boolean isNumeric(char[] str) {
        if(str == null)
            return false;
        int length = str.length;
        int dotNum = 0;//记录点的数量
        int index = 0;//索引
        int eNum = 0;//记录e的数量
        int num = 0;//记录数字的数量
        if (str[0] == '+' || str[0] == '-') {
            index++;
        }
        while (index < length) {
            if(str[index]>='0' && str[index]<='9') {
                index++;
                num = 1;
             // .前面可以没有数字,所以不需要判断num是否为0
            }else if(str[index]=='.') {
                // e后面不能有.,e的个数不能大于1.java科学计数要求aeb，b为整数
                if(dotNum >0 || eNum >0)
                    return false;
                dotNum++;
                index++;
            }else if(str[index] == 'e' || str[index] == 'E') {
                // 重复e或者e前面没有数字
                if(eNum > 0 || num ==0)
                    return false;
                eNum++;
                index++;
                // 符号不能在最后一位
                if(index < length &&(str[index]=='+'||str[index]=='-'))
                    index++;
                // 表示e或者符号在最后一位
                if(index == length)
                    return false;
            }else {
                return false;
            }
            
        }
        return true;
    }

3. 第一个只出现一次的字符

在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.

private LinkedHashMap<Character,Integer> hm = null;
    
    public int FirstNotRepeatingChar(String str) {
        hm = new LinkedHashMap<>();
        
        for(int i=0;i<str.length();i++) {
            if(!hm.containsKey(str.charAt(i))) {
                hm.put(str.charAt(i), 1);
            }else {
                hm.put(str.charAt(i),hm.get(str.charAt(i))+1);
            }
        }
        
        for (int i = 0; i < str.length(); i++) {
            if (hm.get(str.charAt(i)) == 1) {
                return i;
            }
        }
        
        return -1;
    }

3.1 字符流中第一个不重复的字符

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。

思路：参考两个博客一种用hashmap来做，一种用字符数组来做。

HashMap<Character, Integer> map = new HashMap<>();//记录字符出现次数
    ArrayList<Character> list = new ArrayList<>();//记录当前的所有的字符
    //Insert one char from stringstream
    public void Insert(char ch)
    {
        if(map.containsKey(ch))
            map.put(ch, map.get(ch)+1);
        else
            map.put(ch,1);
        list.add(ch);
    }
  //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        for(char c:list) {
            if(map.get(c)==1)
                return c;
        }
        return '#';
    }

字符数组的方法：

char类型和int类型数值在 0-255之内的可以通用

默认初始值是ASCII的0（int）;char类型会自动转换成(int型)ASCII进行算术运算

char [] chars = new char[256];//ascii字符共128，其他字符非中文认为256个，
                                //为每个字符预留空间。默认每个存的ascii值为0 
   StringBuffer sb = new StringBuffer();//记录当前的所有字符
    //Insert one char from stringstream
    public void Insert(char ch)
    {
        sb.append(ch);
        chars[ch]++;//如果字符是1，那么就是在字符1对应的下标的地方
                    //也就是49的下标处，ascii加1.此时如果输出chars[ch],里面存ascii值
                    //为1，所以是一个不可显示的字符。
    }
  //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
         char [] str = sb.toString().toCharArray();
         for(char c:str) {
             if(chars[c] == 1)//判断这个字符数组中在这个字符下标处值是否为1.
                 return c;
         }
         return '#';
    }

5. 左旋转字符串

汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！

public String LeftRotateString(String str,int n) {
        if(str.length() == 0) {
            return "";
        }
        if(str.length() == 1) {
            return str;
        }
        
        String s = str.substring(0,n);
        String t = str.substring(n);
        
        return t.concat(s);
    }

不知道要考什么，过于简单

6. 把字符串转换为整数

将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0

思路：若为负数，则输出负数，字符0对应48,9对应57，不在范围内则返回false。

public int StrToInt(String str) {
        if (str == null || str.length() == 0)
            return 0;
        int mark = 0;
        long number = 0;
        char[] chars = str.toCharArray();
        if (chars[0] == '-')
            mark = 1;//第一位如果是-号，则从第二位开始循环
        for (int i = mark; i < chars.length; i++) {
             if(chars[i] == '+')
                 continue;
             if(chars[i]<48 || chars[i]>57)
                 return 0;
             number = number * 10+chars[i] - 48;
        }
        if(mark==0 && number > Integer.MAX_VALUE) {
            return 0;
        }
        
        if(-number < -2147483648) {
            return 0;
        }
        
        return (int)(mark==0?number:-number);//最后根据mark标记的正负号来决定数字正负
    }

注意边界判断

7. 字符串的排列

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

public ArrayList<String> Permutation(String str) {
        List <String> res = new ArrayList<String>();
        if(str != null && str.length() >0){
            PermutationHelp(str.toCharArray(),0,res);
            Collections.sort(res); //按字典序 输出字符串数组。
        }
            
        return (ArrayList)res;
    }
    public void PermutationHelp(char[] chars, int index, List<String> list) {
        if(index == chars.length -1){ //当递归交换到最后一个位置的时候，就看看list有么有这个字符串，没有的话就放进去。
            String val = String.valueOf(chars);
            if (!list.contains(val)) {//如果最后list没有这个string，因为可能交换后有重复的
                list.add(val);
            }
        }
        else {
            for (int i = index; i < chars.length; i++) { //循环来执行交换操作，先交换，然后固定这个，下一个交换。最后要交换回来不要影响执行
                swap(chars, index, i);
                PermutationHelp(chars, index+1, list);//依次固定一个
                swap(chars, index, i);
            }
        }
    }
    public void swap(char[] chars,int i, int j) {//交换数组中的两个位置中的值
        char temp =chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
            
    }