上海网站推广 优帮云,隆基泰和 做网站,做网站订阅号,wordpress双域名代码随想录-035期-算法训练营【博客笔记汇总表】-CSDN博客 第四章 字符串part02
今日任务 ●28. 实现 strStr()
●459.重复的子字符串
●字符串总结
●双指针回顾 详细布置 28. 实现 strStr() #xff08;本题可以跳过#xff09;因为KMP算法很难#xff0c;大家别奢求 一… 代码随想录-035期-算法训练营【博客笔记汇总表】-CSDN博客 第四章 字符串part02
今日任务 ●28. 实现 strStr()
●459.重复的子字符串
●字符串总结
●双指针回顾 详细布置 28. 实现 strStr() 本题可以跳过因为KMP算法很难大家别奢求 一次就把kmp全理解了大家刚学KMP一定会有各种各样的疑问先留着别期望立刻啃明白第一遍了解大概思路二刷的时候再看KMP会 好懂很多。或者说大家可以放弃一刷可以不看KMP今天来回顾一下之前的算法题目就可以。因为大家 算法能力还没到细扣 很难的算法会把自己绕进去就算别人给解释只会激发出更多的问题和疑惑。
所以大家先了解大体过程知道这么回事 等自己有 算法基础和思维了在看多看几遍视频慢慢就理解了。题目链接/文章讲解/视频讲解https://programmercarl.com/0028.%E5%AE%9E%E7%8E%B0strStr.html 459.重复的子字符串 本题可以跳过本题算是KMP算法的一个应用不过 对KMP了解不够熟练的话理解本题就难很多。
我的建议是 KMP和本题一刷的时候 可以适当放过了解怎么回事就行二刷的时候再来硬啃题目链接/文章讲解/视频讲解https://programmercarl.com/0459.%E9%87%8D%E5%A4%8D%E7%9A%84%E5%AD%90%E5%AD%97%E7%AC%A6%E4%B8%B2.html 字符串总结 比较简单大家读一遍就行 题目链接/文章讲解https://programmercarl.com/%E5%AD%97%E7%AC%A6%E4%B8%B2%E6%80%BB%E7%BB%93.html 双指针回顾 此时我们已经做过10到双指针的题目了来一起回顾一下大家自己也总结一下双指针的心得 文章讲解https://programmercarl.com/%E5%8F%8C%E6%8C%87%E9%92%88%E6%80%BB%E7%BB%93.html
目录
0028_实现strStr()
0459_重复的子字符串
字符串总结
双指针回顾 0028_实现strStr()
class Solution0028 {public int strStr(String haystack, String needle) {if (haystack.equals(needle)) {return 0;}if (!haystack.contains(needle)) {return -1;} else {String str[] haystack.split(needle);if (str.length 0) {return 0;} else {return str[0].length();}}}
}
class Solution0028_1 {/*** 基于窗口滑动的算法* 时间复杂度O(m*n)* 空间复杂度O(1)* 注n为haystack的长度m为needle的长度*/public int strStr(String haystack, String needle) {int m needle.length();// 当 needle 是空字符串时我们应当返回 0if (m 0) {return 0;}int n haystack.length();if (n m) {return -1;}int i 0;int j 0;while (i n - m 1) {// 找到首字母相等while (i n haystack.charAt(i) ! needle.charAt(j)) {i;}if (i n) {// 没有首字母相等的return -1;}// 遍历后续字符判断是否相等i;j;while (i n j m haystack.charAt(i) needle.charAt(j)) {i;j;}if (j m) {// 找到return i - j;} else {// 未找到i - j - 1;j 0;}}return -1;}
}// 方法一
class Solution0028_2 {public void getNext(int[] next, String s) {int j -1;next[0] j;for (int i 1; i s.length(); i) {while (j 0 s.charAt(i) ! s.charAt(j 1)) {j next[j];}if (s.charAt(i) s.charAt(j 1)) {j;}next[i] j;}}public int strStr(String haystack, String needle) {if (needle.length() 0) {return 0;}int[] next new int[needle.length()];getNext(next, needle);int j -1;for (int i 0; i haystack.length(); i) {while (j 0 haystack.charAt(i) ! needle.charAt(j 1)) {j next[j];}if (haystack.charAt(i) needle.charAt(j 1)) {j;}if (j needle.length() - 1) {return (i - needle.length() 1);}}return -1;}
}class Solution0028_3 {//前缀表不减一Java实现public int strStr(String haystack, String needle) {if (needle.length() 0) return 0;int[] next new int[needle.length()];getNext(next, needle);int j 0;for (int i 0; i haystack.length(); i) {while (j 0 needle.charAt(j) ! haystack.charAt(i))j next[j - 1];if (needle.charAt(j) haystack.charAt(i))j;if (j needle.length())return i - needle.length() 1;}return -1;}private 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(j) ! s.charAt(i))j next[j - 1];if (s.charAt(j) s.charAt(i))j;next[i] j;}}
}
0459_重复的子字符串
class Solution0459 {public boolean repeatedSubstringPattern(String s) {return (s s).indexOf(s, 1) ! s.length();}public boolean repeatedSubstringPattern2(String s) {int n s.length();// 外层循环控制子字符串的长度for (int len 1; len n / 2; len) {// 如果字符串长度不能整除子字符串长度则不可能是重复子字符串if (n % len ! 0) continue;// 获取当前子字符串String sub s.substring(0, len);// 内层循环检查是否所有子字符串都相同boolean allMatch true;for (int i len; i n; i len) {if (!sub.equals(s.substring(i, i len))) {allMatch false;break;}}// 如果所有子字符串都相同则返回 trueif (allMatch) return true;}// 如果所有子字符串长度都不满足条件则返回 falsereturn false;}public boolean repeatedSubstringPattern3(String s) {if (s.equals()) return false;int len s.length();// 原串加个空格(哨兵)使下标从1开始这样j从0开始也不用初始化了s s;char[] chars s.toCharArray();int[] next new int[len 1];// 构造 next 数组过程j从0开始(空格)i从2开始for (int i 2, j 0; i len; i) {// 匹配不成功j回到前一位置 next 数组所对应的值while (j 0 chars[i] ! chars[j 1]) j next[j];// 匹配成功j往后移if (chars[i] chars[j 1]) j;// 更新 next 数组的值next[i] j;}// 最后判断是否是重复的子字符串这里 next[len] 即代表next数组末尾的值if (next[len] 0 len % (len - next[len]) 0) {return true;}return false;}
}
字符串总结 代码随想录-字符串总结 双指针回顾 代码随想录-双指针总结
