本文是每天跟着代码随想录刷题时做的笔记，用来总结与复习。

目录

344.反转字符串

541.反转字符串Ⅱ

剑指offer 05.替换空格

151.反转字符串里的单词

剑指offer 58-Ⅱ.左旋转字符串

28.实现strStr()

459.重复的子字符串

今日总结

---

344.反转字符串

题目链接：344. 反转字符串 - 力扣（LeetCode） (leetcode-cn.com)

思路：思路很简单，就是一个双指针加元素交换

 public void reverseString(char[] s) {int left = 0;int right = s.length - 1;while (left < right){char temp = s[left];s[left++] = s[right];s[right--] = temp;}}

541.反转字符串Ⅱ

题目链接：541. 反转字符串 II - 力扣（LeetCode） (leetcode-cn.com)

思路：在字符串长度范围内反转 0 + (2 * k) * i ~ (k - 1) + (2 * k) * i 下标的字符串，i 取值为 0，1，2，3.....，其中注意判断超出字符串长度的情况即可。

public String reverseStr(String s, int k) {char[] chars = s.toCharArray();int left = 0;int right = left + k - 1;if (right >= chars.length){right = chars.length - 1;}while (right < chars.length){int fLeft = left;int fRight = right;while (fLeft < fRight){char temp = chars[fLeft];chars[fLeft++] = chars[fRight];chars[fRight--] = temp;}left += 2 * k;right += 2 * k;if (left >= chars.length){break;}if (right >= chars.length){right = chars.length - 1;}}return new String(chars);}

剑指offer 05.替换空格

题目链接：剑指 Offer 05. 替换空格 - 力扣（LeetCode） (leetcode-cn.com)

思路：

①：直接使用 String 中的 replace 方法

    public String replaceSpace(String s) {String s1 = s.replace(" ", "%20");return s1;}

②：不使用库函数的解法，使用 StringBuilder 来进行字符串的拼接，提高速度

public String replaceSpace(String s) {StringBuilder str = new StringBuilder();for(int i = 0 ; i < s.length(); i++){char ch = s.charAt(i);if(ch == ' '){str.append("%20");} else{str.append(ch);} }return str.toString();
}

③：正规解法：先将字符串长度扩充到替换后的长度，这里要使用 StringBuilder 来进行扩充，因为 String 是不可变长的。设置两个指针，一个指向扩充前字符串末尾 (bf) ，一个指向扩充后的字符串末尾 (af) ，使用 bf 由前往后遍历字符串，若查找到空格，则使用 af 存入 "%20"，若没有查找到空格，则使用 af 存入 bf 对应字符

public String replaceSpace(String s){int count = 0;for (int i = 0; i < s.length(); i++) {if (s.charAt(i) == ' '){count++;}}StringBuilder stringBuilder = new StringBuilder(s);for (int i = 0; i < count; i++) {stringBuilder.append("  ");}String str = stringBuilder.toString();char[] chars = str.toCharArray();int bf = s.length() - 1;int af = stringBuilder.length() - 1;while (bf >= 0){if (chars[bf] == ' '){chars[af--] = '0';chars[af--] = '2';chars[af--] = '%';bf--;}else {chars[af--] = chars[bf--];}}return new String(chars);}

151.反转字符串里的单词

题目链接：151. 翻转字符串里的单词 - 力扣（LeetCode） (leetcode-cn.com)

思路：

①：使用 String 中的 split 函数来获取每一个单词，在将单词进行拼接

public String reverseWords(String s) {String[] s1 = s.split(" ");StringBuilder str = new StringBuilder();int flag = 0;while (s1[flag].equals("")){flag++;}for (int i = s1.length - 1;  i > flag; i--) {if (!s1[i].equals("")){str.append(s1[i]);str.append(" ");}}str.append(s1[flag]);return str.toString();}

②：不使用库函数：先去除字符串头尾的空格，再将字符串反序并处理中间空格，如下

原字符串：

处理完后的字符串：  

最后再通过空格作为标志获取每个单词，将每个单词反转即可

public String reverseWords(String s) {char[] chars = s.toCharArray();int left = 0;int right = chars.length - 1;StringBuilder newStr = new StringBuilder();//去除头尾的空格while (left <= right){if (chars[left] == ' '){left++;}if (chars[right] == ' '){right--;}if (chars[left] != ' ' && chars[right] != ' '){break;}}//将字符串反序，并处理中间空格int bfRight = right - 1;while (right > left){if (chars[right] != ' ' || (chars[right] == ' ' && chars[bfRight] != ' ')){newStr.append(chars[right]);}right--;bfRight--;}newStr.append(chars[left]);getAndReverse(newStr);return newStr.toString();}//得到每个单词并将其反转public void getAndReverse(StringBuilder stringBuilder){int head = 0;int end = 0;while (end < stringBuilder.length()){if (stringBuilder.charAt(end) == ' '){reverse(stringBuilder, head, end - 1);head = end + 1;}end++;}reverse(stringBuilder, head, end - 1);}//反转每个单词public void reverse(StringBuilder stringBuilder, int head, int end){while (head < end){char temp = stringBuilder.charAt(head);stringBuilder.setCharAt(head, stringBuilder.charAt(end));stringBuilder.setCharAt(end, temp);head++;end--;}}

剑指offer 58-Ⅱ.左旋转字符串

题目链接：剑指 Offer 58 - II. 左旋转字符串 - 力扣（LeetCode） (leetcode-cn.com)

思路：

①：截取对应子串进行拼接

public String reverseLeftWords(String s, int n){StringBuilder ansStr = new StringBuilder();ansStr.append(s.substring(n, s.length()));ansStr.append(s.substring(0, n));return ansStr.toString();}

②：先反转整个字符串，再反转对应的对应子串

 public String reverseLeftWords(String s, int n){StringBuilder ansStr = new StringBuilder(s);int length = ansStr.length();reverse(ansStr, 0, length - 1);reverse(ansStr, 0, length - n - 1);reverse(ansStr, length - n, length - 1);return ansStr.toString();}public void reverse(StringBuilder stringBuilder, int head, int end){while (head < end){char temp = stringBuilder.charAt(head);stringBuilder.setCharAt(head, stringBuilder.charAt(end));stringBuilder.setCharAt(end, temp);head++;end--;}}

28.实现strStr()

题目链接：28. 实现 strStr() - 力扣（LeetCode） (leetcode-cn.com)

思路：

①：Horspool算法：设置一个移动表，设置规则如下图所示，根据匹配不成功时 haystack 字符串与 needle 字符串末尾对应的字符 c 的不同情况来对照移动表进行移动。

 

public int strStr(String haystack, String needle) {if (needle.length() == 0){return 0;}Map<Character, Integer> move = new HashMap<>();int flag = needle.length() - 1;int count = 0;if (needle.length() > 1){while (flag > 0){flag--;count++;if (!move.containsKey(needle.charAt(flag))){move.put(needle.charAt(flag), count);}}}int hayPo = needle.length() - 1;while (hayPo < haystack.length()){int nePo = needle.length() - 1;int moveHayPo = hayPo;while (needle.charAt(nePo) == haystack.charAt(moveHayPo)){nePo--;moveHayPo--;if (nePo < 0){return moveHayPo + 1;}}if (move.containsKey(haystack.charAt(hayPo))){hayPo += move.get(haystack.charAt(hayPo));}else {hayPo += needle.length();}}return -1;}

②：KMP 算法：直接学习卡哥的视频：

帮你把KMP算法学个通透！（理论篇）哔哩哔哩bilibili

帮你把KMP算法学个通透！（求next数组代码篇）哔哩哔哩bilibili

public int strStr(String haystack, String needle) {if (needle.length() == 0){return 0;}int[] next = new int[needle.length()];next[0] = 0;int j = 0;for (int i = 1; i < needle.length(); i++){while (j > 0 && needle.charAt(j) != needle.charAt(i)){j = next[j - 1];}if (needle.charAt(j) == needle.charAt(i)){j++;}next[i] = j;}int needPo = 0;for (int i = 0; i < haystack.length(); i++) {while (needPo > 0 && needle.charAt(needPo) != haystack.charAt(i))needPo = next[needPo - 1];if (needle.charAt(needPo) == haystack.charAt(i))needPo++;if (needPo == needle.length())return i - needle.length() + 1;}return -1;}

459.重复的子字符串

题目链接：459. 重复的子字符串 - 力扣（LeetCode） (leetcode-cn.com)

思路：同样使用 kmp 算法，通过分析 next 数组可以发现，如果用字符串的长度减去最长公共前后缀可以整除字符串的长度，那么则表示该字符串符合题意（当然是看的题解啦😭😭😭）

public boolean repeatedSubstringPattern(String s) {int length = s.length();if (s.equals("")){return false;}int[] next = new int[length];next[0] = 0;int j = 0;for (int i = 1; i < length; i++) {while (j > 0 && s.charAt(j) != s.charAt(i)){j = next[j - 1];}if (s.charAt(i) == s.charAt(j)){j++;}next[i] = j;}if (next[length - 1] > 0 && length % (length - next[length - 1]) == 0){return true;}return false;}

今日总结

难点就是 kmp 算法，得多去理解