LeetCode

---

• ☁ 轻松
• ★ 做出来了但没有题解思路好
• ☪ 思考很久
• ⚡ 没有做出✘

类型	难度☁★☪⚡	编号	名称
链表
	★	19	删除链表的倒数第N个节点
	☁	21	合并两个有序链表
	★	23	合并K个排序链表
	☁	24	两两交换链表节点
	☁	25	K个一组翻转链表
树
	☁	208	实现-trie-前缀树
	☁	211	添加与搜索单词
	★	437	路径总和-iii
图
递归
	★	10	正则表达式匹配
	⚡	44	通配符匹配
回溯
	★	37	解数独
	⚡	39	组合总和
	⚡	40	组合总和 II
	☁	46	全排列
	⚡	47	全排列 II
dfs/bfs
	☪	51	n-皇后
	☁	52	n皇后-ii
	★	212	单词搜索-ii
	☪	675	为高尔夫比赛砍树
贪心
	☪	45	跳跃游戏-ii
	☁	53	最大子序和
	☁	55	跳跃游戏
	⚡	300	最长递增子序列 （系列/动态规划/贪心）
	☪	918	环形子数组的最大和
动态规划
	☁	62	不同路径
	☁	63	不同路径-ii
	☁	64	最小路径和
	☁	70	爬楼梯
	⚡	91	解码方法
	☁	121	买卖股票的最佳时机 (系列)
	☪	139	单词拆分
	☪	152	乘积最大子数组
	⚡->☪	198	打家劫舍
	☪	213	打家劫舍-ii
	⚡	264	丑数-ii
	⚡	300	最长递增子序列 （系列/动态规划/贪心）
	☁	509	斐波那契数
	☪	740	删除并获得点数
	☁	746	使用最小花费爬楼梯
	⚡	877	石子游戏 (系列)
	★	1014	最佳观光组合
	☪	1567	乘积为正数的最长子数组长度
特殊-不一样
	☪	11	盛水容器
	⚡	31	下一个排列
	⚡	41	缺失的第一个正数
	☪	42	接雨水
	☁	48	旋转图像
	☪	60	排列序列
	☁	65	有效数字
	☁	400	第-n-位数字
特殊-游戏转化
	☪	583	两个字符串的删除操作 (系列)
特殊-模拟
	⚡	799	香槟塔
特殊-数学
	☁	292	nim-游戏
	⚡	877	石子游戏 (系列)
系列-数字求和
	★	1	两数之和
	★	15	三数之和
	★	16	最接近的三数之和
	☁	18	四数之和
系列-特殊顺序
	☁	74	搜索二维矩阵
	⚡	240	搜索二维矩阵-ii
	☁	496	下一个更大元素-i
系列-转换位运算
	★	187	重复的DNA序列
	☁	318	最大单词长度乘积
	☁	397	整数替换
系列-数组查找
	★	4	从多个数组找中位数
	⚡	33	搜索旋转排序数组
	☁	34	在排序数组中查找元素的第一个和最后一个位置
	☁	35	搜索插入位置
系列-子串
	☪	3	无重复最长子串
	⚡	5	最长回文子串
	☪	28	子串匹配
	☪	30	串联所有单词的字串
	⚡	300	最长递增子序列
	☪	583	两个字符串的删除操作
	☪	1143	最长公共子序列
	☁✘	1218	最长定差子序列
系列-成对符号
	☁	20	有效括号
	⚡	22	括号生成
	☪	32	最长有效括号
系列-石子游戏
	⚡	877	石子游戏
系列-股票
	☁	121	买卖股票的最佳时机
	☁	122	买卖股票的最佳时机-ii
	⚡	309	最佳买卖股票时机含冷冻期
	☪	714	买卖股票的最佳时机含手续费
系列-easy
	☁	2	两数相加
	☁	6	Z字形变换
	☁	7	整数反转
	☁	8	字符串转换整数(atoi)
	☁	9	回文数
	★	12	整数转罗马数字
	☁	13	罗马数字转整数
	☁	14	最长公共前缀
	☁	17	电话号码的字母组合
	☁	26	删除排序数组中的重复项
	☁	27	移除元素
	☁	29	两数相除
	☁	36	有效的数独
	☁	38	外观数列
	☁	43	字符串相乘
	☁	49	字母异位词分组
	☁	50	pow-x-n
	☁	54	螺旋矩阵
	☁	56	合并区间
	☁	57	插入区间
	☁	58	最后一个单词的长度
	☁	59	螺旋矩阵-ii
	☁	61	旋转链表
	☁	66	加一
	☁	67	二进制求和
	☁	68	文本左右对齐
	☁✘	69	sqrt-x
	☁	71	简化路径
	☁	73	矩阵置零
	☁	118	杨辉三角
	☁	119	杨辉三角-ii
	☁	162	寻找峰值
	☁	165	比较版本号
	☁	237	删除链表中的节点
	☁	263	丑数
	☁	273	整数转换英文表示
	☁	299	猜数字游戏
	☁	326	3-的幂
	★	352	将数据流变为多个不相交区间
	☁✘	371	两整数之和
	☁	412	fizz-buzz
	☁	413	等差数列划分
	☁✘	423	从英文中重建数字
	☁	430	扁平化多级双向链表
	☁	447	回旋镖的数量
	☁	476	数字的补数
	☁	524	通过删除字母匹配到字典里最长单词
	☁	563	二叉树的坡度
	☁	594	最长和谐子序列
	☁	700	二叉搜索树中的搜索
	☁	704	二分查找
	☁	709	转换成小写字母
	☁	725	分隔链表
	☁	807	保持城市天际线
	☁	831	隐藏个人信息
	★	869	重新排序得到2的幂
	★	902	最大为N的数字组合
	☁	1005	k-次取反后最大化的数组和
	☁	1137	第-n-个泰波那契数
	☁	1221	分割平衡字符串
	☁	1894	找到需要补充粉笔的学生编号

---

链表

• [19] 删除链表的倒数第N个节点

单向链表，只遍历一次，避免到末尾回不来，考虑双指针。

• [21] 合并两个有序链表

• [23] 合并K个排序链表

分治+递归，代码更简洁。

• [24] 两两交换链表节点

• [25] K个一组翻转链表

---

树

• [208] 实现-trie-前缀树

前缀树是一个好的工具。

• [211] 添加与搜索单词

同208题。

• [437] 路径总和-iii

关键在于起始节点如何考虑到。

---

图

---

递归

• [10] 正则表达式匹配

递归方式，代码更简洁。递归思维。

• [44] 通配符匹配

递归超时
题解：
方法1：动态规划
方法2：贪心

---

回溯

• [37] 解数独

大量分支，回溯法。
题解的代码更加精简。

• [39] 组合总和

回溯法，
从局部考虑去回溯很困难解决细枝末节，
从大局观考虑，递归查找，思维和代码更简洁。

• [40] 组合总和 II

同上，但需要更巧的剪枝，观察规律，剪掉兄弟结点的枝。

• [46] 全排列

将元素插入到空隙。
（大多数人使用回溯的方法，本题我这样也没问题。
只是插空的方法，下一题就无法基于本题的方法了。）

• [47] 全排列 II

继续按照插空的到的结果，再集中取重，尽管通过了，但显然不"算法"。
题解：回溯 + 剪枝
巧妙的剪枝，有效去重。

---

深度/广度优先

• [51] n-皇后

搜索回溯
dfs搜索，for回溯。

• [52] n皇后-ii

同51题。

• [212] 单词搜索-ii

关键在与选择dfs还是bfs，
利用for循环递归调用dfs，加上前后配上vis，
可以实现分支路口的回溯。

题解使用的前缀树方法更加简洁和高效。

• [675] 为高尔夫比赛砍树

---

贪心

• [45] 跳跃游戏-ii

动态规划
题解：贪心，时间和空间复杂度都更小。

• [53] 最大子序和

经典算法题。

• [55] 跳跃游戏

相比45题，难度骤降，贪心十分明显。

• [300] 最长递增子序列 （动态规划/贪心）

贪心
题解：需要维护一个贪心的列表，才能处理新子序列。

• [918] 环形子数组的最大和

由于需要考虑环，将其分为2部分，
1.中间，同53题；
2.两端，减去最小子序列和，即为2端。

---

动态规划

• [62] 不同路径

找规律

• [63] 不同路径-ii

找规律

• [64] 最小路径和

• [70] 爬楼梯

同509题

• [91] 解码方法

类似91题

• [152] 乘积最大子数组

1.动态规划，分成2部分存储最优子解，互相取用。
2.以0分割部分，再以负数的奇偶个数分割部分。

• [139] 单词拆分

关键在于如何剪枝，跳过重复的路径。

• [198] 打家劫舍

动态规划
这是一个抢或不抢的问题。
不抢，可能下一个更好。

• [213] 打家劫舍-ii

动态规划
同198题，跑两次。

• [264] 丑数-ii

逐个判断会超时。
规律：丑数x丑数=丑数
可以想办法从前面的丑数推出下一个丑数。

• [300] 最长递增子序列 （动态规划/贪心）

动态规划
题解：关键在于找到状态转移方程。

• [509] 斐波那契数

动态规划，入门题

• [740] 删除并获得点数

动态规划
思维转换一下，可以将其转为198题

• [746] 使用最小花费爬楼梯

动态规划

• [1014] 最佳观光组合

动态规划
确定固定部分，找出状态转移，明确影响范围。 （自己做的解虽然也是动态规划，比较好理解，但没有题解这么高效。）

• [1567] 乘积为正数的最长子数组长度

同152题
不关心值的大小，只在乎正负。

---

特殊

不一样

• [11] 盛水容器

观察情况，控制变量，使其单调变化，可将O(n^2)转为O(n)，避免遗漏一些情况。

• [31] 下一个排列

找规律，观察下一个排列与此的变化过程。

• [41] 缺失的第一个正数

在常数空间复杂度要求下，需要特殊巧妙的方法，
复用原来的数组空间，利用特殊标记（如负号）进行标记。

• [42] 接雨水

顺序扫描，记录最高点，当前点往前回滚到最高点为止，这个区间的闸门都可以去除。（由于需要回滚，时间复杂度最差为O(n^2)）
题解：
方法1：动态规划（有点），两侧各扫描一次，重叠部分。
方法2：双指针，很巧妙，如果能注意到一侧暂时固定，另一侧的水位高度由这侧的高度决定。（与11题异曲同工。）

• [48] 旋转图像

找规律

• [60] 排列序列

每一位的值是可以计算的，根据排列组合的可能性。

• [65] 有效数字

简单的做法是，正则匹配，但算不上算法。 TODO: 使用编译原理中的有限状态机DFA实现。

• [400] 第-n-位数字

同60题，计算序列。

游戏转化

• [583] 两个字符串的删除操作

游戏规则稍微调整，难度骤降。
转变为了300题，求最长递增子序列。

模拟

• [799] 香槟塔

数学

• [292] nim-游戏

博弈问题

• [877] 石子游戏 (系列)

博弈问题

---

系列

系列-数字求和

• [1] 两数之和

字典
题解：比较有想法的一点是，插入计算的结果，减少后续判断。同时解决了重复元素判断的问题。

• [15] 三数之和

数字类有关大小，都可考虑排序，利用有序，固定一位，另2位前后向中间移动。

• [16] 最接近的三数之和

同上。

• [18] 四数之和

同上，以三数之和扩展。

系列-特殊顺序

• [74] 搜索二维矩阵

同240题

• [240] 搜索二维矩阵-ii

题解从右上角开始，保证了2个方向一个是增，一个是减。

• [496] 下一个更大元素-i

从右向左遍历，使用栈记录较大的元素

系列-转换位运算

• [187] 重复的DNA序列

• [318] 最大单词长度乘积

• [397] 整数替换

系列-数组查找

• [4] 从多个数组找中位数 - 这类有序问题，常常不需要对所有数都遍历，取出总共一半的数即可（题解进一步，只需二分法搜索到总计一半的数即可，时间提升至log）。

• [33] 搜索旋转排序数组

有一定排序，仍需二分查找，需做更多条件处理。

• [34] 在排序数组中查找元素的第一个和最后一个位置

• [35] 搜索插入位置

系列-子串问题

• [3] 无重复最长子串

dict记录每个字母最后出现的位置，每次整体向前蠕动。

• [5] 最长回文子串

方法1：利用对称性，中心扩展法。 （也可以不加'#'凑奇数）
方法2：动态规划，减少重复的回文判断，但内存消耗大。
方法3：不推荐专用算法。

• [28] 子串匹配

KMP。

• [30] 串联所有单词的字串

审题后，发现每个词长度相同，滑动窗口处理。

• [300] 最长递增子序列

• [583] 两个字符串的删除操作

1.游戏转换 2.动态规划 (同1143题)

• [1143] 最长公共子序列

动态规划

• [1218] 最长定差子序列

顺序/逆序都试了，
怎么就老盯着单个元素搜寻，
思维大局观还不够。
每个元素只关心前面扫描过。

系列-成对的符号问题

• [20] 有效括号

堆栈。

• [22] 括号生成

递归。 成对的符号，需要设置左右flag，它们相等时，表示成对。

• [32] 最长有效括号

成对的符号，正反的数量不一样，考虑正反顺序2次遍历。

系列-石子游戏

• [877] 石子游戏

方法1：动态规划，思维转换，将两个人的状态，通过改变游戏规则，转为一个状态。
方法2：数学推理，得出必胜策略。

系列-股票买卖

• [121] 买卖股票的最佳时机

简单的动态规划。

• [122] 买卖股票的最佳时机-ii

贪心法

• [309] 最佳买卖股票时机含冷冻期

题解：多状态转移
主要是理清有多少种状态，
然后是找出其转移方程。

• [714] 买卖股票的最佳时机含手续费

同309题