字符串篇二

反转字符

344. 反转字符串 - 力扣（LeetCode）

class Solution {
    public void reverseString(char[] s) {
        int r = s.length - 1;
        int l = 0;
        while(l < r){
            s[l] ^= s[r];
            s[r] ^= s[l];
            s[l] ^= s[r];
            l++;
            r--;
        }
    }
}

541. 反转字符串 II - 力扣（LeetCode）

每次只操作i + 2*k个数目的字符（其实是 i + k个数目的字符），直到最后不到2k个字符为止

class Solution {
    public String reverseStr(String s, int k) {
        int n = s.length();
        char[] arr = s.toCharArray();
        for(int i = 0; i < n; i += 2*k){
            //这里对于   Math.min(i + k, n) - 1   的-1操作解释一下，因为不论是i + k还是n都代表的是一个位置（它从1开始的）
            //起始位置 i 终点位置 i + k  - 1和 n - 1进行比较 
            reverseString(arr, i, Math.min(i + k, n) - 1);
        }
        return new String(arr);
    }
    //两个字符相互交换一定是在字符数组之中
    public void reverseString(char[] s, int l, int r) {
        while (l < r) {
            s[l] ^= s[r];
            s[r] ^= s[l];
            s[l] ^= s[r];
            l++;
            r--;
        }
    }
}

557. 反转字符串中的单词 III - 力扣（LeetCode）

• 总的来说这种写法比较考验脑子尤其在于对于字符串中的单一单词逆序的处理 i - 1 + start - j（不提倡的写法）

class Solution {
    public String reverseWords(String s) {
        int i = 0, n = s.length();
        StringBuilder bs = new StringBuilder();
        while(i < n){
            //记录空格后的第一个单词
            int start = i;
            //如果是第一个单词的前面有空格那就停在第一个位置上面
            //这个就是为了找到(每一个单词之后的)第一个空格
            while(i < n && s.charAt(i) != ' ') i++;
            //处理   空格后的第一个单词  和单词后的第一个空格的位置单词
            for (int j = start; j < i; j++) bs.append(s.charAt(i - 1 + start - j));
            //专门处理空格(为了防止有多个空格的出现)
            while(i < n && s.charAt(i) == ' '){
                bs.append(' ');
                i++;
            }
        }
        return bs.toString();
    }
}

这种方法可以经常练习一下双指针的操作

class Solution {
    public String reverseWords(String s) {
        StringBuilder ret = new StringBuilder();
        int l = 0, r = 0, n = s.length();
        while (r < n) {
            //l每次记录单词的第一个字母，r每次记录i所在那个单词后的第一个空格
            if (s.charAt(r) == ' ') {
                StringBuilder tmp = new StringBuilder(s.substring(l, r));
                ret.append(tmp.reverse());
                ret.append(' ');
                l = r + 1;
            }
            r++;
        }
        StringBuilder tmp = new StringBuilder(s.substring(l, r));
        ret.append(tmp.reverse());
        return ret.toString();
    }
}

151. 反转字符串中的单词 - 力扣（LeetCode）

学习新API

class Solution {
    public String reverseWords(String s) {
        // 除去开头和末尾的空白字符
        s = s.trim();
        // 正则匹配连续的空白字符作为分隔符分割
        List<String> wordList = Arrays.asList(s.split("\\s+"));
        Collections.reverse(wordList);
        return String.join(" ", wordList);
    }
}

中心扩展法

5. 最长回文子串 - 力扣（LeetCode）

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() <= 1) return s;
        int strLen = s.length();
        int maxStart = 0;  //起点
        int maxEnd = 0;//终点
        int maxLen = 1;//长度
        boolean[][] f = new boolean[strLen][strLen];
        for (int r = 1; r < strLen; r++) {
            for (int l = 0; l < r; l++) {
                if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || f[l + 1][r - 1])) {
                    f[l][r] = true;
                    if (r - l + 1 > maxLen) {
                        maxLen = r - l + 1;
                        maxStart = l;
                        maxEnd = r;
                    }
                }
            }
        }
        return s.substring(maxStart, maxEnd + 1);
    }
}

647. 回文子串 - 力扣（LeetCode）

class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                String ss = s.substring(j, i + 1);
                if (ss.equals(new StringBuilder(ss).reverse().toString())) {
                    ans++;
                }
            }
        }
        return ans;
    }
}