Skip to content

Latest commit

 

History

History
195 lines (184 loc) · 43.3 KB

SOLUTIONS.md

File metadata and controls

195 lines (184 loc) · 43.3 KB
Raw

灵茶山艾府·高质量题解精选

多数题解配有图片/动画，均包含 Python/Java/C++/Go 等语言。

相同知识点的题目，按照 难度分 排序。

知识点 题目 题解 难度
哈希表 1. 两数之和 【动画】从两数之和中，我们可以学到什么？ 简单
链表 160. 相交链表 【图解】一张图秒懂相交链表！ 简单
2. 两数相加 【动画】简洁写法！从递归到迭代！ 中等
23. 合并 K 个升序链表 两种方法：最小堆/分治 困难
双向链表 146. LRU 缓存 【图解】一张图秒懂 LRU！ 中等
460. LFU 缓存 【图解】一张图秒懂 LFU！ 困难
二叉树 1261. 在受污染的二叉树中查找元素 【图解】两种方法：哈希表/位运算 1440
105. 从前序与中序遍历序列构造二叉树 【图解】从 O(n^2) 到 O(n) 中等
106. 从中序与后序遍历序列构造二叉树 【图解】从 O(n^2) 到 O(n) 中等
889. 根据前序和后序遍历构造二叉树 【图解】从 O(n^2) 到 O(n) 中等
滑动窗口 795. 区间子数组个数 【图解】一次遍历+简洁写法 1817
1658. 将 x 减到 0 的最小操作数 两种写法：逆向思维/直接双指针 1817
1234. 替换子串得到平衡字符串 同向双指针（滑动窗口） 1878
1574. 删除最短的子数组使剩余数组有序 【动画】一写就错？两种写法，总有一种适合你！ 1932
2106. 摘水果 滑动窗口，简洁写法 2062
1782. 统计点对的数目 击败 100%！从双指针到终极优化，十万个查询都不怕！ 2457
二分 275. H 指数 II 【图解】一图掌握二分答案！四种写法！附题单！ 中等
1901. 寻找峰值 II 【图解】利用行最大值判断峰顶位置 中等
878. 第 N 个神奇数字 【图解】二分答案+容斥原理 1897
2594. 修车的最少时间 二分答案+优化（附题单！） 1915
2517. 礼盒的最大甜蜜度 【套路】二分答案！附题单！ 2021
4. 寻找两个正序数组的中位数 【图解】循序渐进：从双指针到二分 困难
2386. 找出数组的第 K 大和 两种方法：二分答案+爆搜/最小堆 2648
技巧性枚举 1638. 统计只差一个字符的子串数目 【图解】非暴力 O(nm) 算法 1745
前后缀分解 1653. 使字符串平衡的最少删除次数 【图解】前后缀分解，消除分支的技巧！（附动态规划） 1794
前缀和 303. 区域和检索 - 数组不可变 前缀和及其扩展，附题单！ 简单
304. 二维区域和检索 - 矩阵不可变 【图解】一张图秒懂二维前缀和！ 中等
1031. 两个非重叠子数组的最大和 【图解】没有思路？一张图秒懂！ 1680
1177. 构建回文串检测 一步步优化！从前缀和到前缀异或和（附题单！） 1848
前缀和与哈希表 面试题 17.05. 字母与数字 【套路】前缀和+哈希表，消除分支的技巧 中等
1590. 使数组和能被 P 整除 【套路】前缀和+哈希表+模运算技巧 2039
差分数组 1094. 拼车 【模板讲解】差分数组 1441
2251. 花期内花的数目 两种方法：二分/差分 2022
2132. 用邮票贴满网格图 【图解】从一维差分到二维差分 2364
单调栈 1019. 链表中的下一个更大节点 【图解单调栈】两种方法，两张图秒懂！ 1571
1124. 表现良好的最长时间段 【图解】两种做法，两张图秒懂！ 1908
907. 子数组的最小值之和 【图解】贡献法+单调栈+三种实现版本 1976
1944. 队列中可以看到的人数 单调栈的本质：及时去掉无用数据 2105
2454. 下一个更大元素 IV O(n) 一次遍历+双单调栈 2175
316. 去除重复字母 跟着我过一遍示例 2，你就明白怎么做了 2185
单调队列 862. 和至少为 K 的最短子数组 【图解】两张图秒懂单调队列 2307
优先队列（堆） 2558. 从数量最多的堆取走礼物 【证明】堆化的时间复杂度 1277
373. 查找和最小的 K 对数字 讲清楚为什么一开始要把 (i,0) 都入堆！ 中等
1439. 有序矩阵中的第 k 个最小数组和 三种算法：暴力/二分答案/堆 2133
857. 雇佣 K 名工人的最低成本 一步步提示如何思考此题 2260
2386. 找出数组的第 K 大和 两种方法：二分答案+爆搜/最小堆 2648
LCP 24. 数字游戏 转换+中位数贪心+对顶堆 困难
位运算 771. 宝石与石头 本题最优解！线性时间+常数空间 1165
1457. 二叉树中的伪回文路径 一步步优化：从数组到位运算 1405
1261. 在受污染的二叉树中查找元素 【图解】两种方法：哈希表/位运算 1440
137. 只出现一次的数字 II 带你一步步推导出位运算公式！ 中等
260. 只出现一次的数字 III 【图解】一张图秒懂！转换成 136！ 中等
421. 数组中两个数的最大异或值 【图解】简洁高效，一图秒懂！ 中等
贡献法 979. 在二叉树中分配硬币 【图解】没有思路？进来秒懂！ 1709
2477. 到达首都的最少油耗 【图解】没有思路？一张图秒懂！ 2012
891. 子序列宽度之和 【图解】计算每个元素对答案的贡献，多解法 2183
动态规划 70. 爬楼梯 教你一步步思考动态规划！ 简单
746. 使用最小花费爬楼梯 教你一步步思考动态规划！ 1358
剑指 Offer 47. 礼物的最大价值 【图解】教你一步步思考动态规划！ 中等
931. 下降路径最小和 教你一步步思考动态规划！ 1573
1155. 掷骰子等于目标和的方法数 击败 100%！教你一步步思考动态规划！ 1654
2304. 网格中的最小路径代价 教你一步步思考动态规划！ 1658
1262. 可被三整除的最大和 教你一步步思考动态规划！ 1762
918. 环形子数组的最大和 【图解】没有思路？一张图秒懂！ 1777
1186. 删除一次得到子数组最大和 教你一步步思考动态规划！ 1799
790. 多米诺和托米诺平铺 【图解】找不到规律？请看图！ 1830
1227. 飞机座位分配概率 【图解】没想明白？一张图秒懂！ 中等
2008. 出租车的最大盈利 教你一步步思考动态规划！ 1872
823. 带因子的二叉树 教你一步步思考动态规划！ 1900
1043. 分隔数组以得到最大和 教你一步步思考动态规划！ 1916
1690. 石子游戏 VII 教你一步步思考动态规划！ 1951
1696. 跳跃游戏 VI 一步步优化：从递归到递推到单调队列 1954
1463. 摘樱桃 II 教你一步步思考动态规划！ 1957
1092. 最短公共超序列 【输出具体方案】从递归到递推，教你一步步思考动态规划！ 1977
940. 不同的子序列 II 细分问题+复杂度优化 1985
1223. 掷骰子模拟 教你一步步思考动态规划！ 2008
1105. 填充书架 教你一步步思考动态规划！ 2014
1235. 规划兼职工作 动态规划+二分查找优化 2023
1335. 工作计划的最低难度 两种思路：动态规划/单调栈 2034
1140. 石子游戏 II 【博弈 DP】教你一步步思考动态规划！ 2035
801. 使序列递增的最小交换次数 考虑相邻元素的大小关系 2066
1976. 到达目的地的方案数 在计算最短路的同时 DP！附题单 2095
1079. 活字印刷 O(n^2) 计数 DP *非暴力
1444. 切披萨的方案数 教你一步步思考动态规划！ 2127
1691. 堆叠长方体的最大高度 【图解】算法优化+详细证明 2172
834. 树中距离之和 【图解】一张图秒懂换根 DP！ 2197
1125. 最小的必要团队 状压 0-1 背包，查表法 vs 刷表法 2251
1997. 访问完所有房间的第一天 前缀和优化 DP 2260
1494. 并行课程 II 子集状压 DP：从记忆化搜索到递推（附题单！） *非暴力
1617. 统计子树中城市之间最大距离 【图解】回溯/二进制枚举/O(n^3)枚举直径端点 2309
1187. 使数组严格递增 最长递增子序列的变形：选或不选/枚举选哪个 2316
2312. 卖木头块 枚举切割位置+循环优化 2363
741. 摘樱桃 教你一步步思考动态规划！ 困难
1349. 参加考试的最大学生数 【图解】状压 DP 的两种状态设计思路 2386
1000. 合并石头的最低成本 【图解】区间 DP：状态设计与优化 2423
1595. 连通两组点的最小成本 教你一步步思考动态规划！（附题单） 2423
1815. 得到新鲜甜甜圈的最多组数 【图解】位运算的魔法 2559
1883. 准时抵达会议现场的最小跳过休息次数 【避免浮点误差】教你一步步思考动态规划！ 2588
2902. 和带限制的子多重集合的数目 多重背包方案数：从朴素 DP 到优化 2758
2809. 使数组和小于等于 x 的最少时间 教你一步步思考本题！ 2979
3225. 网格图操作后的最大分数 【图解】DP 及其优化：从 n^4 到 n^3 到 n^2 3028
数学 50. Pow(x, n) 【图解】一张图秒懂快速幂！ 中等
1954. 收集足够苹果的最小花园周长 【图解】O(1) 做法 1759
1016. 子串能表示从 1 到 N 数字的二进制串 三种算法：从暴力到优化 1779
1015. 可被 K 整除的最小整数 【图解】三种算法+优化 1875
754. 到达终点数字 【图解】分类讨论+详细证明+简洁写法+优化 1880
1884. 鸡蛋掉落-两枚鸡蛋 两种方法：动态规划/数学 中等
1739. 放置盒子 【动画】没想明白？一个动画秒懂！附 O(1) 做法 2198
3102. 最小化曼哈顿距离 【图解】曼哈顿距离转切比雪夫距离 2216
1330. 翻转子数组得到最大的数组值 不会化简？请看这！ 2482
1735. 生成乘积数组的方案数 【图解】质因子分解+放球问题 2500
1819. 序列中不同最大公约数的数目 击败100%！枚举GCD+循环优化 2540
3139. 使数组中所有元素相等的最小开销 分类讨论，O(n) 做法 2666
3235. 判断矩形的两个角落是否可达 【图解】转换成图上 DFS + 避免浮点数的做法
贪心 1144. 递减元素使数组呈锯齿状 没有思路？一步步提示你思考！ 1559
1247. 交换字符使得字符串相同 【图解】没想明白？一张图秒懂！ 1597
870. 优势洗牌 田忌赛马 1648
1402. 做菜顺序 枚举做几道菜+贪心 1679
1145. 二叉树着色游戏 【图解】没有思路？一张图秒懂！ 1741
1262. 可被三整除的最大和 两种算法：贪心/动态规划 1762
134. 加油站 用【折线图】直观理解 中等
1775. 通过最少操作次数使数组的和相等 【动画】没想明白？一个动画秒懂！ 1850
1616. 分割两个字符串得到回文串 【图解】没想明白？一张图秒懂！ 1868
1326. 灌溉花园的最少水龙头数目 【图解】没想明白？一张图秒懂！ 1885
1147. 段式回文 【图解】贪心做法，一图秒懂！ 1912
1798. 你能构造出连续值的最大数目 【图解】没想明白？一张图秒懂！ 1931
1686. 石子游戏 VI 巧妙转换 2001
2136. 全部开花的最早一天 贪心及其证明 2033
630. 课程表 III 贪心还能反悔？ 困难
LCP 24. 数字游戏 转换+中位数贪心+对顶堆 困难
1703. 得到连续 K 个 1 的最少相邻交换次数 【图解】转换成中位数贪心+空间优化 2467
脑筋急转弯 481. 神奇字符串 【动画】一个动画秒懂本题+简洁写法 中等
895. 最大频率栈 【动画】没想明白？一个动画秒懂！ 2028
构造 1605. 给定行和列的和求可行矩阵 【动画】没有思路？一个动画秒懂！附优化写法 1868
思维题 1657. 确定两个字符串是否接近 理解操作本质+简洁写法 1530
1040. 移动石子直到连续 II 【图解】下跳棋 2456
1803. 统计异或值在范围内的数对有多少 【图解】不会字典树？只用哈希表也能做！ 2479
782. 变为棋盘 【图解】逆向思维 困难
网格图 面试题 16.19. 水域大小 【模板】网格图 DFS（附题单！） 中等
1254. 统计封闭岛屿的数目 【动画】两种思路：先外后内/出界标记（附题单！） 1659
2258. 逃离火灾 【图解】两种方法：二分答案 / 直接计算 2347
树 1376. 通知所有员工所需的时间 深入理解递归：自顶向下/自底向上（附 O(1) 空间迭代写法！） 1561
1377. T 秒后青蛙的位置 DFS + 一次有趣的 hack 1824
2003. 每棵子树内缺失的最小基因值 【图解】一张图秒懂！多种写法！ 2415
图 DFS 924. 尽量减少恶意软件的传播 只包含一个被感染节点的最大连通块 1869
928. 尽量减少恶意软件的传播 II 逆向思维 1985
最短路 1824. 最少侧跳次数 从 0 到 1 的 0-1 BFS 1778
1334. 阈值距离内邻居最少的城市 【Floyd 模板】带你发明 Floyd 算法：从记忆化搜索到递推 1885
1210. 穿过迷宫的最少移动次数 【诗】还在 if-else？一个循环处理六种移动！ 2022
1976. 到达目的地的方案数 【Dijkstra 模板】在计算最短路的同时 DP！附题单 2095
882. 细分图中的可到达节点 【图解】转换成单源最短路问题 2328
基环树 2127. 参加会议的最多员工数 【图解】内向基环树：拓扑排序 + 分类讨论 2449
LCA 1483. 树节点的第 K 个祖先 【模板讲解】树上倍增算法（以及最近公共祖先） 2115
树状数组 307. 区域和检索 - 数组可修改 【模板讲解】带你发明树状数组！附数学证明 中等

更多题目请看【基础算法精讲】题目列表

分类题单

🔥如何科学刷题？

  1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
  2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
  3. 单调栈（基础/矩形面积/贡献法/最小字典序）
  4. 网格图（DFS/BFS/综合应用）
  5. 位运算（基础/性质/拆位/试填/恒等式/思维）
  6. 图论算法（DFS/BFS/拓扑排序/最短路/最小生成树/二分图/基环树/欧拉路径）
  7. 🔥动态规划（入门/背包/状态机/划分/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
  8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
  9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
  10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
  11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
  12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

周赛总结

其他