前言
昨天没有更新训练营第九天内容，是因为昨天的任务是 LeetCode 28. 实现 strStr()，使用 KMP算法进行解答， 关于KMP算法可以查看我之前的文章 从 KMP算法到 Java的 String.indexOf(String str)方法, 今天还是关于 KMP算法的，但是主要是复习，想学习KMP算法相关的可以看我之前的文章
今日任务：
- 459.重复的子字符串
- 字符串总结
- 双指针回顾
459.重复的子字符串
题目描述
思路分析
老规矩 去判断字符串是否为空， 如果为 null就直接返回掉
为字符串新增虚拟头，方便我们后续的操作
然后里面一整个for循环都是用来记录前缀表用的, 具体如下
for (int i = 2, j = 0; i <= len; i++) { // 处理元素不一致的情况， 进行后退操作 while(j > 0 && s.charAt(i) != s.charAt(j + 1)){ j = next[j]; } // 如果元素一致， 则 j++，表示公共前缀+1 if (s.charAt(i) == s.charAt(j + 1)){ j++; } // 存放当前元素和下标几有公共前缀 next[i] = j; } 复制代码
最后去判断最后一个数的最长公共前缀下标是否大于0， 如果不大于 0就证明这个元素肯定没有公共前缀， 那肯定是错的， 如果大于0之后， 再去计算出公共前缀的长度， 用字符串的长度 % 公共前缀的长度， 如果等于 0，则代表字符串都是由这一个公共前缀重复组成的
这一段不是很好理解，可以去看 代码随想录 或者 我的文章也可以通过 LeetCode里面的代码示例来 debug调试理解
代码展示
public static boolean repeatedSubstringPattern(String s) { // 判断当前入参是否为 null if (s.length() == 0){ return false; } // 获取初始 s的长度 int len = s.length(); // 为字符串 s新增虚拟头结点 s = " " + s; // 根据新的字符串生成 公共前缀数组 int[] next = new int[len+1]; // 遍历 for (int i = 2, j = 0; i <= len; i++) { // 处理元素不一致的情况， 进行后退操作 while(j > 0 && s.charAt(i) != s.charAt(j + 1)){ j = next[j]; } // 如果元素一致， 则 j++，表示公共前缀+1 if (s.charAt(i) == s.charAt(j + 1)){ j++; } // 存放当前元素和下标几有公共前缀 next[i] = j; } // 判断是否为一个子串重复构成 if (next[len] > 0 && len % (len - next[len]) == 0){ return true; } return false; } 复制代码
提交结果
字符串总结
什么是字符串
字符串就是由一堆字符组成的有限序列，也可以理解为一个字符数组，毕竟我们遍历字符串的时候通常是转成一个 char[]或者获取指定下标的字符进行操作
// 遍历字符串的常规操作 String str = "abc"; char[] chars = str.toCharArray(); for (int i = 0; i < chars.length; i++) { System.out.println(chars[i]); } for (int i = 0; i < s.length(); i++) { System.out.println(s.charAt(i)); } 复制代码
使用类的已有方法做算法题吗？
除非你了解这个方法的内部实现， 否则是不建议在做算法题的时候直接使用方法的
双指针法
在字符串反转，移除元素，反转单词等题中都有使用到双指针法，在工作中也有真真切切的去使用到，由此可见算法还是要会的，可以不精，但是当工作中碰到难题不至于两眼发懵
同时双指针法的时间复杂度是 O(n)
反转系列
这个感觉相对简单一点，主要就是在细节处理上，这里借用代码随想录的一句话:当需要固定规律一段一段去处理字符串的时候，要想想在在for循环的表达式上做做文章
KMP
KMP 算法就是处理字符串匹配等问题的， 它利用了公共前缀来记录之前匹配过的信息， 能够让我们节省很多时间不用去重复匹配
这个真的很难，很重要， 我第一次看的时候看文字真的一脸懵逼，看了三遍视频，又 debug了一遍才明白
总结
可能是距离上次做字符串部分还不到一个月，这次做起来有种游刃有余的感觉，也可能是因为这次简单题居多的原因吧，等到后面回溯之后估计就开始一脸懵逼了
双指针回顾
双指针法： 是指一快一慢两个指针在同一个 for循环内完成两个 for循环的工作
- 暴力解法时间复杂度： O(n^2)
- 双指针时间复杂度： O(n)
关于双指针法比较经典的题有： 反转字符串，判断一个字符串是否为回文字符串，在一个有序数组内判断存不存在两数之和等于target等
总结
一转眼代码随想录训练营已经十天了，十天的进度：数组，链表，哈希表，字符串，按照语句训练营时长两个月一刷还有五十天，坚持就是胜利，日积硅步以致千里
