█ 8.字符串

字符串直接匹配问题：kml P380

○ 19. 正则表达式匹配：判断aa.a"和"ab*a 《* . 》

class Solution {
    public boolean isMatch(String s, String p) {

        if(p.isEmpty()){
            return s.isEmpty();
        }
        boolean headMatch = !s.isEmpty() && (s.charAt(0) == p.charAt(0) || p.charAt(0) == ‘.‘);
        
        //关于* 有两种可能
        // 1. 要把p的*和前面的都去掉     s=aca      p=b*ac*a  p = ac*a
        // 2. 要把s (s前面有重复) 去掉   s=bbaca   p=b*ac*a  s = baca

        if(p.length() >= 2 && p.charAt(1)== ‘*‘){
            return isMatch(s, p.substring(2)) || (headMatch && isMatch(s.substring(1), p));
        } else if(headMatch){
            return isMatch(s.substring(1), p.substring(1));
        } else{
            return false;
        }

    }
}

○ 5. 替换空格 《charAt》

/*
class Solution {
    public String replaceSpace(String s) {
        int n = s.length();
        char[] array = new char[n*3];
        int size = 0;
        char c;
        for(int i = 0 ; i < n; i++){
            c = s.charAt(i);
            if(c == ‘ ‘){
                array[size++] = ‘%‘;
                array[size++] = ‘2‘;
                array[size++] = ‘0‘;
            }else{
                array[size++] = c;
            }
        }
        String news = new String(array, 0, size);
        return news;
    }
}*/

class Solution {
    public String replaceSpace(String s) {
        int n = s.length();
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i  <  s.length(); i++){
            if(s.charAt(i) == ‘ ‘ ){
                sb.append("%20");
            }else{
                sb.append(s.charAt(i));
            }
        }
        return sb.toString();
    }
}

○ 20. 表示数值的字符串：判断是不是字符串 《是不是 +-e ?? 设置 Boolean开关》

class Solution {
     public boolean isNumber(String s) {
        if(s == null || s.length() == 0){
            return false;
        }
       
        boolean numSeen = false;
        boolean dotSeen = false;
        boolean eSeen = false;
        char[] str = s.trim().toCharArray();

        for(int i = 0;i < str.length; i++){
            if(str[i] >= ‘0‘ && str[i] <= ‘9‘){

                    numSeen = true;
                
            }else if(str[i] == ‘.‘){
                //.之前不能出现.或者e
                if(dotSeen || eSeen){
                    return false;
                }
                dotSeen = true;
            }else if(str[i] == ‘e‘ || str[i] == ‘E‘){
                //e之前不能出现e，必须出现数
                if(eSeen || !numSeen){
                    return false;
                }
                eSeen = true;
                numSeen = false;//重置numSeen，排除123e或者123e+的情况,确保e之后也出现数
            }else if(str[i] == ‘-‘ || str[i] == ‘+‘){
                //+-出现在0位置或者e/E的后面第一个位置才是合法的
                if(i != 0 && str[i-1] != ‘e‘ && str[i-1] != ‘E‘){
                    return false;
                }
            }else{//其他不合法字符
                return false;
            }
        }
        return numSeen;
    }



}

○ 38. 字符串的排列：所有排列 放在数组里 《 当成 字符串的 排列组合 输出全部的结果 》 s.toCharArray(); HashSet去重，各种交换

class Solution {

    List<String> res = new LinkedList<>();
    char[] c;
    public String[] permutation(String s) {
        c = s.toCharArray();
        dfs(0);
        return res.toArray(new String[res.size()]);
    }
    void dfs(int x) {
        if(x == c.length - 1) {
            res.add(String.valueOf(c));      // 添加排列方案
            return;
        }
        HashSet<Character> set = new HashSet<>();
        for(int i = x; i < c.length; i++) {
            if(set.contains(c[i])) continue; // 重复，因此剪枝
            set.add(c[i]);
            swap(i, x);                      // 交换，将 c[i] 固定在第 x 位
            dfs(x + 1);                      // 开启固定第 x + 1 位字符
            swap(i, x);                      // 恢复交换
        }
    }
    void swap(int a, int b) {
        char tmp = c[a];
        c[a] = c[b];
        c[b] = tmp;
    }
}

○ 46. 把数字翻译成字符串：求不同的翻译方式，因为两位数可以对应ah不同字母 《 0-a 》

class Solution {
    public int translateNum(int num) {
        String s = String.valueOf(num);
        int a = 1, b = 1;
        for(int i = 2; i <= s.length(); i++) {
            String tmp = s.substring(i - 2, i);
            int c = tmp.compareTo("10") >= 0 && tmp.compareTo("25") <= 0 ? a + b : a;
            b = a;
            a = c;
        }
        return a;
    }
}

○ 67. 把字符串转换成整数 《 可以有+- “ ”，截止到不是数字的位置 还有各种 字符串转化 拼接》字符串转换

class Solution {
    public int strToInt(String str) {

        int res = 0, bndry = Integer.MAX_VALUE / 10;
        int i = 0, sign = 1, length = str.length();

        if(length == 0) {
            return 0;
        } 
        while(str.charAt(i) == ‘ ‘){
            if(++i == length){
                return 0;
            }
        }
             
        if(str.charAt(i) == ‘-‘) sign = -1;
        if(str.charAt(i) == ‘-‘ || str.charAt(i) == ‘+‘) i++;

        for(int j = i; j < length; j++) {
            
            if(str.charAt(j) < ‘0‘ || str.charAt(j) > ‘9‘) break;
            
            // 在此轮拼接后是否超过 2147483647 
            if(res > bndry || res == bndry && str.charAt(j) > ‘7‘)
                return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            res = res * 10 + (str.charAt(j) - ‘0‘);
        }
        return sign * res;
    }
}

○ 50. 第一个只出现一次的字符：hashmap 《 用hashmap来存 Chara,Boolean包含不 》 !dic.containsKey(c)

class Solution {
    public char firstUniqChar(String s) {

        HashMap<Character, Boolean> dic = new HashMap<>();
        char[] sc = s.toCharArray();
        for(char c : sc){
            dic.put(c, !dic.containsKey(c));
        }
        for(char c : sc){
            if(dic.get(c)) return c;
        }
        return ‘ ‘;
    }
}

○ 56 - II. 找数组中只出现一次的数 II：hashmap 《 相比于 上一个，也是找只出现一次的数字，但是没有复杂度要求 》 存到HashMap中<num, index> !map.containsKey(key)

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        
        for(int i = 0; i < nums.length; i++){
            int key = nums[i];
            if(!map.containsKey(key)){
                map.put(key, 1);
            }else {
                map.put(key, map.get(key)+1);
            }
        }
        
        for(Map.Entry<Integer, Integer> entry : map.entrySet()){
            if(entry.getValue() == 1){
                return entry.getKey();
            }
        }
        return -1;
    }
}

○ 58 - I. 翻转单词顺序：输出反转后的字符串 《 一句话，直接 split 》

class Solution {
    public String reverseWords(String s) {

        String[] strs = s.trim().split(" "); // 删除首尾空格，分割字符串
        StringBuilder res = new StringBuilder();
        
        for(int i = strs.length - 1; i >= 0; i--) { // 倒序遍历单词列表
            if(strs[i].equals("")) continue; // 遇到空单词则跳过
            res.append(strs[i] + " "); // 将单词拼接至 StringBuilder
        }
        return res.toString().trim(); // 转化为字符串，删除尾部空格，并返回
    }
}

○ 58 - II. 左旋转字符串：截断K，拼到后面 《 字符串，charAt() 》

class Solution {
    public String reverseLeftWords(String s, int n) {
        StringBuilder res = new StringBuilder();
        for(int i = n; i < n + s.length(); i++)
            res.append(s.charAt(i % s.length()));
        return res.toString();
    }
}

○ 字符串压缩

字符串压缩
 输入："aabcccccaaa"
 输出："a2b1c5a3"
class Solution {
    public String compressString(String S) {
        if (S.length() == 0) { // 空串处理
            return S;
        }
        StringBuffer ans = new StringBuffer();
        int cnt = 1;
        char ch = S.charAt(0);
        for (int i = 1; i < S.length(); ++i) {
            if (ch == S.charAt(i)) {
                cnt++;
            } else {
                ans.append(ch);
                ans.append(cnt);
                ch = S.charAt(i);
                cnt = 1;
            }
        }
        ans.append(ch);
        ans.append(cnt);
        return ans.length() >= S.length() ? S : ans.toString();
    }
}

○ 重构字符串 分开重复的

重构字符串 分开重复的
输入: S = "aab"
输出: "aba"
      public String reorganizeString(String S) {
            //把字符串S转化为字符数组
            char[] alphabetArr = S.toCharArray();
            //记录每个字符出现的次数
            int[] alphabetCount = new int[26];
            //字符串的长度
            int length = S.length();
            //统计每个字符出现的次数
            for (int i = 0; i < length; i++) {
                alphabetCount[alphabetArr[i] - ‘a‘]++;
            }
            int max = 0, alphabet = 0, threshold = (length + 1) >> 1;
            //找出出现次数最多的那个字符
            for (int i = 0; i < alphabetCount.length; i++) {
                if (alphabetCount[i] > max) {
                    max = alphabetCount[i];
                    alphabet = i;
                    //如果出现次数最多的那个字符的数量大于阈值，说明他不能使得
                    // 两相邻的字符不同，直接返回空字符串即可
                    if (max > threshold)
                        return "";
                }
            }
            //到这一步说明他可以使得两相邻的字符不同，我们随便返回一个结果，res就是返回
            //结果的数组形式，最后会再转化为字符串的
            char[] res = new char[length];
            int index = 0;
            //先把出现次数最多的字符存储在数组下标为偶数的位置上
            while (alphabetCount[alphabet]-- > 0) {
                res[index] = (char) (alphabet + ‘a‘);
                index += 2;
            }
            //然后再把剩下的字符存储在其他位置上
            for (int i = 0; i < alphabetCount.length; i++) {
                while (alphabetCount[i]-- > 0) {
                    if (index >= res.length) {
                        index = 1;
                    }
                    res[index] = (char) (i + ‘a‘);
                    index += 2;
                }
            }
            return new String(res);
        }

字符串

原文：https://www.cnblogs.com/ming-michelle/p/14704599.html