【刷题DAY09】28, 459, 字符串总结, 双指针回顾.md

发表于 | 分类于 ， ，

28. 找出字符串中第一个匹配项的下标

题目链接：https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string

0x1 看到题目的第一想法

  • KMP

0x2 自己实现过程中遇到哪些困难

  • 啥都不会

0x3 今日学习的文章链接，或者视频链接

0x4 看完代码随想录之后的想法

  • 一次看不懂，多看几遍，理解一下Next数组的构造

0x5 今日收获，记录一下自己的学习时长

  • 字符串匹配
    • KMP
      • 当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了
    • 利用主字符串和匹配字符串做匹配
    • Next数组的构造是用匹配字符串自己和自己做匹配
    • 好好体会Next数组的构造，Next[x]的定义！Next[x]的定义！！Next[x]的定义！！！
      1
      2
      # 利用下面这个语句进行回退，注意回退的时候now不能退到0
      now = Next[now-1]
  • 2h

459. 重复的子字符串

题目链接：https://leetcode.cn/problems/repeated-substring-pattern/

0x1 看到题目的第一想法

  • 利用KMP中的Next进行求解

0x2 自己实现过程中遇到哪些困难

  • 最后的if判断找Next规律找错了

0x3 今日学习的文章链接，或者视频链接

0x4 看完代码随想录之后的想法

  • 找规律
    1
    2
    3
    4
    s = "abcabcabcabc"
    Next = [0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    if(Next[-1] > 0 and Next[-1] % (n - Next[-1]) == 0):
         return True

0x5 今日收获，记录一下自己的学习时长

  • python最后一个元素可以用nums[-1]索引到
  • 45min

待重点复习

ALL

总结