04字符串算法/代码随想录
四、字符串
-
反转字符串
力扣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数组赋值
-
原文地址：https://blog.csdn.net/2403_86942375/article/details/143495338
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！