四、字符串
-
反转字符串
力扣344
遇到数组双指针真是太好用了，左右指针不断逼近即可，代码也很简单
class Solution {public void reverseString(char[] s) {int fast = s.length - 1;int slow = 0;while (slow <= fast) {char temp = s[fast];s[fast] = s[slow];s[slow] = temp;fast--;slow++;}} } -
翻转字符串II
力扣541
由于java中字符串是不可变的，所以需要创建一个数组来更改代码，然后就是双指针了，双指针在数组中移动变化真的特别好用。
class Solution {public String reverseStr(String s, int k) {char[] re = s.toCharArray(); int n = s.length();for (int i = 0; i < n; i += 2 * k) {reverse(re, i, Math.min(i + k, n) - 1);}return new String(re);}public void reverse(char[] arr, int left, int right) {while (left <= right) {char temp = arr[left];arr[left] = arr[right];arr[right] = temp;left++;right--;}} }不要被两个条件个唬掉了，其实一个循环就能搞定，本质上就是剩下的数组不满2k个，那么就前面一半反转，唯一区别的就算可能不满一半，这里需要注意，获取的是数组的长度，而想改变数组的内容需要通过下标获取，所以记得下标和个数的转换。这里只要定义一个转换函数，就清晰了，主函数使用长度，方便区间的改变，传入参数减1就变成下标了（非常推荐这种做法，把长度和索引的逻辑区分开来，这样不会混乱）。接下来就算主函数的书写了，终止条件是数组的长度，每次加2k（也就是把两个条件合并在一起得出的结论），只需要传入函数生活判断，到底是i+k大还是n大，就可以完美解决两个条件。
-
反转字符串里的单词
力扣151
-
常规思路是先去除头尾的空格，以及单词间重复的空格，然后对单词进行反转，再对整个字符串反转，注意java字符串不能改变，记得转换为数组。这里的时间复杂度是O（n），虽然看到while嵌套while，但不代表一定是O（n²），这里的想法比较巧妙，看到空格就删除空格，每次单词添加结束后再加空格即可，这样剩下了大量的时间。其实也就是双指针，快指针去删空格，慢指针等添加完单词再加空格
class Solution {public String reverseWords(String s) {String sb = removeExtraSpaces(s);char[] chars = reserveEachWords(sb);reverseAll(chars); // 修改了这里return new String(chars);}public String removeExtraSpaces(String s) {StringBuilder sb = new StringBuilder();int n = s.length();int i = 0;while (i < n) {while (i < n && s.charAt(i) == ' ') i++;if (i >= n) break;if (sb.length() > 0) sb.append(' ');while (i < n && s.charAt(i) != ' ') sb.append(s.charAt(i++));}return sb.toString();}public char[] reserveEachWords(String s) {char[] sb = s.toCharArray();int start = 0;for (int i = 0; i < sb.length; i++) {if (sb[i] == ' ') {reverse(sb, start, i - 1);start = i + 1;}}reverse(sb, start, sb.length - 1);return sb;}private void reverse(char[] sb, int left, int right) {while (left < right) {char temp = sb[left];sb[left] = sb[right];sb[right] = temp;left++;right--;}}private void reverseAll(char[] sb) {reverse(sb, 0, sb.length - 1); } }
-
-
实现strStr
力扣28
-
暴力没什么好说的，两层循环暴力查找
class Solution {public int strStr(String haystack, String needle) {int n = haystack.length();int m = needle.length();int i = 0;while (i <= n - m) {int t = 0;while (t < m && haystack.charAt(i + t) == needle.charAt(t)) {t++;}if (t == m) {return i;}i++;}return -1;} } -
典型的kmp算法，构建next数组，进行查询
class Solution {public int strStr(String haystack, String needle) {int[] next = new int[needle.length()];getNext(next, needle);int j = 0;for (int i = 0; i < haystack.length(); ++i) {while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {j = next[j - 1];}if (haystack.charAt(i) == needle.charAt(j)) {j++;}if (j == needle.length()) {return i - needle.length() + 1;}}return -1;}public void getNext(int[] next, String s) {int j = 0;next[0] = 0;for (int i = 1; i < s.length(); ++i) {while (j > 0 && s.charAt(i) != s.charAt(j)) {j = next[j - 1];}if (s.charAt(i) == s.charAt(j)) {j++;} next[i] = j;}} } -
什么是kmp算法呢，我们叫被匹配的字符串叫模板串，要匹配的叫主串，当模板串匹配到几个主串的时候，但突然不一样了，像暴力算法O（mn）就要重新匹配，而kmp会根据对应next数组去进行跳转匹配。kmp算法的kmp是三位大佬的名字，其实就是一个结论，最长相同前缀后缀的值对应每一个模板串，但匹配到对用模板串一个字符的时候出现错误，根据这字符的前一个字符的最长相同前缀后缀值，把匹配的值跳转到对应的索引（就是前一个字符的最长相同前缀后缀值），这样就减少了重复匹配。后面难点就是在构建next数组，就算计算各个字符的最长相同前缀后缀值。在getNext函数中，j代表的是前缀值以及最长相同前缀后缀值，i代表的是后缀值。for循环面临两种情况，一个是前缀后缀相匹配，一个是不匹配，不匹配就跳转到前一个字符的最长相同前缀后缀值，正好对应了kmp算法思想，然后循环到索引为0位置（如果一直匹配不到），然后就把前一个字符的最长相同前缀后缀值赋值过来即可，然后给next数组赋值。如果匹配到了就+1，然后给next数组赋值
-
