375/1000 summary

进展：

1、能开始运用题目与题目之间的关联性质解题（例如最长公共字符串问题 -> 生成最短超字符串问题）

2、对于各种基本的题型有所了解：动态规划、深度优先搜索、小顶堆、回溯、并查集，对于动态规划的解题能力有小部分提升

不足：

1、看完题解之后的思考还不够深入，挖掘的细节越是深入，下次遇到类似/相同的问题，解决问题的速度越是快

2、目前的水平还不够，至少还要经过double数量的锻炼

---

932-【分治算法】漂亮数组
836-【二维压缩到一维】判断两个矩形是否相交
812-【三角形面积计算】典型数学题
1013-【数组双指针的妙用】
904-【滑动窗口-水果篮子】
907-【最小栈-数组的所有子数组的最小值sum】
801-【状态转移方程很难写的数组题目】
1631-【二分+DFS】二维数组搜索最小gap
1140-【比较难的二维DP】石子游戏
1314-【前缀和】比较常见的DP
1039-【动态规划】倒三角经典题目，DP+画图

DFS+memo

• ★688—二维矩阵+8个行走方向，K步之后留在矩阵中的概率

DP+01矩阵

• 1504-【动态规划】全是1的矩阵个数 ——> left[i][j]：左边连续的1个数，作为辅助数组
• 1277-【动态规划】统计全为1的正方形个数 ——> dp[i,j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])+1 ：九宫格中，右下角的正方形可以通过左下角、左上角、右上角的三个点已知结果计算
• 1139-【动态规划】最大边界的镂空正方形 ——> dp[i][j][0]以及dp[i][j][1] 表示左边连续的1，以及上边连续的1，辅助四条边的判断

DP+最长子串

• 873-【动态规划】最长连续斐波那契子序列 ——> dp[i][j] 表示以(i,j) 结尾的斐波那契数列最长长度
• 1027-【动态规划】最长等差数列 ——> dp[i][j] 表示以(i,j)结尾的最长等差子串的长度

DP+前缀和

• 523-【动态规划】连续的子数组和 ——> preSum[i]-preSum[j-1] = A[j]+A[j+1]+...+A[i] + HashMap判断是否满足取模条件

DP+字符串

• 467-【动态规划】环绕字符串的唯一子字符串 ——> 问题转换为dp[0~26]保存以a,b,c...z结尾的连续最长字符串长度

DP+连续子数组

• 413-【动态规划】统计等差数列划分的个数 ——> dp[i]：以i结尾的等差数列个数

DP+字符串子序列

• 940-【动态规划】不同的子序列个数
• 1092-【动态规划】构造最短相同超序列（Hard） ——> 转换为LCS问题
• 943-【动态规划】找到最短的超字符串（Hard） ——> DFS+剪枝 | DP（TODO）
• 131-【动态规划】分割回文串 ——> DFS+剪枝

DP+概率

• 1227-【动态规划】飞机座位概率

BFS

• 542-【BFS】01矩阵中到0的最近距离 ——> 找到距离1最近的0的distance -> 转换为找到所有0到最近的1的distance
• 515-【BFS】二叉树每层的最大值 ——> 经典BFS
• 863-【BFS】二叉树中所有距离为K的节点 ——> 将树转换为图
• 934-【BFS+DFS】连接岛屿 ——> 先DFS，再BFS
• 1306-【BFS】跳跃游戏 ——> 基于一维平面的BFS
• 1038-【二叉树】把BST转换为累加树 ——> BST+哈希表

链表

• ★ 328-【链表】按照奇偶顺序重构链表 ——> 双指针
• 86-【链表】分割链表 ——> 双指针，思路同328
• ★142-【链表】判断链表是否有环 ——> 快慢指针，找到point后重试
• 1171-【链表】从链表中删除总和为0的连续节点 ——> 问题转换成找到出现两次的和，省去中间的节点
• 817-【链表】链表组件 ——> 使用HashMap查找
• 445-【链表】链表相加 ——> Stack + 经典位加法
• 92-【链表】局部反转链表 ——> 反转链表+记录标志位
• 143-【链表】重排链表 ——> 双向队列
• 148-【链表】链表排序

股票专题

• 309-【动态规划】买卖股票 ——> 一维DP、二维DP均可
• 714-【动态规划】买卖股票的最佳时间含手续费