笔记：代码随想录

字符串

力扣

1.反转字符串

2.反转字符串

3.替换空格

4.翻转字符串里的单词

5.左旋转字符串

6.实现strStr()【KMP,匹配问题】

知识

KMP看家本领：当出现字符串不匹配时，可以记录一部分之前已经匹配的内容），利用这些信息避免从头匹配。

next数组：前缀表（也可以是前缀表统一减一。），记录下标i之前（包括i）的字符串中，有多大长度的前缀后缀。前缀表：用来回退，记录模式串与主串不匹配时，模式串应该从哪里开始重新匹配。

文本串和模式串：要在文本串：aabaabaafa 中查找是否出现过一个模式串：aabaaf。

求next数组

（1）初始化；（2）前后缀不相同；（3）前后缀相同；（4）next

j表示前缀末尾，i后缀末尾。

7.重复的子字符串【KMP，重复子串问题】

方法：移动匹配和KMP

栈与队列

概述

栈和队列是STL（C++标准库）里面的两个数据结构。

栈是以底层容器完成其所有工作，对外提供同一的接口，底层容器是可插拔的（也就是可以控制使用哪种容器来实现栈的功能，所以栈往往不被归类为容器，而被归类为容器适配器container adapter）。主要就是数组和链表的底层实现。默认是以deque缺省状况下栈的底层。

队列：先进先出

栈：后进后出

队列操作：push、pop、peek、empty 

力扣

1.用栈实现队列

2.用队列实现栈

3.有效的括号

括号匹配是用栈解决的经典问题。

4.删除字符串中所有相邻重复项

还是括号匹配。

5.逆波兰表达式求值

栈与递归某种程度上可以相互转换。逆波兰表达式是用后序遍历的方式把二叉树序列化了。平常看到的是中缀表达式，这个是后缀表达式，比较适合计算机。

6.滑动窗口最大值

单调队列的经典题目。使用deque(from collections import deque)，list会超时。

可以这么理解：pop()控制滑动窗口的后端，push控制滑动窗口的前端。pop在碰到不属于当前窗口的数值当然要弹出，push则负责排序。

7.前K个高频元素