---

贵有恒,何必三更眠五更起

最无益,莫过一日曝十日寒

---

数据结构

链表

1. 链表的基本思路是多加指针
2. 链表很多是前面+dummy节点（虚拟头节点）
3. 链表删除元素： pre.next =pre.next.next

图

树

二叉树

1. 二叉树的种类
2. 二叉搜索树
3. 广度优先（队列），深度优先（栈）
4. 树的常见解决思路: 递归

图的两种表示方法

1. 邻接表
2. 邻接矩阵

算法

回溯算法

回溯算法

backtracking() { 
    if (终止条件) {
         存放结果;
     }
     for (选择：选择列表（可以想成树中节点孩子的数量）) {
        递归，处理节点;
         backtracking(); 
        回溯，撤销处理结果 
    } }

递归

1. 调用自己函数本身，就是递归

终止条件（求解最基本的问题）
递归过程（把原问题转化为更小的问题）

动态规划

动态规划的应用场景

1. 计数
2. 求最值

动态规划的两种解题思路

1. 记忆化搜索 - 从上而下 - 树
2. 数学归纳 - 从下到上 - 表

常见的动态规划的转移方程

1. 最长公共子串
   1. dp[0][j] = 0; (0<=j<=m)
   2. dp[i][0] = 0; (0<=i<=m)
   3. dp[i][j] = dp[i-1][j-1] + 1; (str1[i] == str2[j])
   4. dp[i][j] = 0; (str[i] != str[j])
2. 最长公共子序列
   1. dp[0][j] = 0; (0<=j<=m)
   2. dp[i][0] = 0;(0<=i<=m)
   3. dp[i][j] = dp[i-1][j-1] + 1; (str1[i] == str2[j])
   4. dp[i][j] = max(dp[i][j-1],dp[i-1][j]); (str1[i-1]!=str2[j-1])
3. 最长递增子序列
   1. F[x] = max(1,F[i] +1 | ai <ax && i<x)
4. 最大子序列和
   1. dp[1] = a1; (a1>0 && i==1)
   2. dp[1] = dp[i-1] +ai;(ai>=0 && i>=2)
   3. dp[i]=0; (dp[i-1] + a1 <= 0 && i>=2)
5. 数塔问题
   1. dp[i][j] = max(dp[i-1][j-1],dp[i-1][j] + data[i][j])
6. 01背包问题
   1. dp[i][j] = max(dp[i-1][j-v[i]]+c[i],dp[i-1][j])
7. 从n个数中选择k个数使之和为某个值, 背包问题的变种
   1. F(i,c) = F(i-1,c) || F(i-1,c-v[i])
   2. 时间复杂度: O(n * sum)
8. 矩阵连乘
   1. dp[i][j]=0; i==j
   2. dp[i][j] = min(dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j]); (i<j && i<=k<j)
   3. dp[1][n] 为最终解

其他算法

1. 暴力解法
2. 滑动窗口: 固定长度的滑动窗口，不定长的滑动窗口(快慢指针)
3. 深度优先算法(染色问题)
4. 双指针
5. 极值等问题
6. 连续问题(1446)
7. 单调栈应用场景: 每个数右边第一个比它大的数
8. 深度优先-栈
9. 回溯问题:
   1. 从n个数中随机取t个能否等于某个值

其他

1. 很多算法能先排序就先排序
2. 输入规模和时间复杂度关系
3. 计算机只能暴力计算,但是可能重复计算, 所以需要剪枝

python基础函数

1. functools 中的 reduce, lru_cache
2. collections 中的 Counter, defaultdict
3. itertools 中的 permutations combinations
4. heapq
5. bisect中的bisect_left,bisect_right,insort，左右指的是在相同值的左边还是右边
6. python set的交&,并|,补-, 对称差集^,比较大小<=
7. python中的按位与&，按位或|，按位异或^,按位取反~,左移<<,右移>>
8. in /not in 的判断最好是对set进行判断

时间复杂度和算法

1. 二分查找： O(log(n))

TODO

几个点

1. False == 0,True == 1,这个list[int]的判断条件时很容易错
2. 用字典的时候，先看key在不在然后再去判断相应的取值
3. 有序list 一定想到bisect
4. 最值问题首先想到动态规划
5. 没啥想法先用暴力解法
6. if not q and not p 两者都是None，有一个为None, if not q or not p