【代码随想录算法训练营Day09】28.实现 strStr(); 459.重复的子字符串

本文主要是介绍【代码随想录算法训练营Day09】28.实现 strStr(); 459.重复的子字符串,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • Day 9 第四章 字符串part02
    • 28. 实现 strStr() (本题可以跳过)
      • KMP 思路
      • KMP 代码
    • 459.重复的子字符串 (本题可以跳过)
    • 字符串总结
    • 双指针回顾

Day 9 第四章 字符串part02

  • 今日任务
    • 28.实现 strStr(); 459.重复的子字符串; 字符串总结; 双指针回顾

28. 实现 strStr() (本题可以跳过)

  • 因为KMP算法很难,大家别奢求 一次就把kmp全理解了,大家刚学KMP一定会有各种各样的疑问,先留着,别期望立刻啃明白,第一遍了解大概思路,二刷的时候,再看KMP会
    好懂很多。
  • 或者说大家可以放弃一刷可以不看KMP,今天来回顾一下之前的算法题目就可以。
  • 因为大家 算法能力还没到,细扣 很难的算法,会把自己绕进去,就算别人给解释,只会激发出更多的问题和疑惑。所以大家先了解大体过程,知道这么回事, 等自己有
    算法基础和思维了,在看多看几遍视频,慢慢就理解了。
  • 题目链接:https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/
  • 视频讲解:1. 帮你把KMP算法学个通透!(理论篇); 2. 帮你把KMP算法学个通透!(求next数组代码篇)_哔哩哔哩_bilibili
  • 文章讲解:https://programmercarl.com/0028.%E5%AE%9E%E7%8E%B0strStr.html
  • 参考视频:https://b23.tv/2Px1QbL

KMP 思路

KMP 代码

public static int strStr(String haystack, String needle) {char origin[] = haystack.toCharArray(); //原始数组char pattern[] = needle.toCharArray();  //模式数组int next[] = next(pattern); //最长前后缀数组//System.out.println(Arrays.toString(next));/*1. 匹配成功,i++ j++,直到j==模式字符串长度2. 匹配失败j != 0 跳过最长前后缀字符,继续匹配j == 0 则 i++*/int i = 0;int j = 0;//没匹配到就一直匹配,直到模式字符串尾部和原始字符串对齐while(pattern.length - j <= origin.length - i){if(origin[i] == pattern[j]){    //匹配成功的情况i ++;j ++;} else if (j == 0) {i++;} else{j = next[j - 1];}//找到解if(j == pattern.length) return i - j;}return -1;
}/*最长前后缀数组:只跟模式字符串有关1. 索引:使用了模式字符串前j个字符串-12。 值:最长前后缀的长度(恰好是匹配失败时j要跳转的位置)*/
public static int[] next(char[] pattern){//return new int[]{0,0,1,2,3,0,1};int next[] = new int[pattern.length];int i = 1;int j = 0;/*遇到相同的字符:记录共同前后缀长度,长度即为 j + 1长度记录至数组i索引处然后i++ j++遇到不同字符:1. 前面没有共同部分:j=02. 前面有共同部分,j向回找无需对比的地方,可以跳过无需对比的字符串个数之前已经计算过*/while(i < pattern.length){if(pattern[i] == pattern[j]){next[i] = j + 1;i ++;j ++;}else if(j == 0){i ++;}else{j = next[j - 1];}}return next;
}

459.重复的子字符串 (本题可以跳过)

  • 本题算是KMP算法的一个应用,不过 对KMP了解不够熟练的话,理解本题就难很多。
  • 我的建议是 KMP和本题,一刷的时候 ,可以适当放过,了解怎么回事就行,二刷的时候再来硬啃
  • 题目链接:https://leetcode.cn/problems/repeated-substring-pattern/
  • 视频讲解:https://www.bilibili.com/video/BV1cg41127fw/
  • 文章讲解: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

这篇关于【代码随想录算法训练营Day09】28.实现 strStr(); 459.重复的子字符串的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/737225

相关文章

Spring Security+JWT如何实现前后端分离权限控制

《SpringSecurity+JWT如何实现前后端分离权限控制》本篇将手把手教你用SpringSecurity+JWT搭建一套完整的登录认证与权限控制体系,具有很好的参考价值,希望对大家... 目录Spring Security+JWT实现前后端分离权限控制实战一、为什么要用 JWT?二、JWT 基本结构

Java实现优雅日期处理的方案详解

《Java实现优雅日期处理的方案详解》在我们的日常工作中,需要经常处理各种格式,各种类似的的日期或者时间,下面我们就来看看如何使用java处理这样的日期问题吧,感兴趣的小伙伴可以跟随小编一起学习一下... 目录前言一、日期的坑1.1 日期格式化陷阱1.2 时区转换二、优雅方案的进阶之路2.1 线程安全重构2

Android实现两台手机屏幕共享和远程控制功能

《Android实现两台手机屏幕共享和远程控制功能》在远程协助、在线教学、技术支持等多种场景下,实时获得另一部移动设备的屏幕画面,并对其进行操作,具有极高的应用价值,本项目旨在实现两台Android手... 目录一、项目概述二、相关知识2.1 MediaProjection API2.2 Socket 网络

使用Python实现图像LBP特征提取的操作方法

《使用Python实现图像LBP特征提取的操作方法》LBP特征叫做局部二值模式,常用于纹理特征提取,并在纹理分类中具有较强的区分能力,本文给大家介绍了如何使用Python实现图像LBP特征提取的操作方... 目录一、LBP特征介绍二、LBP特征描述三、一些改进版本的LBP1.圆形LBP算子2.旋转不变的LB

Redis消息队列实现异步秒杀功能

《Redis消息队列实现异步秒杀功能》在高并发场景下,为了提高秒杀业务的性能,可将部分工作交给Redis处理,并通过异步方式执行,Redis提供了多种数据结构来实现消息队列,总结三种,本文详细介绍Re... 目录1 Redis消息队列1.1 List 结构1.2 Pub/Sub 模式1.3 Stream 结

C# Where 泛型约束的实现

《C#Where泛型约束的实现》本文主要介绍了C#Where泛型约束的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录使用的对象约束分类where T : structwhere T : classwhere T : ne

将Java程序打包成EXE文件的实现方式

《将Java程序打包成EXE文件的实现方式》:本文主要介绍将Java程序打包成EXE文件的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录如何将Java程序编程打包成EXE文件1.准备Java程序2.生成JAR包3.选择并安装打包工具4.配置Launch4

MySQL索引的优化之LIKE模糊查询功能实现

《MySQL索引的优化之LIKE模糊查询功能实现》:本文主要介绍MySQL索引的优化之LIKE模糊查询功能实现,本文通过示例代码给大家介绍的非常详细,感兴趣的朋友一起看看吧... 目录一、前缀匹配优化二、后缀匹配优化三、中间匹配优化四、覆盖索引优化五、减少查询范围六、避免通配符开头七、使用外部搜索引擎八、分

Python实现特殊字符判断并去掉非字母和数字的特殊字符

《Python实现特殊字符判断并去掉非字母和数字的特殊字符》在Python中,可以通过多种方法来判断字符串中是否包含非字母、数字的特殊字符,并将这些特殊字符去掉,本文为大家整理了一些常用的,希望对大家... 目录1. 使用正则表达式判断字符串中是否包含特殊字符去掉字符串中的特殊字符2. 使用 str.isa

Spring Boot 集成 Quartz并使用Cron 表达式实现定时任务

《SpringBoot集成Quartz并使用Cron表达式实现定时任务》本篇文章介绍了如何在SpringBoot中集成Quartz进行定时任务调度,并通过Cron表达式控制任务... 目录前言1. 添加 Quartz 依赖2. 创建 Quartz 任务3. 配置 Quartz 任务调度4. 启动 Sprin