\1…\9
\1…\9用来匹配与第n(1~9)个分组的内容，必须与()配合使用
例：在以下代码段中\2表示匹配第2个分组（一个括号代表一个分组）的内容，即\2匹配”world”字符串
import re
string = "helloworld world"
pattern = r'^(\w+)(world) \2$'
print(re.search(pattern, string))
python | re sub的使用方法
leetcode | 28.实现strStr()
28.实现strStr()
题目描述
实现 strStr() 函数。
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
题目链接
思路
直接调用python内置方法
暴力匹配
让字符串 needle 与字符串 haystack 的所有长度为 m（needle字符串的长度） 的子串均匹配一次。
为了减少不必要的匹配，我们每次匹配失败即立刻停止当前子串的匹配，对下一个子串继续匹配。如果当前子串匹配成功，我们返回当前子串的开始位置即可。如果所有子串都匹配失败，则返回 −1-1−1。
3.kmp算法
kmp算法的目的：为了避免不必要的指针回溯
主串指针i不回溯，模式串指针j的变化取决于模式串的结构是否有重复
pi数组值的计算：
pi数组的值为最长相同前后缀长度+1(串本身不能作为前后缀)
pi[1]=0,其他情况next[]=1.
leetcode | 496.下一个更大元素
496.下一个更大元素
题目描述
给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。
请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。
nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。
思路
1.暴力解法
对于每一个 nums1[i] 中的元素，先在 nums2 中找到它，然后向右遍历找到第 1 个大于 nums1[i] 的元素。
2.单调栈
步骤：
1）使用单调栈先对 nums2 中的每一个元素，求出它的右边第一个更大的元素；
2）将上一步的对应关系放入哈希表（HashMap）中；
3）再遍历数组 nums1，根据哈希表找出答案。
维护单调栈：
我们维护的栈恰好保证了单调性：栈中的元素从栈顶到栈底是单调不降的。
当我们遇到一个新的元素 nums2[i] 时，我们判断栈顶元素是否小于 nums2[i]，
如果是，那么栈顶元素的下一个更大元素即为 nums2[i]，我们将栈顶元素出栈。
重复这一操作，直到栈为空或者栈顶元素大于 nums2[i]。此时我们将 nums2[i] 入栈，
保持栈的单调性，并对接下来的 nums2[i + 1], nums2[i + 2] … 执行同样的操作。
leetcode | 237.删除链表中的节点
leetcode | 234.回文链表
leetcode | 232.用栈实现队列
232.用栈实现队列
题目描述
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：
你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
思路
使用两个栈实现队列，一个栈作为输入栈（入队），一个对作为输出栈（出队/取队头元素）。
入队操作的实现：将元素压入输入栈
出队操作的实现：弹出输出栈栈顶元素，若输出栈为空，输入栈不为空，则将输入栈所有元素出栈并压入输出栈，接着再弹出输出栈栈顶元素。
队列判空：输入栈和输出栈同时为空时队列为空。
leetcode | 255.用两个队列实现栈
225.用队列实现栈
题目描述
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
注意：
你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
思路
1.使用两个队列实现栈
使用两个队列实现栈的操作，其中 queue1 用于存储栈内的元素，queue2 作为入栈操作的辅助队列。
入栈操作时，首先将元素入队到 queue2，然后将 queue1 的全部元素依次出队并入队到 queue2，此时 queue2 的前端的元素即为新入栈的元素，再将 queue1 和 queue2 互换，则 queue1 的元素即为栈内的元素，queue1 的前端和后端分别对应栈顶和栈底。
由于每次入栈操作都确保 queue1 的前端元素为栈顶元素，因此出栈操作和获得栈顶元素操作都可以简单实现。出栈操作只需要移除 queue1 的前端元素并返回即可，获得栈顶元素操作只需要获得 queue1 的前端元素并返回即可（不移除元素）。
由于 queue1 用于存储栈内的元素，判断栈是否为空时，只需要判断 queue1 是否为空即可。
2.使用一个队列实现栈
使用一个队列时，为了满足栈的特性，即最后入栈的元素最先出栈，同样需要满足队列前端的元素是最后入栈的元素。
入栈操作时，首先获得入栈前的元素个数 n，然后将元素入队到队列，再将队列中的前 n 个元素（即除了新入栈的元素之外的全部元素）依次出队并入队到队列，此时队列的前端的元素即为新入栈的元素，且队列的前端和后端分别对应栈顶和栈底。
由于每次入栈操作都确保队列的前端元素为栈顶元素，因此出栈操作和获得栈顶元素操作都可以简单实现。出栈操作只需要移除队列的前端元素并返回即可，获得栈顶元素操作只需要获得队列的前端元素并返回即可（不移除元素）。
由于队列用于存储栈内的元素，判断栈是否为空时，只需要判断队列是否为空即可。
leetcode | 206.反转链表
206.反转链表
题目描述
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
思路
1.递归
递：将大问题分解为小问题，将整个链表依次拆解直到只剩下一个节点
归：在链表只剩下一个节点时开始”归“，使用head.next.next = head,head.next = None这两行代码从后往前（从原链表的视角看）将链表中的每一个连接改为反向的
2.迭代
假设链表为 1→2→3→∅，我们想要把它改成 ∅←1←2←3。
在遍历链表时，将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。
3.头插法
首先创建一个只有头节点的反转链表，从头到尾遍历原链表，将每次遍历到的节点按照头插法插入反转链表中，以此类推，当我们遍历完整个链表时就得到一个反转链表。
头插法：即每次都将将要插入的节点作为链表的首节点（不是头节点）
头插法代码实现：
node.next = head.next
head.next = node
leetcode | 203.删除链表元素
203.删除链表元素
题目描述
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
思路
1.递归
链表的定义具有递归的性质，因此链表题目常可以用递归的方法求解。
对于给定的链表，首先对除了头节点 head 以外的节点进行删除操作，然后判断 head 的节点值是否等于给定的 val。如果 head 的节点值等于 val，则 head 需要被删除，因此删除操作后的头节点为 head.next；如果 head 的节点值不等于 val，则 head\ 保留，因此删除操作后的头节点还是 head。
递归的终止条件是 head 为空，此时直接返回 head。当 head 不为空时，递归地进行删除操作，然后判断 head 的节点值是否等于 val 并决定是否要删除 head。
2.迭代
用 temp 表示当前节点。如果 temp 的下一个节点不为空且下一个节点的节点值等于给定的 val，则需要删除下一个节点。删除下一个节点可以通过以下做法实现：
temp.next=temp.next.next
如果 temp 的下一个节点的节点值不等于给定的 val，则保留下一个节点，将 temp 移动到下一个节点即可。
当 temp 的下一个节点为空时，链表遍历结束，此时所有节点值等于 val 的节点都被删除。
具体实现方面，由于链表的头节点 head 有可能需要被删除，因此创建哑节点 dummyHead，令 dummyHead.next=head，初始化 temp=dummyHead，然后遍历链表进行删除操作。最终返回 dummyHead.next 即为删除操作后的头节点。