代码随想录算法训练营第十天 | KMP算法 字符串总结 双指针回顾

简介: 代码随想录算法训练营第十天 | KMP算法 字符串总结 双指针回顾

前言

昨天没有更新训练营第九天内容,是因为昨天的任务是 LeetCode 28. 实现 strStr(),使用 KMP算法进行解答, 关于KMP算法可以查看我之前的文章 从 KMP算法到 Java的 String.indexOf(String str)方法, 今天还是关于 KMP算法的,但是主要是复习,想学习KMP算法相关的可以看我之前的文章

今日任务:

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等

总结

一转眼代码随想录训练营已经十天了,十天的进度:数组,链表,哈希表,字符串,按照语句训练营时长两个月一刷还有五十天,坚持就是胜利,日积硅步以致千里



目录
相关文章
|
17天前
|
算法 容器
【算法】——双指针算法合集(力扣)
移动零,复写零,快乐数,盛最多水的容器,有效三角形的个数,和为s的两个数(查找总价格为目标值的两个商品 ),三数之和,四数之和
|
3月前
|
算法
两个字符串匹配出最长公共子序列算法
本文介绍了最长公共子序列(LCS)问题的算法实现,通过动态规划方法求解两个字符串的最长公共子序列,并提供了具体的编程实现细节和示例。
113 1
两个字符串匹配出最长公共子序列算法
|
3月前
|
存储 搜索推荐 C语言
深入C语言指针,使代码更加灵活(二)
深入C语言指针,使代码更加灵活(二)
|
3月前
|
存储 程序员 编译器
深入C语言指针,使代码更加灵活(一)
深入C语言指针,使代码更加灵活(一)
|
3月前
|
C语言
深入C语言指针,使代码更加灵活(三)
深入C语言指针,使代码更加灵活(三)
深入C语言指针,使代码更加灵活(三)
|
3月前
|
算法
第四章 KMP算法理论基础
第四章 KMP算法理论基础
29 0
|
3月前
|
算法
KMP算法
KMP算法
50 0
|
3月前
|
算法 C++
【算法】双指针+二分(C/C++
【算法】双指针+二分(C/C++
|
6天前
|
算法 数据安全/隐私保护
室内障碍物射线追踪算法matlab模拟仿真
### 简介 本项目展示了室内障碍物射线追踪算法在无线通信中的应用。通过Matlab 2022a实现,包含完整程序运行效果(无水印),支持增加发射点和室内墙壁设置。核心代码配有详细中文注释及操作视频。该算法基于几何光学原理,模拟信号在复杂室内环境中的传播路径与强度,涵盖场景建模、射线发射、传播及接收点场强计算等步骤,为无线网络规划提供重要依据。