Leetcode刷题day9|字符串二|28.实现strStr(),459.重复的子字符串,字符串总结，双指针总结

Dear 丶 2024-03-30 15:32 11阅读 0赞

##  ##

#### 文章目录 ####

*  
 *   *  一、实现strStr()
     *   *  思路分析
         *  图示分析
         *  AC代码
     *  二、重复的子字符串
     *   *  思路分析
         *  图示分析
         *  AC代码
     *  三、字符串总结
     *   *  什么是字符串
         *  要不要使用库函数
         *  字符串编程题常用算法
         *   *  双指针法
             *  反转系列
             *  KMP算法
     *  四、双指针总结
     *   *  数组篇
         *  链表篇
         *  字符串篇
         *  N数之和

### 一、实现strStr() ###

#### 思路分析 ####

#### 图示分析 ####

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-40fetyPJ-1673002939282)(F:\\typora插图\\image-20230106160520583.png)\]

#### AC代码 ####

class Solution {
        
        public int strStr(String haystack, String needle) {
        
            int n = haystack.length(), m = needle.length();
            if (m == 0) {
        
                return 0;
            }
            int[] pi = new int[m];
            for (int i = 1, j = 0; i < m; i++) {
        
                while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
        
                    j = pi[j - 1];
                }
                if (needle.charAt(i) == needle.charAt(j)) {
        
                    j++;
                }
                pi[i] = j;
            }
            for (int i = 0, j = 0; i < n; i++) {
        
                while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
        
                    j = pi[j - 1];
                }
                if (haystack.charAt(i) == needle.charAt(j)) {
        
                    j++;
                }
                if (j == m) {
        
                    return i - m + 1;
                }
            }
            return -1;
        }
    }

### 二、重复的子字符串 ###

#### 思路分析 ####

#### 图示分析 ####

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TJ8rmvxg-1673002994091)(F:\\typora插图\\image-20221128145629476.png)\]

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-IuMWABBq-1673002994092)(F:\\typora插图\\image-20221128150725440.png)\]

#### AC代码 ####

class Solution {
        
        public boolean repeatedSubstringPattern(String s) {
        
            if (s.equals("")) return false;
            int len = s.length();
            s = " " + s;
            char[] chars = s.toCharArray();
            int[] next = new int[len + 1];
            for (int i = 2, j = 0; i <= len; i++) {
        
                while (j > 0 && chars[i] != chars[j + 1]) j = next[j];
                if (chars[i] == chars[j + 1]) 
                    j++;
                next[i] = j;
            }
            if (next[len] > 0 && len % (len - next[len]) == 0) {
        
                return true;
            }
            return false;
        }
    }

### 三、字符串总结 ###

#### 什么是字符串 ####

字符串是由若干字符串组成的有限序列。

C/C++是以’\\0’为结尾，java不是。

我们在处理字符串相关问题经常使用chatAt函数或者将字符串通过toCharArray函数转化称为字符数组处理。。

#### 要不要使用库函数 ####

建议：如果题目关键部分可以直接使用库函数解决，就不要使用库函数。

如果库函数只是解题过程中的一小部分，并且我们非常熟悉这个库函数的内部实现原理考虑使用库函数。

另外，在没事的时候，去看看常用字符串函数的实现，分析一下时间复杂度，有个大概印象。

#### 字符串编程题常用算法 ####

常见的问题有字符串查找、字符串反转等。

##### 双指针法 #####

双指针不隶属于任意一种数据结构，数组、链表、字符串中都有所使用

我们这里只说双指针在字符串编程题中的常见用法，至于其他的，我们再单独总结。

比如，在反转字符串中，我们使用了双指针，一首一尾，原地修改了完成了反转；

再比如，在替换空格中，我们使用了双指针，一新一旧（扩容后和扩容前），原地修改字符串完成了要求。

##### 反转系列 #####

对于字符串而言，反转不是一个问题，而是一类问题，在基本的问题上可以衍生出来一些类的问题。虽然这里我把它列到常用算法里了，但其实它并不能算是真正意义上的算法，只是我认为它出题的频率很高，我们可以把这个套路记住，当成一个模板而已。

比如，最基础的反转整个字符串，就是使用双指针，一首一尾将转成字符数组的字符串原地修改。

再比如，分组进行反转，我们的思路就时分组+反转，也就是在原来的基础上套上一个for循环，然后每次的Left和right的值进行特殊化处理，我们这里可以记住之前处理方式，一个就是i,另一个是选数组最大坐标和按照指定分组规则得到的下一组的right坐标，同时for循环每次的修改都是i+=2\*k。

总的来说，字符串的翻转系列相较于链表的翻转系列还是比较简单的。

##### KMP算法 #####

> KMP的主要思想是**当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。**
> 
> KMP的精髓所在就是前缀表，我们必须要弄清楚什么是KMP，什么是前缀表，以及为什么要用前缀表。
> 
> 那么使用KMP可以解决两类经典问题：
> 
> 1.  匹配问题
> 2.  重复子串问题
> 
> 再一次强调了什么是前缀，什么是后缀，什么又是最长相等前后缀。
> 
> 前缀：指不包含最后一个字符的所有以第一个字符开头的连续子串。
> 
> 后缀：指不包含第一个字符的所有以最后一个字符结尾的连续子串。
> 
> 然后**针对前缀表到底要不要减一，这其实是不同KMP实现的方式**，我们在中针对之前两个问题，分别给出了两个不同版本的的KMP实现。
> 
> 其中主要**理解j=next\[x\]这一步最为关键！**

### 四、双指针总结 ###

再次强调，双指针这种方法不属于任何一种数据结构专属的算法。一般而言，下边这几种数据结构都会经常用到双指针法，下边我们来总结一下用到双指针的常用场景。另外，我们再看几种会经常用到双指针的场景。

#### 数组篇 ####

首先，数组的指定元素的删除，若想要原地删除，双指针就是一个非常不错的方法。一新一旧，都从头部开始，遍历判断，一旦是目标值跳过，否则赋给新数组。[移除元素][Link 1]

其次，数组重复元素的删除，若想要原地删除，也可以使用双指针，一新一旧。[删除有序数组中的重复项][Link 2]

#### 链表篇 ####

首先，整个链表的反转，

其次，分组的反转，【这里我们为了提高效率，基本没有使用首尾双指针，而是使用的前后的双指针】

再有，相遇追及问题，环问题、倒数节点问题快慢指针。

这几种场景问题的我在前边有讨论过，不再赘述。

[环形链表系列][Link 3]

[倒数节点系列][Link 4]

[链表高频题1][1]

[链表高频题2][2]

#### 字符串篇 ####

首先，反转字符串

其次，字符串中指定字符的替换。

这两种类型上一篇blog已总结，包括本篇blog的第三部分也有部分总结，不再赘述。

#### N数之和 ####

两数之和

三数之和

四数之和

n数之和

下边的这两篇有涉及到或者类似的问题，注意区分什么时候使用双指针，什么使用哈希表。

[n=2][n_2]

[n>2][n_2 1]

*练习题目汇总（重点）*

> https://programmercarl.com/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.html
> 
> https://programmercarl.com/0344.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2.html
> 
> https://programmercarl.com/%E5%89%91%E6%8C%87Offer05.%E6%9B%BF%E6%8D%A2%E7%A9%BA%E6%A0%BC.html
> 
> https://programmercarl.com/0151.%E7%BF%BB%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2%E9%87%8C%E7%9A%84%E5%8D%95%E8%AF%8D.html
> 
> https://programmercarl.com/0206.%E7%BF%BB%E8%BD%AC%E9%93%BE%E8%A1%A8.html
> 
> https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html
> 
> https://programmercarl.com/0015.%E4%B8%89%E6%95%B0%E4%B9%8B%E5%92%8C.html
> 
> https://programmercarl.com/0018.%E5%9B%9B%E6%95%B0%E4%B9%8B%E5%92%8C.html

[Link 1]: https://leetcode.cn/problems/remove-element/
[Link 2]: https://leetcode.cn/problems/remove-duplicates-from-sorted-array/
[Link 3]: http://t.csdn.cn/3oVZI
[Link 4]: http://t.csdn.cn/W83yI
[1]: http://t.csdn.cn/JbuoE
[2]: http://t.csdn.cn/gTrtw
[n_2]: http://t.csdn.cn/GAsR0
[n_2 1]: http://t.csdn.cn/bNih1