Goog Good Study, Day Day Up……

2020-07

日期	题目	题解	难度
1	718. 最长重复子数组	动态规划	☆ ☆ ☆
2	378. 有序矩阵中第K小的元素	二分查找 + 归并排序(利用小顶堆进行归并)	☆ ☆ ☆
3	108. 将有序数组转换为二叉搜索树	中序遍历，总是选择中间位置左边的数字作为根节点	☆
4	32. 最长有效括号	栈(栈内元素是包含括号字符和索引的包装类)	☆ ☆
5	44. 通配符匹配	动态规划	☆ ☆ ☆ ☆ ☆
6	63. 不同路径 II	动态规划	☆ ☆ ☆
7	112. 路径总和	递归	☆ ☆
8	面试题 16.11. 跳水板	数学方法枚举	☆
9	面试题 17.13. 恢复空格	动态规划 + 字典树(Trie)	☆ ☆ ☆ ☆
10	309. 最佳买卖股票时机含冷冻期	动态规划(会用状态机状态转换的思想，对股票的收益和不同操作状态进行动态转换)	☆ ☆ ☆ ☆ ☆
11	315. 计算右侧小于当前元素的个数	归并排序计算逆序数 + 索引数组 submissions	☆ ☆ ☆ ☆ ☆
12	174. 地下城游戏	动态规划(此题正向进行动态规划很难确定两个预期值的最优，采用逆向，从数组右下角开始)	☆ ☆ ☆ ☆ ☆
13	350. 两个数组的交集 II	排序 + 双指针，两数组排序后，根据各个数组指针所指值大小来移动求交集	☆ ☆
14	120. 三角形最小路径和	动态规划(重点是从三角形的底部开始转移，到顶部结束，转移的过程中计算最小和)	☆ ☆ ☆
15	96. 不同的二叉搜索树	动态规划(当前节点数的不同二叉搜索数个数 = 左子树不同二叉搜索树个数 * 右子树不同二叉搜索树个数)	☆ ☆ ☆
16	785. 判断二分图	节点染色 + 广度/深度优先搜索遍历图(二分图节点分为两种颜色红、绿，如果相邻节点颜色同时是红和绿，肯定不是二分图)	☆ ☆ ☆ ☆
17	35. 搜索插入位置	二分查找	☆
18	97. 交错字符串	动态规划(定义 dp(i)(j) 表示s1的前i个元素和s2的前j个元素是否能交错组成s3的前i+j 个元素)	☆ ☆ ☆ ☆ ☆
19	312. 戳气球	[动态规划(def(i,j)函数的定义则为不戳破i与j，仅戳破i与j之间的气球我们能得到的最大金币数，如此划分状态转移方程def(i,j) = max{ def(i,k) + def(k,j)+nums[i][j][k]}\	i<k<j的实现,其中nums[i][j][k]为戳破气球k时我们能得到的金币数，因为def(i,j)表示戳破i到j之间的气球，自然包括k)]a178d2fb	☆ ☆ ☆ ☆ ☆ ☆
20	167. 两数之和 II - 输入有序数组	双指针	☆
21	95. 不同的二叉搜索树 II	递归(根据根节点，递归求解左右两边节点分别所能构的二叉搜索数集合，组合左右集合，构建当前根节点二叉搜索数)	☆ ☆ ☆
22	剑指 Offer 11. 旋转数组的最小数字	二分法(根据mid节点的值与right节点值大小的比较来移动left和right指针)	☆ ☆
23	64. 最小路径和	动态规划	☆ ☆
24	1025. 除数博弈	数学问题，递推找规律(N奇数的时候Alice（先手）必败，N为偶数的时候Alice必胜)	☆ ☆
25	410. 分割数组的最大值	动态规划(dp[i][j]表示将数组的前i个数分割为j段所能得到的最大连续子数组和的最小值)	☆ ☆ ☆ ☆ ☆
26	329. 矩阵中的最长递增路径	记忆化深度优先搜索(需要有一个二维数组记录每个节点能走的最远路径大小)	☆ ☆ ☆ ☆ ☆
27	392. 判断子序列	双指针	☆
28	104. 二叉树的最大深度	递归	☆
29	LCP 13. 寻宝	状态压缩动态规划(题解未看懂)	☆ ☆ ☆ ☆ ☆ ☆ ☆
30	343. 整数拆分	动态规划(dp[i]表示将正整数i拆分成至少两个正整数的和之后，这些正整数的最大乘积。将i拆分成j和i−j的和，如果i−j不再拆分成多个正整数，此时的乘积是j×(i−j)；如果i−j继续拆分成多个正整数，此时的乘积是j×dp[i−j])	☆ ☆ ☆ ☆
31	面试题 08.03. 魔术索引	单次遍历判断索引和索引对应的元素值	☆

2020-06

日期	题目	题解	难度
21	124. 二叉树中的最大路径和	递归，要理解最大路径和，节点的最大贡献值的区别	☆ ☆
22	面试题 16.18. 模式匹配	根据模式枚举	☆ ☆ ☆ ☆
23	67. 二进制求和	末尾对齐，短序列遍历过程空位取0,逐位相加	☆
24	16. 最接近的三数之和	排序 + 双指针	☆
25	139. 单词拆分	动态规划，刚刚开始用DFS实现，运行超时，需理解动态规划思想	☆ ☆ ☆
26	面试题 02.01. 移除重复节点	哈希表	☆
27	41. 缺失的第一个正数	哈希表(通过数组值对应原数组下标构建hash表，两种方式：置换 + 标记为负数)	☆ ☆ ☆
28	209. 长度最小的子数组	双指针	☆ ☆
29	215. 数组中的第K个最大元素	基于快速排序的选择方法	☆ ☆ ☆
30	剑指 Offer 09. 用两个栈实现队列	双栈	☆