Everyday sentence

11-29: I don’t like rasins. They used to be fat and jucy, and now they are twisted. They had their lives stolen. They taste sweet, but really they are humiliated grapes.

12-1: We all fear death and question our place in the universe. The artist’s job is not to succumb to despair, but to find an antidote for the emptiness of existence.

12-2: You know the only thing that has made the whole thing worthwhile…has been those… few times that I’ve been able to really, truly connect with another human being.

12-3: We are made of dreams, and dreams are made of us.

12-5: Funny, how just when you think life can’t possibly get any worse it suddenly does.

12-6: 美丽的梭罗河/ 我为你歌唱 / 你的光荣历史 / 我永远记在心上 / 旱季来临 / 你轻轻流淌 / 雨季时波涛滚滚 / 你流向远方

开篇词

算法万变不离其宗，为了帮大家更好地建立知识体系，也为了自己更好地回顾，在本篇中总结一下medium及以上一些比较有代表性的思路

快速排序和快速选择排序

都是基于分治的思想

快排一般是选左边的数low作为基准数，然后从表的最右边放一个哨兵开始向左搜索，找到第一个小于基准数的记录，并将其的值赋给low，然后从左侧开始向右搜索，找到第一个大于基准数的记录，把其值赋给right，然后再交替搜索，直到指针相遇，把基准数的值赋给这个指针的位置，这样就以pivot为标准完成了一次划分，依次对左右进行递归即可

后来我又看见了一种新的思路去做，该思路是随机选择一个主元，然后把它放在最右边。定义两个指针 i 和 index，一开始 i = l ，index = l。for循环移动 i , 如果 i 上的值比主元要小，就交换index和 i ，并且index += 1。当 i 移动到 r - 1的时候终止。交换 index 和 r 即可完成一次划分

在主sort函数里面把 r <= l 的情况return掉，然后根据partition得到mid，分别对左右两块进行递归

快速选择是为了找到第K大的数的一种更高效的算法，它可以不用保证主元左右两边有序，一次主元划分结束后比较k和主元的位置，有选择地对左边或者右边递归。一般分为select函数，和一个内部的partition函数。partition是一个用于找主元位置的函数，select用二分的思想并进行剪枝，只需要一半的计算量，另外在主元的选择上多了一步随机选择

BFPRT算法

这是更高级的算法，通过n/mod 5，向下取整分组，每组中五个元素，每个组的中位数可以用插入排序得到。通常被分为partition函数，pivot_median函数，bfprt函数。思想是用组中中位数的中位数作为pivot来划分。经过数学证明在top k问题上有线性的复杂度

堆排序

构建大根堆，使得父元素的节点大于等于它的子节点。我们将堆顶最大的元素与末尾元素进行交换，通过调整堆顶元素使得剩下的n - 1个元素仍为大根堆，重复执行以上的操作就可以得到一个有序序列

归并排序

二分序列，对左右分别进行排序，然后最后线性归并，用两个指针分别指示两个序列中归并到哪一位了

合并k个有序链表

最朴素的想法就是循环两两合并

进一步优化可以写成分治归并的格式，二分的方法去归约。先写一个函数，一半一半地处理成排序链表，然后进行合并，合并的时候就是两个链表的合并，这里可以继续用递归的方法，复用merge函数，最后返回较小一半的头指针

直接多路合并，在选取每次当前最小的元素的时候用优先队列，本质就是上面讲过的堆排序。堆有两种创建方法，一种是使用一个空列表，然后使用heapq.heappush()函数把值加入堆中，另外一种就是使用heap.heapify(list)转换列表成为堆结构。初始化的时候把链表的首元素的值（不是节点）都放进head堆中，while head堆不为空的时候，每次pop一个元素，在入堆的时候入一个元组，不仅把当前结点的值加进去，还要把当前结点是第几个链表标记一下，以便每个链表中的移位

待做的题目

最小窗口子序列，找迷宫中的最小路径

卡特兰数

2n个人围城一圈,两两握手,没有交叉，问有多少种方式：第一个人可以和偶数的人握手，h(n) 定义为2n个人的方式次数，h(0) = 1, h(1) = 1, h(n) = h(0) * h(n -1) + …. h(n-1)h(0)

C(n,2n)/(n+1) = C(n,2n) - C(n+1,2n) = (4n-2)*h(n-1)/(n+1)

= (2n!) / (n! * n!) / (n + 1)

一堆数入出栈序列的组合数，小兔的棋盘（从00到nn不越过对角线的走法），可以转换成序列任务。组合数把入栈看作1出栈看作0，棋盘问题把往右走看作1，往上走看作0，依然是0的个数在任意长度不能超过1的个数

类似的问题还有n个结点构造二叉树种类。也是用递归的方式，N种选根的办法

10个高矮不同的人，排成两排，每排必须是从矮到高排列，而且第二排比对应的第一排的人高，问有多少种排列方式。把人从矮到高排，用等长的数列代表排法，0代表放在第1排，1代表第2排

n对括号正确匹配成的字符串数

n+1个数相乘，所有的括号方案数

n+2条边的多边形，能被分割成三角形的方案数，用递归的思想去想，连接一条边之后分成两个多边形，因为一条边有两个点，所以结果需要除2

平衡二叉树（AVL）

它是一种二叉排序树，是指一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是平衡二叉树，常用红黑树来实现。F(n)=F(n-1)+F(n-2)+1 ，是在对一棵查找树能进行增删查的工作的时候仍然保持好身材，使得所花时间与logn成比例。

将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF，那么平衡二叉树上的所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。 距离插入结点最近的，且平衡因子的绝对值大于1的结点为根的子树，称为最小不平衡子树。

平衡二叉树构建的基本思想就是在构建二叉排序树的过程中，每当插入一个结点时，先检查是否因插入而破坏了树的平衡性，若是，则找出最小不平衡子树。在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。常见的有LL，RR，LR，RL调整

红黑树

jdk1.8以后的hashmap是用红黑树来实现的，但我并不会java（逃）

红黑树是一种自平衡的二叉树，在插入和删除的过程中会采取一定的策略对树的组织形式进行调整，以尽可能减少树的高度来减少查找时间。特点是结点为红/黑，根节点始终是黑色，叶子（要挂上满的NIL）结点也是黑色，红色结点的两个直接孩子为黑，任意结点到每个叶子的所有简单路径都包含相同数量的黑色结点。这样可以保证在满足平衡二叉树的前提下，根到叶子结点的最长路径不会超过最短路径的两倍。平衡策略包括左旋，右旋，变色。这里和平衡二叉树不同的是它的旋转定义是按照作用结点来旋转的。

约定新插入的结点为红色，策略如下：

删除策略，执行前先判断删除结点有几个孩子结点，如果是两个的话我们需要从左子树上寻找值最大的，或右子树寻找值最小的，用结点值替换掉删除结点的值，替换成只有一个孩子结点的删除情况：

结论：在相同的节点情况下，AVL树的高度低于红黑树，但相对于要求严格的AVL树来说，它的旋转次数少，所以对于搜索，插入，删除操作较多的情况下，红黑树更高效一些

LFU缓存机制

需要创造一个链表节点类，节点需要包含前后节点信息，节点的频数信息，其key和val的信息。用一个keymap的字典来哈希存储key对应的节点信息。然后再构造一个freqMap的哈希表，对每个频数上都初始化一个有头尾节点的双向链表。在LFU类中还需要有保存此时size的变量，capacity的变量和此时最小频数的变量

约瑟夫环

N个人围成一圈，第一个人从1开始报数，报M的将被杀掉，下一个人接着从1开始报。如此反复，最后剩下一个，求最后的胜利者

很神奇的是，如果反推，只需要把杀死的那个人加在最后面，然后右移M位，把溢出的部分顺序放在最前面，就还原了之前的序列

编程的时候，可以用递归的思想去理解，最后一个人的下标一定为0

atoi函数，自动机

DFA（有限状态机），关键是建立一个状态跳转的表格，根据上一个状态和当前字符来根据表格更新当前状态，一般建一个新的类来维护里面的变量，这样写出来的代码比较全面而且不会太臃肿

动态规划求解编辑距离

一看到题目就觉得应该是动态规划，困难题肯定不是一维，那么最自然的就是定义word1中的前i个子串和word2中的前j个子串为dp[i][j]

对于增删改三种操作，要意识到顺序是无所谓的

在有一个是空串的时候，边界上的距离就是另一个非空串的长度

在更新的时候判断当前末位置是否相等，然后注意下标和dp中下标的对应含义，很快就能写出代码来

python输入输出常用的函数

sys.stdin.readline()不会把字符串末尾的/n去掉，所以一般后面会加上strip()函数，内参数是需要去除的东西，默认为空格，去两头。等效于input()，如果是整型之类的外面再强制转化一下就可以，如果字符串需要分割再转型，就用lines = line.split()割成列表，然后用lines = list(map(int, lines))

多行输入和需要循环读入的时候：可以while True然后try except

try:
    while(True):
        row = int(input())
        lines_multrows = []
        for n in range(row):    
            line = input()
            if line=='': # (if not line 也可以)
                break
        lines = line.split()
        lines = list(map(int,lines))
        lines_multrows.append(lines) #多行数组
except:
      pass

join函数也挺常用的，”用什么连接”.join(seq_list)。输出的时候如果需要换行则直接循环print()，如果单行输出则使用print(xx, end = “ “)

%o八进制，%d十进制，%x十六进制

%.3f，3位小数，f表示浮点形式输出，默认六位

%e，科学计数法输出，默认六位

字符串输出%10.2s，占位10右对齐，-10就是左对齐，点2还是取几位的意思

更高阶的输出可以用format，”{} {}”.format(“”,””)，{}里可以带index或者关键字，还有很多新用法，不展开了

旋转矩阵

如果新开一个数组，找到角标之间的关系不难。如果要求原地，那么有两种方法，第一种推导的成分比较多一些，就是发现每4个循环又会回到原地，所以用一个tmp变量就可以把四个角换过来，再思考一下需要交换的元素循环起止位置（分奇偶的情况进行思考）。

还有一种比较难理解，但是很容易写，顺时针旋转90度就相当于先上下翻转，然后沿顺对角线翻转

DFS和BFS

网格上的题目基本都是用遍历求解的，dfs可以用来计数，不满足条件的时候return 0，满足的时候return 1 + dfs。bfs是用一个队列非空的时候做一些操作。set可以用来装不重复的答案值，涉及坐标的时候可以打包成元组存储

递归问题

要善于发现问题中与原问题拥有相同子结构的子问题，递归中为了提高效率会进行回溯和减枝，本质就是DFS/BFS，更容易理解一点。也可以转化为动态规划的问题。

扔鸡蛋问题

很经典的大厂编程题，N表示有几层楼，K表示有几个鸡蛋，我们要找到鸡蛋恰好摔不碎的楼层所需要的最少移动次数。是具有相当难度的动态规划问题

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        memo = dict()
        def dp(K, N):
            # base case
            if K == 1:
                # 只有一个鸡蛋了，这时候只能扫完N层
                return N
            if N == 0:
                # 搜索区间为空，那这次递归不需要计次
                return 0
            res = float("inf")
            # 查一下是不是已经算过了
            if (K,N) in memo:
                return memo[(K,N)]
            for i in range(1,N+1):
                # 我们考虑最坏情况，所以应该选分类中较大的return
                res = min(res, max(dp(K-1,i-1),dp(K,N-i))+1)
            # 加到备忘录里
            memo[(K,N)] = res
            return res
        return dp(K,N)

如果在第i层扔了，鸡蛋碎了，那么在1到 i-1 层楼搜索，状态变为dp（K-1，i-1）。如果鸡蛋碎了，那么在 i+1层到N层， 到dp（K，N-i ）

为了提升效率，可以加上一个备忘录。

但尽管如此，时间复杂度还是很高，时间复杂度是KN*N。我们还可以进一步优化，把dp中的那个N循环用二分查找的方法搜索优化为logn。

进一步优化可以修改状态的定义，

dp[k][m] = n
# 当前有 k 个鸡蛋，可以尝试扔 m 次鸡蛋
# 这个状态下，最坏情况下最多能确切测试一栋 n 层的楼
# 转移方程，鸡蛋没碎测楼上层数，鸡蛋碎了测楼下层数，再加上当前层数
dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1

接着就是填表了，如果单纯正向填表的话也挺慢的，但是因为我们需要返回的是符合dp[K] [ j ]大于等于N的最小 j 。所以我们可以竖着填表，这样可以把时间复杂度降低为KN，速度实测提升接近十倍。

更加牛逼的，如果我们用一维数组去更新的话，我们会发现，每一个状态与他左边和左上的状态有关，所以我们实际上更快的是倒着填表。这样又能在前面的基础上再提升三倍。

最后的最后，更骚的还可以在m的搜索上用上二分查找，把时间复杂度进一步降低为K * logN

光影切割问题中的逆序数求解

在光影切割问题中除了直接去求解直线交点是否在区间内，还可以用一种很聪明的办法去看边界交点是否逆序来得到交点的数目。

逆序数对求解用归并排序，特别需要注意的是，在归并统计count的时候应该选取一边数组进行统计就可以了，比如只在左边数组归并操作的时候更新count或者右边数组归并的时候更新，不然就容易出现重复计数的情况

还有一种方法使用树状数组，这是一种动态维护序列前缀和的数据结构

树状数组

有一个数组，如果我们需要多次查询前i项和，而这个数组又是动态的，那么这时候最方便的方法就是树状数组

lowbit是与负的自己取与，只保留从低位向高位数，第一个数字1

编号为x的结点上统计着[x−lowbit(x)+1,x]这一段区间的信息，x的父亲就是x+lowbit(x)

求最大值任务就在每个位置比较max

基础版本的是单点修改+区间查询

升级：区间修改+单点查询，这时候构造一个差分数组，这样在更改的时候就只要修改两个端点的值就可以了，而且单点查询就变成了求前缀和的形式。

区间修改+区间查询：写出差分形式下的公式可知，假设差分数组为c，我们需要再构造一个c1[ i ] = i *c[ i ]，结果就是 (p + 1) * c数组中p位置的前缀和 - c1数组中p位置的前缀和

二维树状数组

类似地定义tree[x][y]记录的是右下角为(x, y)，高为lowbit(x), 宽为 lowbit(y)的区间的区间和

区间修改，单点查询的时候仍然运用差分思想，矩阵面积计算推出来的公式，构造差分数组d[ i ] [ j ] 表示 𝑎[ i ][ j ]与 𝑎[ i-1 ][ j ]+ 𝑎[ i ][ j-1 ]− 𝑎[ i-1 ][ j-1 ]的差。此时区间修改变成：

add(xa, ya, z);   
add(xa, yb + 1, -z);   
add(xb + 1, ya, -z);  
add(xb + 1, yb + 1, z);

如果是多点查询，我们通过推导可知，除了差分数组d之外，还需要同时维护三个额外的数组，d[ i ] [ j ] * i，d[ i ] [ j ] * j ，d[ i ] [ j ] * i * j，记做d2，d3，d4

最后的结果是 (x + 1) * (y + 1) * d数组在x，y处的前缀和 - (y + 1) * d2前缀和 - (x + 1) * d3前缀和 + d4前缀和

针对逆序数问题的树状数组

做对数字做离散化，离散化指的是不关心确切值，只是看元素的相对大小关系，以节省树状数组空间。可以用sort + bisect模块，里面有bisect和insort两类函数，参数为(array, x, lo, hi)，bisect返回x在array排序后的应该存在的位置，insort是插入操作。后面接的left和right是在x已经存在于array中的时候的处理策略，表示插入在重复值的左边还是右边。也可以对元素做set，然后对set来heapify获得排序，最后创建一个rank_map = dict()来存储num和rank之间的关系(也就是辅助数组C)。

创建一个BIT类，类内init创建一个辅助的树状数组，初始化全0，query用来自上而下获取前缀和，索引顺序是慢慢往下走lowbit位。update用来自下而上更新树状数组，索引顺序是不超过元素个数的情况下慢慢往上走lowbit位。

为了解决这个逆序对的问题，遍历数组的时候从后往前统计，update中遇到这个数的时候加1。query得到的是原数组到query的前缀和，在右更新且query值为rank-1的的情况下就代表着右边比他小的数字的个数，也就是对逆序对的贡献值。

前缀和

如果前缀和不是动态的，而是固定的。我们可以创建一个前缀和数组，对于带index的问题，我们也可以简单地用字典（也就是哈希表）来存当前前缀和的个数

逆序问题的延伸，右侧比当前小的个数数组

这个问题和逆序问题其实本质是一样的，在写归并思路代码的时候，由于要记录排序后数字的原位置，所以需要一个index数组来同步变换，在归并的时候需要将index和nums都copy一份，nums的copy用来进行比较，index的copy用来进行索引。

值得体会的是，首先在函数调用中传入有些全局参数可以降低一部分的运行时间。其次，在copy的时候不是简单的引用拷贝，因为对象是数组，所以需要逐元素复制，这时候在归并函数的步骤里只拷贝left到right就足够了，相比于整份拷贝可以节省大量的时间，但在函数中的索引相应地就需要减去left的大小来保证不越界。

线段树

树状数组是线段树的子集，线段树更厉害，它不仅可以维护前缀和，还可以维护区间操作和。在树状数组上对于存在逆元的操作上可以用两次操作和询问的方法来实现区间查询，但是对于某些特殊的运算，比如最大最小值，模非质数就不可以了。

线段树的典型应用是RMQ问题（Range Minimum Query）

寻找01矩阵中1离最近0的距离

首先，因为是在1上面的位置显示距离，而我们的搜索算法基本上是在终点位置返回，所以需要反着思考，把起点从0开始搜索

第一种想法是用BFS，0元素全部入队，用一个set来表示是否被访问过。第二种想法是用动态规划，因为两点之间的距离要最短只会包含两种状态（左上，左下，右上和右下），分别用动态规划的思想去填表，要注意填表的起点会随着方向的不同而变化（其实只需要左上和右下两次遍历就可以了）

一手顺子

输入：hand = [1,2,3,6,2,3,4,7,8], W = 3 输出：true 解释：手牌可以被重新排列为 [1,2,3]，[2,3,4]，[6,7,8]。

需要用到count函数，一种想法是用while循环，从最小的count开始不断在顺子上都减1，如果中途发现顺子断了就return False，如果能用完所有的count就return True

还有一种方法是把count之后的字典排序，然后遍历字典，在顺子循环中可以一次减去多张牌，如果此时键不存在返回false，如果此时的count是0就continue下一个count

简单顺子

给一串数字，判断是否为顺子，0表示大小王可以代替任何数字

有两种思路，首先这些牌里除了0不能有重复的数字，然后这里面最大的数字减去最小的数字（不考虑大小王）加1应该等于牌的数量

还有一种思路是进行排序，然后用大小王去填补中间有空缺的数列，看看大小王的数量是不是能填补这些空缺

扑克牌（2020 阿里笔试：最少出牌次数）

一行是个空格分隔的整数A1,A2,…A10,分别代表牌为A,2,…,10的个数. 可以打单牌，对子，顺子，三对，输出打完所有牌的最少次数

统计重复个数（找循环节）

通过两层循环储存所有匹配终末位置，最后再数结尾标志符的个数

岛屿数量

挺经典的，刷了好几遍了，1是陆地0是水，输出岛屿的个数。有三种思路，BFS，DFS和并查集。遍历的思想是循环遍历每一个元素，如果是陆地就把岛屿数量加一并从它开始向四个方向探索，探索过之后就把这个位置当作海洋。

并查集的思想很容易理解，写法上用一个字典实现，对每一个unique的键值，存储它的父节点。主要分为两个函数，union(x,y)实现的是树的根合并。find(x)的作用是找到x元素的根结点，并且做一个压缩路径(相当于把根节点路径上的所有元素都直接连到根节点上，可以节省很多时间)，把字典里的父结点直接连到根节点上。这题里位置可以用index来指示。 ## 遍历的时候有个优化，可以只搜索一半的方向

全排列的个数

用递归不难分离子问题，有一个取巧的做法用库函数itertools.permutations(nums)

回溯问题其实就是多叉决策树遍历的过程，在前序遍历和后序遍历的位置做一些操作。通用的算法框架是在算法中先写结束的触发条件，然后遍历排除不合法的行为（剪枝），递归，最后撤销选择。但回溯算法其实就像是纯暴力枚举，复杂度一般都很高

著名的N皇后问题也是通过回溯算法解的

背包问题

01背包，完全背包，多重背包，混合背包，二维费用的背包，分组背包，背包问题求方案数，求方案，有依赖的背包问题。

f[ i ] [ j ] 表示只看前i个物品，总体积是 j 的情况下，最大价值是多少。循环的时候可以优化空间到一维，如果求解的是体积恰好为m的情况，这时候需要 f[ i ]的初始化不能为0，需要把除了f [ 0 ]之外的值都设为负无穷，然后最后也是需要枚举求最大值。

完全背包本来需要在内层体积的循环下再套一层k循环，但是可以优化成从小到大枚举，这样可以考虑 i 物品的叠加

多重背包是01背包的扩展，内循环还是从大到小更新，里面再加一层数量的循环更新，这里还要注意当选的物品个数合法但是超过了当前的容量的时候，break掉。可以进一步优化，把数目进行二进制拆分（1，2，4，8可以表示0-15的数）（如果10，可以拆成1，2，4，3。3是从10-7得来的）这样我们可以把物品分成logn份，然后再做01背包遍历goods

class Vec:
    def __init__(self,v,w):
        self.v = v
        self.w = w

goods = []
for i in range(N):
    line = list(map(int,input().split()))
    v,w,n = line[0],line[1],line[2]
    k = 1
    while(k<=n):
        n -= k
        goods.append(Vec(k*v,k*w))
        k *= 2
    if n > 0:
        goods.append(Vec(n*v,n*w))

还可以究极版优化，

二维费用背包

滑动窗口的最大值

是一道经典的单调队列的问题

前缀树，字典树

快速幂

可以从二进制角度和二分角度理解，分别对应着非递归（迭代）和递归的写法。二进制角度就是用数字的二进制来表示十进制，展开之后就变成logn个数相乘，然后循环计算就可以了。二分角度把n分为奇数和偶数情况，分别用x的平方和x平方多一个x来进行拆分。右移操作也就是相当于向下取整

丑数：优先队列

挥剑世无双

27/67 两个集合间的最短距离 山脉数组查找目标值

待深挖

高阶跳跃游戏，子树，KMP算法解，无限深二叉树x在深度为k的祖先

整数中1出现的次数

x的平方根

法1:数学方法用指数函数和对数函数通过换底公式代替平方根函数，由于计算机无法存储浮点数的精确值，所以最后取结果的时候应同时判断ans和ans+1。

法2:二分查找

法3:通过移项来构造一个函数求零点的问题，然后用牛顿迭代法，取初始为C，写出迭代x的公式，当差值小于10的负6或者负7的时候结束迭代

拓扑排序

针对于一个有向无环图，它有拓扑排序，且序列可能不止一种。

有两种方法可以求拓扑排序，第一种是深度优先搜索，每一轮搜索任取一个未搜索状态的节点进行深度优先搜索，将当前结点标记为搜索中，遍历该结点的每一个相邻结点，如果相邻结点未搜索，则开始搜索它，等到搜索完成的时候再回溯。如果相邻结点搜索中，则图中存在环，不存在拓扑序列。如果相邻结点已完成，不用操作。当前结点的所有相邻结点都已完成的时候，将当前结点放入栈中，并将其标记为已完成。最后栈顶到栈底就是一个拓扑序列。

第二种是广度优先遍历，初始的时候所有入度为零的点被放进队列中，然后每一步取出一个队首元素，把它放进答案，然后把其所有相邻结点的入度都减1，如果某个节点的入度变为零，那么也把它放进队列中。当结束的时候所有的节点都在答案中的话就算找到了拓扑排序。

最长回文子串

主要有中心扩散法，动态规划法和马拉车算法

其中马拉车算法可以在线性解决，它是比较高级的算法。先在字符串中间加符号隔开预处理，使得奇偶回文数的形式统一，然后用kmp的思想去优化中心扩散

KMP字符串匹配算法

思想是利用错配的信息去减少重复匹配，对子串用指针在每走一步的时候计算一个当前字符串的最长公共前后缀（不包括本身）next数组。在计算最长公共前后缀的时候，初始的0位置设为-1（表示不动），也是同样用两个指针在子串上走，如果匹配就继续走同时用慢指针的位置更新快指针位置的next数组，如果不匹配就重新放置慢指针

然后用子串和母串去比，错配的时候根据next数据重新放置子串指针。最后返回匹配上的起始位置

K个一组的翻转链表

k个分组反转，反转有两种写法，一种是迭代（逐个反转）；一种是递归（假设它的后续都已经反转结束返回了）

为了反转之后连回原链表，我们需要同时记录子链表的头尾节点，所以用迭代法更方便，需要记录pre和nex节点来找它的前后继

另外，为了返回方便和pre的一致性，需要在头上造一个dumb节点

二叉树的最近公共祖先

课程表

计算右侧小于当前元素的个数

计算右侧小于当前元素的个数

暴力的想法就是双重遍历，这里可以利用bisect函数，但是很显然会超时。还有一种想法

线段树

hadoop学习

https://mp.weixin.qq.com/s/oGc79uYz05wDfRSivMpJUA

https://mp.weixin.qq.com/s?__biz=MzI5NzIyMjQwNA==&mid=2247484453&idx=1&sn=de66ff2df55e36d60e167923338bcbc2&chksm=ecb92c4edbcea558d270fd097e67497de01d9f0de4a56490090d74a2efd6af8ac9922187095d&scene=21#wechat_redirect

滑动窗口

76，3，209，424，438，567

双指针法

接雨水

巴科斯范式

这是在《编译原理》中的内容，可以用作编写字符串解码问题中的递归代码，根据非终结符和 FOLLOW 集构造出这样的预测分析表进行文法分析

在二叉树的序列化与反序列化中又遇到了， LL(1) 型文法。正常解法是用BFS或者DFS做

单调栈

以单调递增栈为例，如果新的元素比当前栈大，就入栈。如果新元素比栈顶元素小，就一直出栈，直到栈顶比当前元素小。这样就能保证，栈内元素递增，出栈的时候，新元素是比出栈元素向后走第一个比其小的元素

图上最短距离

单词接龙

并查集

等式方程的可满足性

转变数组后最接近目标值的数组和

找数字的题目应该想到用二分查找去做

从先序遍历还原二叉树

这个二叉树中用 - 符来标识深度，深度优先遍历一般是递归+回溯，但这里用迭代的方法更方便。递归的过程就是系统在进行函数堆栈，这里因为回传的全局变量多，所以采取了直接用栈模拟递归的方法。ord函数用于为字符串转换ASIC码，chr函数反之。

最佳观光组合

没曾想这是一道智力题，控制变量的思想，把 i 和 j 变量分离进行考虑，在扫描过程中不断更新answer和前置最大的 i位置，实现线性时间扫描

进制问题

二进制转十进制从低位到高位乘以底就可以了，十进制转二进制辗转相除，最后把结果倒着写。反转列表的时候可以用reversed返回一个迭代器，或者用sorted(a,cmp=None, key=None, reverse=True)，或者直接切片。

进制转化也可以直接用函数，int(x, 2)函数实现二进制转十进制，{0:b}.format实现十进制转2进制

模拟二进制加法的时候可以逢2进位，用carry标识。也可以用异或运算来实现（bin实现转2进制）[ 2: ]去掉0b前缀

def addBinary(self, a, b) -> str:
        x, y = int(a, 2), int(b, 2)
        while y:
            answer = x ^ y
            carry = (x & y) << 1
            x, y = answer, carry
        return bin(x)[2:]

单词拆分

基础的想法是用一个指针去做拆分，判断当前单词是否在单词表中和剩余字串是否能被break，当单词出现在字典中的时候进行向下搜索，没有出现的时候回溯进行移动指针的操作

优化的方法就是在这个DFS过程中加上记忆化，用一个memo数组去存之前遍历的结果。当然也可以用BFS加一个visited数组完成

更进一步，可以写成动态规划的形式，前 x 个字符的子串能否 break 成单词表里的单词 + 剩余子串是否为单词表中的单个单词来判断前i个字符是否可以被break

缺失的第一个正数

最基础的想法当然是两重循环，当然也可以排序去做，更进一步可以想到哈希，这时候时间复杂度被降到了线性，空间复杂度仍是N

更高效的，可以利用原数组空间，观察答案的取值范围，对负数进行处理之后，在原数组上打标记来实现哈希表的功能。或者是不断地将在[ 1，N ]区间内的数字置换到它正确的位置上去

长度最小的子数组

找到一个连续子数组，它的和大于等于给定的s。

双指针时间复杂度为线性，start和end标记数组的起止位置，当和没有满足条件的时候后移end，当满足条件之后尝试左移start，同时在满足条件的时候不断维护答案即可

还可以用二分查找+前缀和的方法去做，前缀和存储从第一位开始累加的和，然后枚举每个位置作为开始位置，二分查找满足条件的中止位置，每一次验证可以从前缀和数组之差很方便地得到

Top K问题

维护一个k的小根堆，或者是用快速选择来做。快速选择是利用了快速排序中每次排序主元都会移动到它最终的位置上这一特性来实现线性求解的

小根堆可以用heapq做，根的替换用heaprelace函数，这里顺便复习一下手写堆排序的算法流程。

首先是sift函数( 这里是大根堆为例 )，传入一个数组和位置i，它的左孩子 i 是2*i+1，右孩子是2*i+2，如果孩子节点存在且比当前的父节点大，指向这个节点，把它和父节点交换。如果存在交换，那么需要递归对交换了的节点子树进行sift。建堆的过程是从n//2开始往前sift的循环

双栈实现队列功能

这个做法很容易想到，但是有一种不用每次添加删除都来回倒腾的方法，stack_in只负责进入，stack_out只负责取出，只有stack_out为空时才把stack_in的所有元素倾倒进stack_out中，这样顺序就不会乱

最长重复子数组

动态规划法：dp[ i ][ j ]表示从A的 i 位开始和B的 j 位开始的最长公共前缀，这样每次转移只需要考虑单位的比较，从后往前更新dp

滑动窗口法：超级贴切本题，就真的是两个数组在相对滑动，在滑动中去比较此时对应位置情况的最长重复数组

二分查找 + 哈希：比较新的是题目中提到值是小于100的，用Rabin-Karp 算法对序列进行哈希，把值为S的数看做是某个素数base进制的数，它的十进制形式就是哈希值（如果很大就对其他素数取个模）。

Rolling hash，哈希碰撞（专门开了一篇文章说字符串）

有序矩阵中第k小的元素

矩阵分行有序和列有序，只考虑其一性质的时候可以把本题看成归并排序，这是多路归并，所以用小根堆来选取每次当前最小的元素

如果同时考虑两个有序信息，可以用二分查找，还没做

搜索二维矩阵和这题有相似之处，还没做

图上最短路径

DJ求单源最短路径，FD算法求多源最短路径，应用非常广泛，因为很多真实场景最后都可以化为图上的路径求解，比如计算机网络路由的路径选择。在图上对每个点都用一次DJ和FD的效果是一样的，DJ不能处理有负边的图，FD可以（但不能有负环）

FD

FD的写法非常简洁优雅，三重循环四行代码，转移方程基于动态规划，利用滚动数据和无后效性，可以降维。初始化距离矩阵为直接相连的边长，循环的时候不断遍历始末节点和中间节点，如果距离经过k节点使得距离变短了，就把k纳进来。注意三重循环的顺序，中间节点的循环在最外层，然后是始末节点的循环。

如果要打印出路径，需要定义另外一个p矩阵，p( i, j )存储路径i 到 j 上倒数第二个节点，查找的时候倒着查找，输出的是路径的反序。更新的时候如果经过k节点使得距离变短了，就把p( i, j )更新为p( k, j )

DJ

基于贪心，维护两个点集，A点集代表已经求出源点到该点的最短路的点的集合，B代表未求出源点到该点的最短路径的点的集合。维护一个向量d, d( i ) 代表源点到点 i 的最短路径长度。不断找出点集B中d( i ) 最小的点，这个点为进入点集A的候选节点，然后通过该点松弛点集B中其他的点，更新向量d，然后将该候选点放入点集A，直到点集B为空。

先初始化d数组，while点集A没有纳入所有点，在找点集B中最小的d的时候，可以用优先队列优化。但是因为在while中除了找最小的d，还需要一步更新操作，复杂度为边的数量，所以如果是稠密图，此时优先队列的引入还会增加复杂度

据说DJ还可以用斐波那契堆优化，没仔细了解过，有兴趣可以自行搜索

Bellman-Ford和SPFA

大名鼎鼎的贝尔曼算法，也是求单源最短路径的，但是它既可以处理负边也可以处理负环。SPFA是贝尔曼算法被优先队列优化之后的名称。

https://zhuanlan.zhihu.com/p/33162490

二分递归

将有序数组转换为二叉搜索树

二叉搜索树的中序遍历为有序数列，然后题目还有一个限制，需要搜索树高度平衡，这样的搜索树仍然不是唯一的。所以我们只需要对有序序列进行二分递归，在选择根节点的时候可以选择任意一个中间位置数字

优先队列

在找某个数组中最值的时候，可以用优先队列优化n的遍历过程

优先队列一般是用二叉堆实现的，可以调包，但是这里多说一点堆的调整策略，以防需要手撕堆实现的情况。i 的左节点为2i + 1, 右节点为2i + 2。父节点为( i - 1)//2

向下调整的时候，与子节点中较小的那一个进行交换，然后继续向下调整，相等的时候与右节点进行交换。向上调整的时候，也是一样，如果该节点比父节点要小，那么就需要交换，然后继续向上调整。初始化的时候先建立完全二叉树，然后从第一个非叶节点n//2-1倒着向0进行向下调整。如果修改了一个节点使之比父节点小，那么需要向上调整。插入的时候插到最末尾，然后向上调整。删除（弹出）的时候，把最后一个节点和根位置交换，缩小堆的长度（丢弃原来的根），然后向下调整。

栈处理有效匹配符

最长有效括号：

用一个栈来记录索引，特别的是，在栈存储的是最后一个没有被匹配到的括号的下标。所以当我们遇到右括号且栈正常弹出之后，栈仍然有元素时就可以更新最大有效长度了。若栈无法弹出（为空），则把当前的位置当作是最后一个没有被匹配到的右括号位置。为了应对初始空栈时遇到左括号的情况，在初始放入-1作为最后一个没有被匹配到的括号下标

这题还可以用动态规划的思想做，dp表示以当前位为结尾的子串的最长有效括号，注意到结尾只能以右括号结束，所以当当前位是右括号，前一位是左括号的时候形成基本的2位扩增，前一位也是右括号的时候利用前一位的dp值去寻找上一个子模式外的第一位符，看看它是不是左括号，是的话就形成一个大扩增，如果不是就不扩增。写程序的时候需要注意在取数组中的值的时候一定要条件判断是否在有效的index内。

还可以利用卡特兰数的思想，设立两个指针记录左右括号的数量，当左括号等于有括号的时候进行长度计算。当右括号数大于左括号的时候把两个指针重新置0。但这样做的时候当右括号数始终大于左括号数量的情况会被忽略，所以我们需要正着做一遍，反着再做一遍即可。时间复杂度还是n，空间变成了1

动态规划

通配符匹配

是正则表达式匹配的简化版，不用考虑模式串之间的跟随关系，用二维的dp表示待匹配字符串和模式串的下标是否能完美匹配，需要注意的是初始化的设定，当模式串为空的时候，只有待匹配串也为空（也就是0，0）处才为true。当待匹配串为空时，需要看模式串的前几位是否都为星号来判断。

这题还可以用贪心算法求解：

还有以字典树为基础的AC自动机，wildcard matching 算法（尚未了解）

交错字符串

三个字符串s1,s2,s3 ，判断s3能否从s1和s2交错拼接得到

想法就是拆解为s1的前 i 个， s2的前 j 个能否拼接成s3的前 i + j 个。可以用DFS递归 + 记忆化的方法，也可以直接用动态规划求解

遍历

路径总和

在遍历树结构的时候保存根节点到当前节点的路径和，可以采用深度或者广度优先遍历，广度优先遍历可以使用两个deque实现队列存储节点和当前的路径和，深度优先遍历还可以进一步演变为原函数下的递归，注意寻找条件和返回条件

股票类题目汇总

买卖股票的最佳时机

如果把股票的价格化成折线图，我们可以发现我们要找的就是波峰和波谷

最佳买卖股票时机含冷冻期

动态规划的思想，状态的定义非常关键，这里可以定义为0表示持有股票，1表示不持有股票且在冷冻期，2表示不持有股票且不在冷冻期。这里需要注意两点，第一在优化空间复杂度的时候，不要在更新过程中间去覆盖dp数组，第二是dp的初始化要把持有股票的时候设置为负的第一天的股票价格，防止根本不买入的情况。

灯泡开关

版本1: 这题需要观察规律，观察到一个位置的翻转次数等于它的因数个数，所以如果它的因数个数是奇数，它最终的状态就是开着的，如果是偶数就是关着的。另外，有奇数个因数的数字一定是完全平方数

版本2: 有两种思路，第一种是用set直接去暴力枚举每种可能的状态。第二种是通过观察发现偶数的相同操作效果会被抵消，

打家结舍

每个节点只会有选择和不选择两个状态，在二叉树上进行后续遍历去更新每个节点的最优值。用动态规划的思想开空间去记忆化搜索过程，或者在每一个递归用返回的两个状态进行判断

山谷序列

腾讯20年第二次笔试的第一题，前n个严格递减，后n个严格递增，中间两个数相同，问最长长度。

解：构造两个数组，以 i位结尾的最长递减子序列，和以 i位开始的最长递增子序列，最后对每一位在它之后的序列上找到与之相同的元素位置，取两个子序列中小的值作为所求的n值，返回2*n作为序列的长度

概率切木棍

一个长度为L的木棍，切成两段，扔掉左边的长度，当右边长度小于等于d的时候不再切割，问切割次数的期望。写成积分公式去求出长度为x的木棍的切割次数期望，带入特殊值长度为d的时候期望为0，最后把通式编码

多项式方程求根

多项式降次排列，给出系数，求使得方程为0的根，升序输出它的实根。

圆环问题

给一个些六个数的环，判断里面是否有两个环是一样的

图上送餐

n个点m条路，T次往返，给出图的边信息，每次都从原点出发，到某一点送餐，求送餐的最短距离

单源最短路径

快速幂

数值积分

原函数很复杂的时候，一般会用数值积分的方式来近似，先定义好f函数，然后用辛普森公式或者柯西公式来近似求解，这些公式的系数推导和泰勒展开相关

2020.10.18

双指针使用的场景：从两端向中间迭代数组。

毕业的文章也顺利发表，工作也有了着落，现在是2020.12.18，接下来我会用C++重新来温故一下算法知识：

找不同

这里面其中一种解法是利用异或运算，异或运算的特点有三个：任何数和0做异或，结果仍然是原来的数；任何数和自身做运算结果是0；异或满足交换律和结合律。所以出现次数为偶数的数字都会变成0，和最后数字异或仍然不改变最后一个数。体会到的一点就是，因为C++中对变量进行了严格的定义，所以它会自动进行相应的转化。