String

本篇博客只记录刷题思路不记录具体代码，用于本人快速回顾
题目来源代码随想录
奖励自己上半天班😋

  1. 注意Java的String是不可变的，所以很多时候要toChar()
  2. 涉及到交换的操作都很适合双指针
  3. 数组填充优化解决思路：先确定长度再从后往前遍历
  4. KMP 算法

反转字符串

一眼双指针

非常朴素无华，秒了

值得注意的是swap不用temp的高效写法，三次异或

s[l] ^= s[r];  //构造a^b的结果，并放在a中
s[r] ^= s[l];  //a^b的结果再^ b，存入b，此时b=a,a=a^b
s[l] ^= s[r];  //a ^ b的结果再^a，存入a，此时b=a,a=b完成交换

反转字符串Ⅱ

在上一道题的基础上多加一个判断即可

注意最后需要判断尾数够不够k个，来确定end指针的位置，所以我们需要取min：int end = Math.min(ch.length - 1, start + k - 1);

也可以直接用i+k<=s.length()判断

替换数字

思路非常简单，遍历到数字就append”number”（❌）

nono，给的是String类型，String类型是不可变的

所以可以先转成char[]，但是需要先for遍历string确定数字数量再确定char长度，再for填充数组，又要注意是从后往前填充，从前往后的话需要整体向后移动数组后面部分，很麻烦

==》这也是常见的数组填充解决思路，双指针思路

实现strStr()

字符串匹配算法，KMP登场！

又称学一次忘一次算法，在B站上搜教程发现热门前几的视频都收藏过😶

https://www.cnblogs.com/Higurashi-kagome/p/18013626

原始肯定是最容易想到暴力，运气不好的话得匹配到最后一个

KMP就是为了优化这一步：已经知道之前遍历过的字符，那能不能利用这些信息来避免暴力算法中回退的步骤呢

这里就需要一个next数据，记录我们可以回退的数量

img

next数组/前缀表求解思路：寻找子串中相同前后缀的长度，并且一定是最长的前后缀

可以暴力

也可以递推优化

  1. while遍历s，定义当前共同前后缀长度len【why not for，因为i不一定++】
  2. 如果s[i] == s [len]，next[i]= ++len，i++
  3. 如果不相等
    1. len ==0 ，直接 next[i] = 0，i++
    2. len != 0，更新 len = next[len - 1];
      1. 感觉这一步挺难理解的，因为现在为len的字符串是不匹配的，我们就通过next[len-1]找更短的前缀匹配
      2. 比如说ABABA，i=4时len=2，s[i]!=s[len]且len!=0，那我们就更新len为next[len-1]的值
public class KMP {
    public static int[] buildNext(String patt) {
        int[] next = new int[patt.length()];
        next[0] = 0; // 初值设为 0
        int prefixLen = 0; // 当前共同前后缀的长度
        int i = 1;

        while (i < patt.length()) {
            if (patt.charAt(i) == patt.charAt(prefixLen)) {
                // 下一个字符依然相同，长度加 1
                prefixLen++;
                next[i] = prefixLen;
                i++;
            } else {
                // 下一个字符不同
                if (prefixLen == 0) {
                    next[i] = 0;
                    i++;
                } else {
                    // 查表看看其中存不存在更短的前后缀
                    prefixLen = next[prefixLen - 1];
                }
            }
        }
        return next;
    }

有了next数组后：

  1. 双指针：主串指针i和子串指针j
  2. 遍历主串，判断是否和子串对应位置字符匹配
  3. 匹配的话直接++
  4. 不匹配的话根据next跳过子串位置
  5. while后的 j==子串.length，说明匹配成功

重复的子字符串

不要想复杂了这就是一道easy而已呀，直接枚举

  1. for遍历s，i*2<n剪枝
  2. If n%i==0，说明现在有可能成倍匹配，没匹配到就break
  3. 匹配到用boolea信号量return true

还有一种很巧妙的方法是直接复制成ss，然后判断ss(1,length-1)是否包含s，两行完成但是时间和空间效率不高

String str = s + s;
return str.substring(1, str.length() - 1).contains(s);

要是想复杂点（但完美的复杂度）也可以KMP

重复也就是查找