Leetcode
###
###
###
###
Day4
链表与指针的实现 双指针解决链表问题
21. 合并两个有序链表
19. 删除链表的倒数第 N 个结点
86. 分隔链表 双指针 在合并之前需要清理pointer 2 末端的next 避免成环
876. 链表的中间结点 双指针 fast快一步
141. 环形链表 从dummy开始 iterate
23. 合并K个升序链表 用 heapq 把list里的node存进去， 然后每次pop出最小值，然后把对应node的next存入 queue，所以 queue里面需要存入node在list里对应的index。
Day5
滑动窗口
/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
unordered_map<char, int> need, window;
for (char c : t) need[c]++;
int left = 0, right = 0;
int valid = 0;
while (right < s.size()) {
char c = s[right];
// 右移（增大）窗口
right++;
// 进行窗口内数据的一系列更新
while (window needs shrink) {
char d = s[left];
// 左移（缩小）窗口
left++;
// 进行窗口内数据的一系列更新
}
}
}
Day6
数组双指针问题
leetcode704 左右指针进行二分 leetcode34 左右边界
二分模版 注意区间 还有返回值的判断
int binarySearch(int[] nums, int target) {
int left = 0, right = ...;
while(...) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
...
} else if (nums[mid] < target) {
left = ...
} else if (nums[mid] > target) {
right = ...
}
}
return ...;
}
leetcode5 回文判断 分奇偶 从中间开始判断
leetcode167 两数之和 左右指针 判断大小 缩小左右边界
Day7
前缀和
303. 区域和检索 - 数组不可变
304. 二维区域和检索 - 矩阵不可变 #### 差分数组
维护一个 差分数组
在区间上加减 只需操作对应的index即可
通过当前值加上前值来还愿数组
Day8
二分查找的应用
遇到单调函数，求左右边界是可以使用
注意如何转化提议很重要
1011. 在 D 天内送达包裹的能力 一个数组 求最小用多大的容器能 能在规定容器个数内实现
410. 分割数组的最大值 一个数组 规定了容器个数 求最小的容器容量容纳这些数
875. 爱吃香蕉的珂珂 同理 一个数组 规定了时间 求每个小时最少吃多少能在规定时间内完成
if (nums[mid] == target) {r护额
if (nums[mid] == target) {
Day8
二叉堆 （优先级队列） 多链表排序， 寻找最值
***第一类，排序合并***
23. 合并 K 个升序链表 链表中的值加入优先级队列 重新链接
373. 查找和最小的 K 对数字 虽然是两个组数进行数对排序 但可以抽象成多个链表排序的问题 如 以第一个数组的值为第一个值的多条链表。 ***
378. 有序矩阵中第 K 小的元素 同上
313. 超级丑数. 维护prime的链表 和丑数的链表， （ugly[index] *prime, prime, index+1) 每次pop出一个最小值 然后把对应链表prime上的下一个 丑数值添加入heapq
***再来看第二类，寻找第 k 个最大元素这类题：***
215. 数组中的第 K 个最大元素 维护一个size 为k的最小二叉堆 最后会留下k个最大值
451. 根据字符出现频率排序 字典排序 提取key 对key进行排序
list(freq.keys()).sort(key = lambda x: -freq[x]) #根据value对key进行降序排列
703. 数据流中的第 K 大元素
295. 数据流的中位数 大小顶堆 前一半数据在大顶堆里，
Day9
二叉树 遍历or递归 与子树相关后序遍历
二叉树的前中后序
解法
二叉树题目的递归解法可以分两类思路，第一类是遍历一遍二叉树得出答案，第二类是通过分解问题计算出答案，这两类思路分别对应着 回溯算法核心框架 和 动态规划核心框架。
dp
- 重叠子问题
- 状态转移方程
- 最优子结构
套路 1.明确 状态 2.明确 选择 应用递归进行选择 3.明确 dp函数 4.明确 base case
回溯算法
穷举
res = []
def backtrack(self, track, list):
if (end condition):
res.add(track)
return
for i in list:
# make decision
backtrack(track, list)
# undo decision
Day10
NIO 笔试
矩阵转至 暴力解 两个for loop
牛牛函数 求二进制下最小的1 x & -x
ROBOTSENSE 笔试
堆箱子 dp问题 对箱子排序 dp[i] --i对应每个箱子 两个for loop 用于更新 i箱子可以堆的最大高度
栈
143. 重排链表
20. 有效的括号 遇到有括号 一个元素出栈 用一个dict来维护对应的pair
150. 逆波兰表达式求值 运算符 从stack中pop两个值出来 根据符号进行运算
##### 单调栈
从数组尾部开始便利 用stack保存一个单调的数组 通过维护这个数组来寻找更大 更小值
739. 每日温度 496. 下一个更大元素 I 两题思路一致 一个存 index 一个存值
Day11
单调栈
1944. 队列中可以看到的人数 单调栈模版调用， 如果有比i高的人 计数器需要加1
1475. 商品折扣后的最终价格 same
402. 移掉 K 位数字 从做往右找一个单调性 如果头部为0 则不加入
Day12
单调队列 解决滑动窗口最大值问题
239. 滑动窗口最大值 collection.deque 用双端队列维护一个单调减的队列， 如果加入值比前值大，则将前值压出 窗口最大为3 每次到三个值时 压出先进的元素
1438. 绝对差不超过限制的最长连续子数组 SortedList
Day13
#####
862. 和至少为 K 的最短子数组 前缀和 单调队列 滑动窗口
**918. 环形子数组的最大和** 在数组尾部拷贝一份形成环形数组 前缀和 用一个数不可用两次所以 用一个单调队列存可行的presum 长度为数组的大小 通过preSum - s.min来update最大和
1696. 跳跃游戏 VI 动态规划 加上 通过单调队列来优化 similar problem 1425. 带限制的子序列和 209. 长度最小的子数组 🟠
hash
拉链法原理 一个table 每个index为一个slot slot用于存储链表
线性探查法 一个table 存key，value pair， 通过hashfunc将key映射到index， 如果index被占据，向后探查找到空位存放
Day14
#####哈希表的应用
15. 三数之和 🟠 以2sum为基础 进行穷举 注意跳过重复元素
138. 复制带随机指针的链表 先克隆新节点 再链接
242. 有效的字母异位词. 判断长度， 哈希表计数， python可以用counter来做
49. 字母异位词分组 用defaultdict（list）便于储存需要返回的str结果 group = collections.defaultdict(list)
169. 多数元素
387. 字符串中的第一个唯一字符
389. 找不同 位运算，ord() cast to ascil chr() cast to char https://leetcode.cn/problems/find-the-difference/solutions/526048/python3-si-chong-jie-fa-ha-xi-biao-shu-z-19mi/
442. 数组中重复的数据 哈希原地标记 用正负号来标记 如果已标为负 则出现过了
448. 找到所有数组中消失的数字 同上^^
4. 寻找两个正序数组的中位数 大小堆。sol2： 二分查找
Day15
#####哈希表的应用
linkedhashmap map key to node, use list connect ndoe 有序
Arrayhashmap map key to index, key-value pair is stored in the array
32. 最长有效括号 需要一个 dp 数组，记录 leftIndex 相邻合法括号子串的长度，才能得出题目想要的正确结果。
Day16
1235. 规划兼职工作 dp + 二分查找 dp记录前i份工作的最大收益 #####经典数据结构设计题
146. LRU 缓存 由于我们要同时维护一个双链表 cache (维护顺序)和一个哈希表 map（维护 key 映射 node）
895. 最大频率栈 map val2freq map freq to a stack fo list w.r.t this freq
284. 顶端迭代器 设一个flag 来判断 是否调用peek（） 如果是的说明指针已经移动了
Day17
BFS
// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
Queue<Node> q; // 核心数据结构
Set<Node> visited; // 避免走回头路
q.offer(start); // 将起点加入队列
visited.add(start);
int step = 0; // 记录扩散的步数
while (q not empty) {
int sz = q.size();
/* 将当前队列中的所有节点向四周扩散 */
for (int i = 0; i < sz; i++) {
Node cur = q.poll();
/* 划重点：这里判断是否到达终点 */
if (cur is target)
return step;
/* 将 cur 的相邻节点加入队列 */
for (Node x : cur.adj()) {
if (x not in visited) {
q.offer(x);
visited.add(x);
}
}
}
/* 划重点：更新步数在这里 */
step++;
}
}
752. 打开转盘锁 主要是写出node如何移动
111. 二叉树的最小深度
102. 二叉树层序遍历
107. 二叉树层序遍历2 res[::-1] 反转list
stock related problem
121. 买卖股票的最佳时机
122. 买卖股票的最佳时机 II
309. 最佳买卖股票时机含冷冻期 存一个dp_0_pre 用来两天前的价格
714. 买卖股票的最佳时机含手续费 每次买入加一个fee ——
188. 买卖股票的最佳时机 IV
def maxProfit(self, k: int, prices: List[int]) -> int:
n = len(prices)
if k >= (n // 2):
# inf times of trading
dp_0 = 0
dp_1 = -float("inf")
for i in range(n):
temp = dp_0
dp_0 = max(dp_0, dp_1 + prices[i])
dp_1 = max(dp_1, temp - prices[i])
return dp_0
else:
# maxProfit_kTimes
dp =[[[0,0] for _ in range(k+1)] for _ in range(n)]
# k = 0 时的 base case
# for (int i = 0; i < n; i++) {
# dp[i][0][1] = Integer.MIN_VALUE;
# dp[i][0][0] = 0;
# }
for i in range(n):
for k_ in range(k,0, -1):
if i== 0:
dp[i][k_][0] = 0
dp[i][k_][1] = - prices[i]
continue
dp[i][k_][0] = max(dp[i-1][k_][0], dp[i-1][k_][1] + prices[i])
dp[i][k_][1] = max(dp[i-1][k_][1], dp[i-1][k_-1][0] - prices[i])
return dp[-1][-1][0]
Day18
1768. 交替合并字符串 zip_longest的技巧
915. 分割数组 两次遍历， 第一次从左到右，记录前面的最大值， 从右到左，记录前面的最小值。 第二次遍历，从左向右，找边界。
house rob
198. 打家劫舍. DP 抢或不抢 dp[i] = max(dp[i-1], dp[i-2] + nums[i])
213. 打家劫舍 II. 环形数组 将问题拆为两条， 抢第一个[0,n-2] rob最后一个[1,n-1]
337. 打家劫舍 III. 二叉树 对于一个节点 存在偷与不偷 保存对应的最大值
递归链表
206. 反转链表 清晰reverse()的定义， reverse函数将head.next为头的链表反转，并返回末端节点的头节点
head.next.next = head 将当前头部加到链表末端
head.next = None 将当前头部的next置为空
92. 反转链表 II
先实现left为1 right为任意值的反转，这个与206类似，但我们需要记一个后驱节点，将反转的尾部接到后驱节点上
base case就是从头节点开始反转
用递归的思想，将left不为1的情况，变化成1的情况进行处理。
Day19
934 最短的桥
DFS BFS
Day20
46. 全排列 回溯 track需要用copy储存
Day21
单调栈搜索左右边界
907. 子数组的最小值之和
minstack, left, right = [], [0] * n, [0] * n
for i in range(n):
while minstack and arr[minstack[-1]] >= arr[i]:
right[minstack.pop()] = i
left[i] = minstack[-1] if minstack else -1
minstack.append(i)
25. K 个一组翻转链表：用迭代把前k个反转，然后用返回新的头节点，后面前k个进行递归，接到上一层的尾部（即旧头节点）
18. 四数之和 nSum and twoSum
234. 回文链表 后续遍历作为right指针，head作为右指针，进行比较
83. 删除排序链表中的重复元素 快慢指针
Day22
遍历二维数组
48. 旋转图像 Transpose将行转为列， 在mirror（镜像）
54. 螺旋矩阵 4个边界，遍历的同时收缩边界
59. 螺旋矩阵 II
Day23
滑动窗口的延伸 RabinKarp
**用数值替代窗口，每次从左侧加入一位，相当于将数值进一位并加上个位数的数值，删除则是减去最大位数上的数值（- R**（L-1））位数L，进制数R
滑动窗口的套路
取余运算，避免整形爆炸，最好是一个较大的素数
X % Q == (X + Q) % Q
(X + Y) % Q == (X % Q + Y % QR
滑动窗口的套路
取余运算，避免整形爆炸，最好是一个较大的素数
常数时间删除-查找数组中的任意元素
380. O(1) 时间插入、删除和获取随机元素 dict 和 array的组合 通过把需要删除的元素换到最后一个，进行移除，注意要将map移除
田忌赛马背后的算法决策
870. 优势洗牌 排序 双指针 如果大于就将right指针的值加入 否则left
528. 按权重随机选择 改成概率 然后二分搜索leftbound
Day24
去重：字典or boolean队列 &栈。加上单调栈和计数器来判断是否需要移除前数
316. 去除重复字母
1081. 不同字符的最小子序列
402. 移掉 K 位数字 单调栈，注意处理头部0和k>=length的情况
贪心，把不满足条件的值以及之后的值都改为9，前一位-1
738. 单调递增的数字 最后输出时，直接转为int型，会自动处理头部的0
二叉树：遍历与分解问题
116. 填充每个节点的下一个右侧节点指针 idea1： 从右向左BFS idea2: 三叉树
<img width="789" alt="image" src="https://user-images.githubusercontent.com/89954165/198917745-b9c781ac-8633-4af6-9b93-c6508d87e953.png">
654. 最大二叉树 找到最大值，然后左右递归
Day25
二叉树构造: 找到根节点，然后构造左右子树
105.从前序与中序遍历序列构造二叉树 、定义build为构造左右子树然后返回根节点，需要找到对应左右子树的索引。
106. 从中序与后序遍历序列构造二叉树 同上，找到左右子树对应的index
889. 根据前序和后序遍历构造二叉树，左右子树，以preorder的下一个数为左节点，找到对应的左节点在postorder中的位置，（index1），找对左树的长度，算出右树头节点的位置
297. 二叉树的序列化与反序列化 同样适用递归的方法进行反序列化
652. 寻找重复的子树 后序遍历+序列化+set&dict进行查重， dict存入第一个重复的node.
912. 排序数组 归并排序 左右sort 然后merge 注意merge的是已经排好序的子队列
Day26
归并排序的应用
493. 翻转对 运用了归并排序的思想，在merge过程中，我们需要比较有右边集合有多少满足条件的数，并有counter计数。通过一个end指针来维护满足条件的区间[mid+1, end]则为当前右指针满足的个数，因为集合已经排好序了，所以右指针的下一个满足个数至少为前一个指针的满足的个数
315. 计算右侧小于当前元素的个数 不改变数组本身，而是用一个下标索引的数组，来进行排序，可以通过下标访问到需要计数的index。
327. 区间和的个数 前缀和的归并排序，merge时记录满足条件的个数，[start,end)end为第一个不满足上界的index(前一个不满足的话，后面一个可能满足，所以要向后判断)，start为第一个满足下届的index(前面不满足的话，后面的也不可能满足，所以可以移动start index)，中间的个数为count
# count
start, end = mid+1, mid+1
for i in range(lo, mid +1):
while start<=hi and temp[start] -temp[i] < lower:
start +=1
while end<=hi and temp[end] - temp[i] <= upper:
end +=1
self.count += end - start
Day27
1688. 最大连续重复子串，暴力解，找到一个后，找两个..... #### BST
230. 二叉搜索树中第K小的元素 中序遍历
538. 把二叉搜索树转换为累加树 反过来中序遍历
Day28
BST
450. 删除二叉搜索树中的节点：想清楚如何移除找到的点，找到左子树最大值然后将右树接在后面即可
98. 验证二叉搜索树：自顶向下，对应当前节点进行判断，如果不满足BST的条件则返回False
701. 二叉搜索树中的插入操作 递归找到合适的空位，进行插入
Day 29
QuickSort & QuickSelect
排序时，当lo==hi时，则不进行排序
但在选择时， lo==hi，需要进行选择，否则无法得到lo==hi时的index
QuickSelect，类似于二分查找的操作，每次会在大于和小于之间选择一个进行
341. 扁平化嵌套列表迭代器 实则为n叉树的遍历 每个节点存的是intege or list，但这个方法有一个缺陷，如果输入的规模非常大，构造函数中的计算就会很慢，而且很占用内存，不符合迭代器的惰性。
所以我们每次在hasNext中得到下一个integer即可，dislist后将其他元素放回原位，保证顶部为integer。在Next函数中移除第一个值即可。
236. 二叉树的最近公共祖先 判断左右子树中是否找到数值，如果都找到的话，则更新这个点为公共祖先，否则将左右子树中非0的项作为公共祖先
235. 二叉搜索树的最近公共祖先：利用左小右大的特效，如果一个节点满足小值在左，大值在右，则这个点就是公共祖先，否则根据值的大小，选择一棵子树进行查询。
222. 完全二叉树的节点个数：分解为满二叉树和非满二叉树求和
1106. 解析布尔表达式 栈模拟
Day30
Graph Theroy
797. 所有可能的路径：遍历
300. 最长递增子序列：当前最大值取决前面比这个值小的最大值+1
354. 俄罗斯套娃信封问题：二分查找 <img width="966" alt="image" src="https://user-images.githubusercontent.com/89954165/200191944-e6ac710a-7a8a-4c54-aa9e-9d23d7f6f5a7.png"> <img width="1028" alt="image" src="https://user-images.githubusercontent.com/89954165/200191955-d681bbd5-6f3e-4a5a-9b9e-a0161b7798bb.png">
二分寻找左边放置数值，找不到对应的边界，则新增堆
Day31
816. 模糊坐标：3循环的字符串处理，避免小数点后带0，避免第一位为0的整数，除0本身
DP
931. 下降路径最小和：DP，注意边界条件，索引问题
72. 编辑距离，好题！！注意base case的处理 当i or j为0时， 所需操作数=另一个不为0的索引值 <img width="360" alt="image" src="https://user-images.githubusercontent.com/89954165/200218676-5566090c-3cce-47e6-8063-313d17047e74.png">
53. Maximum Subarray dp，滑动窗口，前缀和都可解，dp比较直观 dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
Day32
1684. 统计一致字符串的数目 set()是可以相减的
DP
583. 两个字符串的删除操作 寻找公共子序列的长度，原长-公共子序列的长度
143. 最长公共子序列 dp[i][j]的定义是，在s1[:i-1]和s2[:j-1]上，两者的公共子序列长度，那么如果s1[i]==s2[j], dp[i+1][j+1]的长度是dp[i][j] +1
0-1 bag
首先是背包分类的模板： 1、0/1背包：外循环nums,内循环target,target倒序且target>=nums[i]; 2、完全背包：外循环nums,内循环target,target正序且target>=nums[i]; 3、组合背包：外循环target,内循环nums,target正序且target>=nums[i]; 4、分组背包：这个比较特殊，需要三重循环：外循环背包bags,内部两层循环根据题目的要求转化为1,2,3三种背包类型的模板
然后是问题分类的模板： 1、最值问题: dp[i] = max/min(dp[i], dp[i-nums]+1)或dp[i] = max/min(dp[i], dp[i-num]+nums); 2、存在问题(bool)：dp[i]=dp[i]||dp[i-num]; 3、组合问题：dp[i]+=dp[i-num];
1049. 最后一块石头的重量 II（首先，先将问题转换为背包问题）
dp[i][j]含义:从前i块石头中选取，选取值之和小于等于目标值j的最大值为dp。（i、j分别对应从外到内两层循环。）
322. 零钱兑换
dp[i][j]含义:前i种面额的硬币，组成总额为j金额使用的最少硬币数为dp。（i、j分别对应从外到内两层循环。）
416. 分割等和子集（首先，先将问题转换为背包问题）
dp[i][j]含义:对nums的前i个元素进行选取，dp记录是否存在选取值相加结果为目标值j。（dp是bool型）（i、j分别对应从外到内两层循环。）
494. 目标和（首先，先将问题转换为背包问题）
dp[i][j]含义:对nums的前i个元素进行选取相加值为目标值j的组合个数为dp。（i、j分别对应从外到内两层循环。）
279. 完全平方数（首先，先将问题转换为背包问题）
dp[i][j]含义:前i个完全平方数，组成目标值j时，使用的完全平方数最少个数为dp。（i、j分别对应从外到内两层循环。）
377. 组合总和 Ⅳ
dp[i][j]含义:组成目标值为i的组合的最后一个数是nums[j]的组合的个数为dp。（i、j分别对应从外到内两层循环。）。注：因为本题需要考虑组合的顺序，顺序不同则被视为不同的组合。所以状态定义要考虑到每种目标值的最后一个nums的选取上。
518. 零钱兑换 II
dp[i][j]含义:前i种面额的硬币，组成总额为j的金额的不同组合个数为dp（i、j分别对应从外到内两层循环。）。
1155. 掷骰子的N种方法：
dp[i][j]含义:前i个骰子总点数为j的不同组合个数为dp（i、j分别对应从外到内两层循环。）。最内侧对骰子面数的循环，是一个累加过程（最后一个骰子每个面朝上组合数的累加）。
518. 零钱兑换 II
416. 分割等和子集：将问题转化为0-1背包，用其中元素装满sum/2的bag，每个元素不能重复使用，判断是否能将一个数组分割为两个子集,其和相等 0-1背包存在性问题：是否存在一个子集,其和为target=sum/2,外循环nums,内循环target倒序
1049. 最后一块石头的重量 II
416 题 将集合分成两个相等子集，相当于问你如何装满一个容量为 sum / 2 的背包，这是标准的背包问题。但 698 题让你将集合分成 k 个相等的子集，也就是每个子集元素之和为 sum / k。对于某一个子集来说，可以把问题转化为装满容量为 sum / k 的背包问题，但问题在于你要同时保证其他的 k - 1 个子集元素之和也都是 sum / k，那么这就无法用标准的背包问题思路求解了，只好用回溯算法的暴力穷举一个个尝试。
Review
5. 最长回文子串 双指针，对每个index进行查找
Day33
Todo： 516. 最长回文子序列,压缩空间是，注意边界条件
1312. 让字符串成为回文串的最少插入次数
494. 目标和（首先，先将问题转换为背包问题）
sum(a) - sum(b) = target
sum(a) + sum(a) = target + sum
sum(a) = (target + sum) / 2
dp[i][j]含义:对nums的前i个元素进行选取相加值为目标值j的组合个数为dp。（i、j分别对应从外到内两层循环。）
dp[i][0] = 1 在前i个数进行组合相加时，总可以不选任何值，得到目标值0
*** 此题，因为j=0时可能存在的而不是base case，所以遍历的时候要从sum(a)遍历到0
764. 最大加号标志 四个方向的前缀和，统计连续1的个数，每个位置可以形成的最大十字取决于四个方向上最小的连续1个数
求满足target的不同组合数
dp[j]:满足j的不同组合数, dp[target] = dp[target -nums[0]] + dp[target -nums[1]] + dp[target -nums[2]]....内循环要求出满足调整的所有组合
322. 零钱兑换
70. 爬楼梯
377. 组合总和 Ⅳ：🉑️dp，但排列组合问题用回溯比较直观 <img width="682" alt="image" src="https://user-images.githubusercontent.com/89954165/200740670-f07cc0b8-17ff-4733-b475-f809a9200750.png">
Day34
random one
791. 自定义字符串排序
DP
64. 最小路径和 dp
174. 地下城游戏 逆向，从[i,j]到最后的节点需要多少血量，[i-1,j-1]到[i-1,j]和[i,j-1]两种,正序dp，此时dp[i][j]代表(0，0)到(i,j)的最低血量；但是实际递推时发现无法处理正健康值的网格，比如下一个网格是正健康值，则从起点到下一个网格的最低初始血量不变，但健康值发生了改变，dp数组无法记录与反映这一变化。考虑倒序dp，此时dp[i][j]代表(i,j)到终点的最低血量，此时根据: 后一节点到达终点所需的最低血量(已知)、与当前节点的健康值(已知)倒推当前节点到达终点的最低血量(至少等于1)
514. 自由之路
787. K 站中转内最便宜的航班 dp 注意一些细节，比如用temp的dp数组来计算每次中转的结果，避免在一次中转中出现多次中转的问题，有无dp可能会有多个值，所以记得每次update时，要用更新值和dp本身中取最小值
Day34
10. 正则表达式匹配:when we reach "*" and [i] == [j-1], we can choice match or not. If not, the j move forward 2 steps, otherwise, i move forward one step. <img width="913" alt="image" src="https://user-images.githubusercontent.com/89954165/201205419-176d81be-5115-448f-b5f9-a46c09e5921c.png"> <img width="808" alt="image" src="https://user-images.githubusercontent.com/89954165/201205467-17d87f68-f865-44eb-a88b-65496f414441.png">
贪心
435. 无重叠区间：按照end时间排序，往下压，直到找到下一个满足条件（next start》 last end），替换end，反复操作，找到无重叠区间的个数
452. 用最少数量的箭引爆气球：同上，找到无重叠区间的个数，但是边界条件有变化
55. 跳跃游戏:找到最远可以达到的距离
45. 跳跃游戏 II:选择最优跳跃，用end表示这个跳跃的结束，i 和 end 标记了可以选择的跳跃步数，farthest 标记了所有选择 [i..end] 中能够跳到的最远距离，jumps 记录了跳跃次数。相当于用end来实现选择跳跃这个循环，当i=end时，选出下一个选择范围
Day35
7. 整数反转
790. 多米诺和托米诺平铺，dp 找到状态转移 <img width="657" alt="image" src="https://user-images.githubusercontent.com/89954165/201415654-6d989284-6fe5-4aae-8158-e4c32ec6dfd7.png">
11. 盛最多水的容器,双指针，理想状态面积最大是，宽度和高度都最大，但是从宽度最大开始收缩，面积
42. 接雨水:双指针，分别记录左指针之前和右指针之后的最大值，如果左指针的最大值小于右指针的最大值，那么可以求左指针这个点能接的雨水，因为能接的雨水量取决于左右最大值中较小的那个
887. 鸡蛋掉落
1、无论你在哪层楼扔鸡蛋，鸡蛋只可能摔碎或者没摔碎，碎了的话就测楼下，没碎的话就测楼上。
2、无论你上楼还是下楼，总的楼层数 = 楼上的楼层数 + 楼下的楼层数 + 1（当前这层楼）。
dp[k][m - 1] 就是楼上的楼层数，因为鸡蛋个数 k 不变，也就是鸡蛋没碎，扔鸡蛋次数 m 减一；
dp[k - 1][m - 1] 就是楼下的楼层数，因为鸡蛋个数 k 减一，也就是鸡蛋碎了，同时扔鸡蛋次数 m 减一。
Day36
8. 字符串转换整数 (atoi) 仔细读题，去空格，如果有符号的话，提取出来，然后判断后面的是否是数字
DP
312. 戳气球:dp[i][j]表示在（i，j）这个开区间上，可以得到的最大值，遍历i+1到j-1，得到dp[i][k]+dp[k][j] + nums[i] * nums[k]*nums[j]，找到最大的dp[i][j]。 <img width="759" alt="image" src="https://user-images.githubusercontent.com/89954165/201487212-bdffa195-641c-45c3-a0f5-7984f244d2d8.png">
从下上往遍历，看图，比较直观 <img width="855" alt="image" src="https://user-images.githubusercontent.com/89954165/201487196-73891d02-381d-4402-9755-117466e1edd6.png">
877. 石子游戏 <img width="764" alt="image" src="https://user-images.githubusercontent.com/89954165/201490293-ade459c7-9e61-4fb5-8bf9-3aae8fd9ee6e.png">
Day37
805. 数组的均值分割
def splitArraySameAverage(self, nums: List[int]) -> bool:
n = len(nums)
if n<2:
return False
total = sum(nums)
average = total / len(nums)
# 使nums的和为0。 *n 避免浮点数
for i in range(n):
nums[i] = nums[i] * n - total
m = n//2
# 找到所有子集合的sum
def findSubSum(x):
res = set()
def solve(i,s,count):
if i == len(x):
if count: res.add(s)
else:
solve(i+1,s+x[i],count+1)
solve(i+1, s, count)
solve(0,0,0)
return res
s1, s2 = findSubSum(nums[:m]), findSubSum(nums[m:])
leftsum, rightsum = sum(nums[:m]), sum(nums[m:])
if 0 in s1 or 0 in s2:
return True
for s in s1:
# 需要注意 s 不能等于leftsum，否则就只剩下一个集合了
if -s in s2 and not (leftsum == s and rightsum == -s):
return True
return False
DP
279. 完全平方数:转化为背包问题，能装n的背包，有[1,4,9,....]这些重量货，最少赚满背包需要几个货。或者用BFS来解决
位运算
191. 位1的个数: n&(n-1),移除最后一个1
231. 2 的幂:2 的幂，在二进制中只有一位为1
326. 3 的幂: 一直对n%3，如果为0则/3，继续，最后n=1则为3的幂
342. 4 的幂: 四的幂一个是2的偶数幂，2的偶数幂%3 ==1 2的基数幂%3 == 2
268. 丢失的数字
Day38
845 数组中的最长山脉：用双指针从头开始遍历，left指在山脉的开端，right指在山脉的结尾（最后一个满足条件的index），update结束后把left移到right后一位 #### 岛屿问题
200. 岛屿数量：遍历整个grid，当遇到1时，用dfs把所有相邻的1变为0
Day39
775. 全局倒置与局部倒置:如果一个数偏离他的index两位以上，则全局倒置》局部倒置，说明有一个数至少大于当前index而且大于index+这两个值。 #### 岛屿问题
1020. 飞地的数量:用dfs淹没岛屿，将所有连着的1变为0并统计数量，如果1在边界上，则记为0
1254. 统计封闭岛屿的数目:把所有边界的陆地用dfs淹没，然后遍历整个grid，遇到0则+1并dfs
Day40
392. 判断子序列:判断子序列，双指针
792. 匹配子序列的单词数：双指针，将所有s中的字符所对应的索引存入字典，每次遇到word一个字符，找到s中该字符所对应的索引，根据word上一个字符对应s中的index（x），在char_index[cur]中进行二分查找，这个字符的index在x后(target),找到则返回这个字符在s中的索引，并把下一个x设为 s'+1，找不到则返回-1. #### 岛屿问题
695. 岛屿的最大面积:遇到1dfs，然后update最大值
1905. 统计子岛屿:先将grid2中不可能为子岛的岛淹没，然后再遍历grid中 岛屿的个数
123
Day40
891. 子序列宽度之和：排序， i作为最小值的贡献为 2**（n-1-i)， i作为最大值的贡献为 2**i, 用快速幂，否则超时
a & 1 可以判断奇偶
a >>=1 相当于除以2 #### 次方幂
372. 超级次方：递归，每次把最后一个数的幂求出来，然后乘在pow([:-1],10,mod) 
50. Pow(x, n): 分奇偶，如果为偶数，计算减半。如果n为负数，则取倒数，然后再递归 
回溯
37. 解数独:对于每一个可行位置选择1～9，判断每个数字的可行性，如果可行进去下一个j。如果j超出index范围，说明需要换行，则i+1，j=0。避免无限递归，base case为当i==len（grid）， return True。 ***因为只要找到一个可行解就可，所以backtark可以返回boolean，如果为True 则直接返回***
22. 括号生成:有效括号的条件是，左括号比不比右括号少，最后左右括号的个数相等。
岛屿问题
694. 不同岛屿的数量:用一个数组来记录dfs的遍历顺序，前序后序都需要记录。
Day41
1732. 找到最高海拔:差分数组的还原
Day42
检查子树:递归，判断当前树是否可行，如果不行就判断左子树和右子树，当递归到t1==None时，如果t2不为空，则false，反之true
2007. 从双倍数组中还原原数组:哈希表
799. 香槟塔：模拟，用一个滚动数组储存每一行的值，这个值可以从上一行的数据进行转移，如果》1，则多余的部分转移到杯中，否则不变
645. 错误的集合: 把当前值作为索引，将索引所对的数标为负数，遇到重复值时，索引对应的数已经为负数了。缺失的数字就是唯一为正数的索引
292. Nim 游戏: 只要1～3，5～7，9～11，都可以赢，所以只要不是4个倍数就能赢
Day 43
808. 分汤, dp or dfs, 加上概率 当n//25 》= 179时，答案约为1，(dfs（a-4,b) + dfs(a-3,b-1) + dfs(a-2,b-2) + dfs(a-1, b-3))/4
**** 注意使用 @lru_cache，来缓存dfs的结果
319. 灯泡开关： 巧妙利用因子个数，只有当个数为奇数的时候，才能得到使灯亮着，只有平方数的因子数为奇数个。
1288. 删除被覆盖区间:合并，覆盖，换区间 <img width="558" alt="image" src="https://user-images.githubusercontent.com/89954165/202967444-940378c3-c57e-4ebb-ba66-24a75a841483.png">
Day 44
878. 第 N 个神奇数字:二分查找，lcm(a,b)最小公倍数，容斥原理 <img width="192" alt="image" src="https://user-images.githubusercontent.com/89954165/203187523-8377b8ee-8c69-4b50-9cbd-e319e3ca90ec.png">
Day 45
56. 合并区间:sort and two pointers
123adasd
Day 46
1569. 将子数组重新排序得到同一个二叉查找树的方案数：分别对左右子树进行考虑，左子树的可行个数 * 右子树的可行个数 * 左右子树的组合个数（comb（a,b）)
其中，左右数组合并的方式，相当于从m+n个位置中，选出m个位置来放左边的数组，剩下的放右边的数组。这样就能保证左右数组中，内部的相对顺序不变。 
986. 区间列表的交集:双指针，key：如何判断有交集，有交集则找到交集并记录，每次都需要移动一个指针，当前末端小的那一个进行移动
43. 字符串相乘:从末端一位一位的模拟乘法，分别用两个指针指在对应的位数上，结果对应的位数在i+j和i+j+1上，将结果存在一个数组里面，取出leading 0 转为字符串
Day 47
795. 区间子数组个数: 双指针，一个指向上一个大于right的，另一个指向上一个大于left的，计算区间长度
809. 情感丰富的文字:比较模版，长度不一样，字符不一样，目标字符个数为2但自身字符个数不为2.
659. 分割数组为连续子序列: 对于每一个数来说，有两种分配情况，一种是接在已经存在的序列之后，另一种是作为开头重新再开一个序列，如果两都不满足，说明False
123
Day 48
#882 细分图中的可到达节点 dijkstra
1234123124123
Day 49
dijkstra
1. 有向图和无向图都可以用dijkstra，
2. Dijkstra计算最短路径的正确性依赖于一个前提，路径中每增加一条边，路径的总权重就会增加。（理解为单调性）
743. 网络延迟时间: build the gradh, dijkstra
1514. 概率最大的路径：
1631. 最小体力消耗路径
Day 50
813. 最大平均值和的分组 dp[i][j]表示前i位数分成j组的平均值最大和，base case：当j ==1时，求所有数的平均值，dp[i][j]的最大值为，所有可能的dp[j-2:i]【j-1】
+ 剩余值的平均值中，最大的那个。（使用presum以便于计算平均值）
1 ssdasdf
Day 51
712. 两个字符串的最小ASCII删除和 dp 求最大公共子序列的ascii码
123
Day 52
125. 验证回文串 字符串处理技巧，filter(str.isalnum,s) remove all non alphabet or number
680. 验证回文串 II
Day 53
2287. 重排字符形成目标字符串 Counter 计数 取最小值
397. 整数替换， 递归+记忆化 ***@cache****
Day 54
560. 和为 K 的子数组 连续数组求和：前缀和 用hashmap寸每个前缀和出现的次数，来避免循环
Day 55
207 图遍历，环检测。
530. 二叉搜索树的最小绝对差: 二叉树中序遍历---有序