理论

思维导图

第一章 双指针

刷题第一章 双指针

344. 反转字符串

  1. class Solution {
  2. public void reverseString(char[] s) {
  3. int left = 0, right = s.length - 1;
  4. while (left < right) {
  5. char ch = s[left];
  6. s[left] = s[right];
  7. s[right] = ch;
  8. left++;
  9. right--;
  10. }
  11. }
  12. }

541. 反转字符串 II

这道题看着是上面的进阶,其实每个啥,放这里了!

  1. class Solution {
  2. public String reverseStr(String s, int k) {
  3. char[] chs = s.toCharArray();
  4. int n = chs.length - 1;
  5. int start = 0; // 2k长度的第一个点
  6. while (start <= n) { // 当前起始点还在合法范围内
  7. if (start + 2 * k - 1 <= n) { // 即接下来的长度>=2k
  8. reverseString(chs, start, start + k - 1);
  9. start += 2 * k;
  10. } else if (start + k - 1 > n) { // 剩余字符少于 k 个,则将剩余字符全部反转
  11. reverseString(chs, start, n);
  12. break;
  13. } else {
  14. reverseString(chs, start, start + k - 1);
  15. break;
  16. }
  17. }
  18. return new String(chs);
  19. }
  20. public void reverseString(char[] s, int left, int right) {
  21. while (left < right) {
  22. char ch = s[left];
  23. s[left] = s[right];
  24. s[right] = ch;
  25. left++;
  26. right--;
  27. }
  28. }
  29. }

但人家这官网写的代码,说实话,最近差的远

  1. class Solution {
  2. public String reverseStr(String s, int k) {
  3. char[] a = s.toCharArray();
  4. for (int start = 0; start < a.length; start += 2 * k) {
  5. int i = start, j = Math.min(start + k - 1, a.length - 1);
  6. while (i < j) {
  7. char tmp = a[i];
  8. a[i++] = a[j];
  9. a[j--] = tmp;
  10. }
  11. }
  12. return new String(a);
  13. }
  14. }

剑指 Offer 05. 替换空格

这道题太假,不想做了,复制官网代码。
需要从后向前传的那个题目,要输入是数组,且后面有足够空间。
这道题算是双指针吧!

  1. class Solution {
  2. public String replaceSpace(String s) {
  3. int length = s.length();
  4. char[] array = new char[length * 3];
  5. int size = 0;
  6. for (int i = 0; i < length; i++) {
  7. char c = s.charAt(i);
  8. if (c == ' ') {
  9. array[size++] = '%';
  10. array[size++] = '2';
  11. array[size++] = '0';
  12. } else {
  13. array[size++] = c;
  14. }
  15. }
  16. String newStr = new String(array, 0, size);
  17. return newStr;
  18. }
  19. }

151. 翻转字符串里的单词

这道题怎么说,也不想做!
方法一:API调用
image.png

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

方法二:自行编写对应的函数

  1. class Solution {
  2. public String reverseWords(String s) {
  3. StringBuilder sb = trimSpaces(s);
  4. // 翻转字符串
  5. reverse(sb, 0, sb.length() - 1);
  6. // 翻转每个单词
  7. reverseEachWord(sb);
  8. return sb.toString();
  9. }
  10. public StringBuilder trimSpaces(String s) {
  11. int left = 0, right = s.length() - 1;
  12. // 去掉字符串开头的空白字符
  13. while (left <= right && s.charAt(left) == ' ') {
  14. ++left;
  15. }
  16. // 去掉字符串末尾的空白字符
  17. while (left <= right && s.charAt(right) == ' ') {
  18. --right;
  19. }
  20. // 将字符串间多余的空白字符去除
  21. StringBuilder sb = new StringBuilder();
  22. while (left <= right) {
  23. char c = s.charAt(left);
  24. if (c != ' ') {
  25. sb.append(c);
  26. } else if (sb.charAt(sb.length() - 1) != ' ') {
  27. sb.append(c);
  28. }
  29. ++left;
  30. }
  31. return sb;
  32. }
  33. public void reverse(StringBuilder sb, int left, int right) {
  34. while (left < right) {
  35. char tmp = sb.charAt(left);
  36. sb.setCharAt(left++, sb.charAt(right));
  37. sb.setCharAt(right--, tmp);
  38. }
  39. }
  40. public void reverseEachWord(StringBuilder sb) {
  41. int n = sb.length();
  42. int start = 0, end = 0;
  43. while (start < n) {
  44. // 循环至单词的末尾
  45. while (end < n && sb.charAt(end) != ' ') {
  46. ++end;
  47. }
  48. // 翻转单词
  49. reverse(sb, start, end - 1);
  50. // 更新start,去找下一个单词
  51. start = end + 1;
  52. ++end;
  53. }
  54. }
  55. }

剑指 Offer 58 - II. 左旋转字符串

反转字符串还有这个用处??真的很惊奇!!

class Solution {
    public String reverseLeftWords(String s, int n) {
        char[] chs = s.toCharArray();
        reverse(chs, 0, n - 1);
        reverse(chs, n, chs.length - 1);
        reverse(chs, 0, chs.length - 1);
        return new String(chs);
    }
    private void reverse(char[] chs, int left, int right) {
        while (left < right) {
            char ch = chs[left];
            chs[left++] = chs[right];
            chs[right--] = ch;
        }
    }
}

刷题第二站 快慢指针

第二章 字符串算法

刷题第一站 KMP算法

理论

KMP算法解决的是:文本串中是否出现过模式串
str1中的某个子串是否是str2,如果是,返回开始位置。不包含,返回-1.

28. 实现 strStr()

class Solution {
    public int strStr(String haystack, String needle) {
        if (haystack == null || needle == null) {
            return -1;
        }
        if (needle.length() == 0) {
            return 0;
        }
        if (haystack.length() == 0) {
            return -1;
        }
        char[] str1 = haystack.toCharArray();
        char[] str2 = needle.toCharArray();
        int[] next = getNextArray(str2);
        int i1 = 0, i2 = 0;
        while (i1 < str1.length && i2 < str2.length) {
            if (str1[i1] == str2[i2]) {
                i1++;
                i2++;
            } else if (next[i2] == -1) {
                i1++;
            } else {
                i2 = next[i2];
            }
        }
        return i2 == str2.length ? i1 - i2 : -1;
    }

    private int[] getNextArray(char[] str2) {
        if (str2.length == 1) {
            return new int[]{-1};
        }
        int[] next = new int[str2.length];
        next[0] = -1;
        next[1] = 0;
        int i = 2;
        int cn = 0;
        while (i < next.length) {
            if (str2[i - 1] == str2[cn]) {
                next[i++] = ++cn;
            } else if (cn > 0) {
                cn = next[cn];
            } else {
                next[i++] = 0;
            }
        }
        return next;
    }
}

459. 重复的子字符串

这道题是KMP算法,但没懂解法!后面再看下!

刷题第二站 马拉车算法

5. 最长回文子串

暴力解法

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    private int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            --left;
            ++right;
        }
        return right - left - 1;
    }
}

动态规划

class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }

        boolean[][] dp = new boolean[len][len];
        int maxLen = 1;
        int begin = 0;
        // 初始化:所有长度为1的子串都是回文串
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
            if (i != len - 1 && s.charAt(i) == s.charAt(i + 1)) {
                dp[i][i + 1] = true;
                begin = i;
                maxLen = 2;
            }
        }
        for (int i = len - 1 - 2; i >= 0; i--) {
            for (int j = i + 2; j < len; j++) {
                dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1];
                if (dp[i][j] && maxLen < j - i + 1) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }
}

Manacher算法
暂时略!!下面这个代码暂时未通过

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        char[] charArr = manacherString(s);
        int[] pArr = new int[charArr.length];
        int C = -1;
        int R = -1;
        int maxLen = 0, begin = 0;
        for (int i = 0; i < charArr.length; i++) {
            pArr[i] = R > i ? Math.min(pArr[2 * C - R], R - i) : 1;
            while (i + pArr[i] < charArr.length && i - pArr[i] > -1) {
                if (charArr[i + pArr[i]] == charArr[i - pArr[i]]) {
                    pArr[i]++;
                } else {
                    break;
                }
            }
            if (i + pArr[i] - 1 > R) {
                R = i + pArr[i] - 1;
                C = i;
            }
            if (pArr[i] * 2 - 1 > maxLen) {
                maxLen = pArr[i] * 2 - 1;
                begin = i - pArr[i] + 1;
            }
        }
        return s.substring(begin / 2, begin / 2 + maxLen / 2 - 1);
    }
    public char[] manacherString(String str) {
        char[] res = new char[str.length() * 2 + 1];
        int index = 0;
        for (int i = 0; i < res.length; i++) {
            res[i] = (i & 1) == 0 ? '#' : str.charAt(index++);
        }
        return res;
    }
}

647. 回文子串

下面是马拉车算法,中心扩展法也是很重要的,这里略!!

class Solution {
    public int countSubstrings(String s) {
        StringBuilder sb = new StringBuilder();
        sb.append("#");
        for (int i = 0; i < s.length(); i++) {
            sb.append(s.charAt(i));
            sb.append("#");
        }
        int[] pArr = new int[sb.length()];
        int C = -1;
        int R = -1;
        int count = 0;
        for (int i = 0; i < sb.length(); i++) {
            pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1;
            while (i + pArr[i] < pArr.length && i - pArr[i] > -1) {
                if (sb.charAt(i + pArr[i]) == sb.charAt(i - pArr[i])) {
                    pArr[i]++;
                } else {
                    break;
                }
            }
            if (i + pArr[i] - 1 > R) {
                R = i + pArr[i] - 1;
                C = i;
            }
            if (i % 2 == 1) {
                count += (pArr[i]) / 2;
            } else {
                count += pArr[i] / 2;
            }
        }
        return count;
    }
}

680. 验证回文字符串 Ⅱ

class Solution {
    public boolean validPalindrome(String s) {
        if (s == null) return false;
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) == s.charAt(right)) {
                left++;
                right--;
            } else {
                break;
            }
        }
        // 此时结束可能是right >= left;当然也可能是遇到不相等了
        if (right <= left) return true;
        // 下面是跳一个
        boolean left_1 = true;
        int a = left + 1, b = right;
        while(a < b) {
            if (s.charAt(a) == s.charAt(b)) {
                a++;
                b--;
            } else {
                left_1 = false;
                break;
            }
        }

        boolean right_1 = true;
        a = left;
        b = right - 1;
        while(a < b) {
            if (s.charAt(a) == s.charAt(b)) {
                a++;
                b--;
            } else {
                right_1 = false;
                break;
            }
        }
        return left_1 || right_1;
    }
}

409. 最长回文串

class Solution {
    public int longestPalindrome(String s) {
        int[] count = new int[52];
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) >= 'a' && s.charAt(i) <= 'z') {
                count[s.charAt(i) - 'a']++;
            } else {
                count[s.charAt(i) - 'A' + 26]++;
            }
        }
        int res = 0;
        for (int num : count) {
            res += num / 2;
        }
        res <<= 1;
        res = res < s.length()? res + 1 : res;
        return res;
    }
}

第三章 滑动窗口

刷题第一站 滑动窗口

3. 无重复字符的最长子串

以后滑动窗口模板尽量就用这个代码!!看看是否可行!!

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 哈希函数,记录每个字符是否出现过
        Set<Character> occ = new HashSet<Character>();
        int n = s.length();
        // 右指针,初始值为-1,相当于我们在字符串的左边界的左侧,还没有开始移动
        int rk = -1, ans = 0;
        for (int i = 0; i < n; i++) {
            if (i != 0) {
                // 左指针向右移动一格,移除一个字符
                occ.remove(s.charAt(i - 1));
            }
            while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
                // 不断地移动右指针
                occ.add(s.charAt(rk + 1));
                rk++;
            }
            // 第i到rk个字符是一个极长的无重复字符子串
            ans = Math.max(ans, rk - i + 1);
        }
        return ans;
    }
}

其它

刷题第一站

6. Z 字形变换

题解

class Solution {
    public String convert(String s, int numRows) {
        if (numRows < 2) return s;
        List<StringBuffer> list = new ArrayList<StringBuffer>();
        for (int i = 0; i < numRows; i++) {
            list.add(new StringBuffer());
        }
        int row = 0, flag = -1;
        for (Character c : s.toCharArray()) {
            list.get(row).append(c);
            if (row == 0 || row == numRows - 1) {
                flag = -flag;
            }
            row += flag;
        }
        StringBuffer res = new StringBuffer();
        for (StringBuffer sb : list) {
            res.append(sb);
        }
        return res.toString();
    }
}

总结