刷题笔记day9

KMP算法

文章讲解：代码随想录
是否自己做出来通过全部用例：否

看了题解后的收获

大致浏览了一下，以后有时间再回来啃这道题。

字符串总结

文章讲解：代码随想录

看了总结后的收获

回顾双指针法/局部反转+整体反转实现反转字符串操作。

双指针回顾

文章讲解：代码随想录

看了回顾后的收获

  • 通过两个指针在一个for循环下完成两个for循环的工作。
  • 很多数组（字符串）填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。
  • 不要随便用erase()，其时间复杂度为O(n)。
  • 反转链表：只需要改变链表的next指针的指向，直接将链表反转 ，而不用重新定义一个新的链表。
  • 环形链表：使用快慢指针（双指针法），分别定义fast和slow指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果fast和slow指针在途中相遇，说明这个链表有环。
  • 三数、四数之和：使用双指针法比哈希法更容易。

总结：除了链表一些题目一定要使用双指针，其他题目都是使用双指针来提高效率，一般是将O(n^2)的时间复杂度，降为O(n)。