Leetcode题解索引_网络流 leetcode

Leetcode题解

• 难度等级
• • 简单
  • 中等
  • 困难
  • 算法策略与数据结构专题
  • • 链表双指针
    • 二叉树和递归
    • 快速排序
    • 滚动哈希
    • 字典树
    • 线段树
    • SRQT分解
    • 二分查找
    • 滑动窗口
    • 随机采样算法
  • 其他题解

 

---

难度等级

简单

• [1].俩数之和：枚举、逆向思维+查表、查找表

• [7].整数反转：模拟法、求余法

• [9].回文数：求余法、栈、数组

• [13].罗马数字转整数：查表法、模拟法

• [14].最长公共前缀：双指针

• [20].有效的括号：栈

• [21].合并两个有序链表：双指针交替前进（需要同时遍历两个链表，并且在遍历的过程中根据节点值的大小进行操作）

• [26].删除排序数组中的重复项：双指针

• [27].移除元素：双指针、特殊情况处理

• [53].最大子序和：枚举、枚举优化、动态规划、分治、贪心

• [69].x 的平方根：二分

• [70].爬楼梯：递归、递归+记忆化搜索、动态规划、递推

• [88].合并两个有序数组：双指针

• [100]. 相同的树：深度优先搜索

• [101]. 对称二叉树：深度优先搜索

• [104]. 二叉树的最大深度：回溯、分解子问题

• [110]. 平衡二叉树：深度优先搜索

• [112].路径总和：递归

• [121].买卖股票的最佳时机：模拟法

• [141].判断链表是否有环：快慢指针（需要对链表中的节点进行遍历，并且都涉及到节点之间的相对位置或者距离）

• [155].最小栈：辅助栈、存储、差值、增设变量

• [160].相交链表：双指针相向而行（寻找两个数组或链表中的匹配项）

• [167].两数之和 II - 输入有序数组：二分查找、双指针

• [191].位 1 的个数：枚举、判断一个数字是否是2的幂、查表法

• [198].打家劫舍：递归、递归+记忆化搜索、动态规划

• [203].移除链表元素：哨兵、递归

• [206].反转链表：双指针

• [219].存在重复元素 II：滑动窗口 + 查找表

• [226].翻转二叉树：递归

• [231].2的幂： & 运算

• [237].删除链表中的节点： 链表删除结点的特殊情况，改变值再删除

• [257]. 二叉树的所有路径： 深度优先搜索

• [283].移动零： 排序、快排中位数思路+双指针

• [292].Nim 游戏：余数

• [303].区域和检索 - 数组不可变：线段树（区间树）、SQRT分解

• [401].二进制手表：枚举、回溯

• [404]. 左叶子之和：深度优先搜索

• [447].回旋镖的数量：查找表

• [455].分发饼干：贪心

• [496]. 下一个更大元素 I：单调栈

• [572]. 另一棵树的子树：深度优先搜索

• [590].N叉树的后序遍历：递归、递推

• [617]. 合并二叉树：深度优先搜索

• [623]. 在二叉树中增加一行：深度优先搜索

• [784].字母大小写全排列：递归、递推

• [804].唯一摩尔斯密码词：集合、映射

• [876]. 链表的中间结点：快慢指针（需要对链表中的节点进行遍历，并且需要根据节点之间的相对位置或者距离进行操作）

• [993]. 二叉树的堂兄弟节点：深度优先搜索

• [997].找到小镇法官：度数

• [1022]. 从根到叶的二进制数之和：深度优先搜索

• [2652]. 倍数求和：枚举、容斥原理

• [剑指 Offer 40]. 最小的 k 个数：快排中位数思路、优先队列

 

---

中等

• [3].无重复字符的最长子串：双指针实现滑动窗口

• [5]. 最长回文子串：双指针、Manacher 算法

• [19].删除链表的倒数第 N 个节点：快慢指针（需要对链表中的节点进行遍历，并且都涉及到节点之间的相对位置或者距离）

• [22]. 括号生成：回溯、空间换时间

• [24].两两交换链表中的节点：哨兵、递归

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

• [75].颜色分类：特征是三路分割，方法是使用三指针进行排序，根据当前指针所指的值进行交换

• [86]. 分隔链表：双指针交替前行（需要同时遍历两个链表，并且在遍历的过程中根据节点值的大小进行操作）

• [94]. 二叉树的中序遍历：递归、栈、Morris 中序遍历

• [95]. 不同的二叉搜索树 II：深度优先搜索

• [96]. 不同的二叉搜索树：枚举、动态规划

• [105]. 从前序与中序遍历序列构造二叉树：根节点定位法 + 深度优先搜索生成左右子树

• [106]. 从中序与后序遍历序列构造二叉树：根节点定位法 + 深度优先搜索生成左右子树

• [129]. 求根节点到叶节点数字之和：深度优先搜索

• [130]. 被围绕的区域：深度优先搜索、并查集

• [144].二叉树的前序遍历：递归、迭代、Morris 前序遍历

• [187].重复的 DNA 序列：哈希表、滚动哈希、Rabin-Karp

• [199]. 二叉树的右视图：深度优先搜索

• [208]. 实现 Trie (前缀树)：字典树

• [209].长度最小的子数组：使用两个指针来控制滑动窗口的范围，并通过调整窗口的左右边界来寻找最小连续子数组

• [211]. 添加与搜索单词 - 数据结构设计：字典树支持通配符查询

• [227]. 基本计算器 II：栈

• [307]. 区域和检索 - 数组可修改：线段树（区间树）、SQRT分解

• [319]. 灯泡开关：完全平方数

• [331]. 验证二叉树的前序序列化：度数

• [343].整数拆分：递归、递归+记忆化搜索、动态规划

• [347].前 K 个高频元素：排序、优先队列(最小堆)

• [372]. 超级次方：迭代、递归

• [382]. 链表结点：数组取模、蓄水池抽样

• [384]. 打乱数组：洗牌算法

• [398]. 随机数索引：哈希、蓄水池抽样

• [416].分割等和子集：动态规划

• [429].N 叉树的层序遍历：队列、递归

• [437]. 路径总和 III：深度优先搜索

• [470]. 用 Rand7 实现 Rand10：拒绝采样

• [474]. 一和零：动态规划

• [503]. 下一个更大元素 II：单调栈

• [513]. 找树左下角的值：深度优先搜索

• [528]. 按权重随机选择：加权随机取样

• [677]. 键值映射：字典树实现映射

• [695].岛屿的最大面积：求最大的联通分量个数、Flood Fill算法、并查集

• [752].打开转盘锁：BFS求无权图最短路径

• [785].判断二分图：DFS、BFS

• [877]. 石子游戏：奇偶、动态规划

• [889]. 根据前序和后序遍历构造二叉树：深度优先搜索

• [951]. 翻转等价二叉树：深度优先搜索

• [971]. 翻转二叉树以匹配先序遍历：深度优先搜索

• [988]. 从叶结点开始的最小字符串：深度优先搜索

• [1041].困于环中的机器人：模拟法

• [1091].二进制矩阵中的最短路径：BFS求无权图最短路径、Dijkstra 算法

• [1261]. 在受污染的二叉树中查找元素：深度优先搜索

• [1315]. 祖父节点值为偶数的节点和：深度优先搜索

• [1367]. 二叉树中的链表：深度优先搜索

• [1448]. 统计二叉树中好节点的数目：深度优先搜索

• [1457]. 二叉树中的伪回文路径：深度优先搜索

• [1726]. 同积元组：哈希

• [2530]. 执行 K 次操作后的最大分数：贪心、优先队列
   

---

困难

• [23]. 合并 K 个升序链表：k 个指针分别指向 k 条链表、最小堆快速获取 k 个节点中的最小节点

• [84].柱状图中最大的矩形：枚举、空间换时间

• [124]. 二叉树中的最大路径和：深度优先搜索

• [224]. 基本计算器：栈

• [894]. 所有可能的真二叉树：深度优先搜索

• [980].不同路径 III：DFS+回溯哈密尔顿路径、DFS+状态压缩哈密尔顿路径、DFS+记忆化搜索哈密尔顿路径、动态规划

• [987]. 二叉树的垂序遍历：深度优先搜索

• [998]. 最大二叉树 II：遍历右子节点

• [1147].段式回文：贪心 + 哈希优化、动态规划

• [1392].最长快乐前缀：枚举、Rabin-Karp（哈希优化）、KMP

• [LCP 04].覆盖：网络流最大匹配、匈牙利最大匹配

 

---

算法策略与数据结构专题

链表双指针

• 链表和双指针框架
• 21.合并两个有序链表
• 86.分隔链表
• 23.合并 K 个升序链表
• 19.删除链表的倒数第 N 个结点
• 876.链表的中间结点
• 141.环形链表
• 142.环形链表 II
• 160.相交链表

题目共同特征：

• 双指针交替而行：需要同时遍历两个链表，并且在遍历的过程中根据节点值的大小进行操作
• 快慢指针：需要对链表中的节点进行遍历，并且需要根据节点之间的相对位置或者距离进行操作
• 双指针相向而行：寻找两个数组（或链表）中的匹配项，或者，处理满足特定条件的数组（或链表）中的元素

 

二叉树和递归

• 二叉树的递归模式

• 二分搜索树

• 根到叶路径问题：遍历框架 + 前中后序位置 + 路径记录 + 叶子节点处理：257. 二叉树的所有路径、129. 求根节点到叶节点数字之和、298. 二叉树最长连续序列、988. 从叶结点开始的最小字符串、1022. 从根到叶的二进制数之和、1457. 二叉树中的伪回文路径、617. 合并二叉树

• 98. 验证二叉搜索树

题目共同特征：

• 如果单独抽出一个二叉树节点，它需要做什么事情？需要在什么时候（前/中/后序位置）做？
• 前序位置是进入节点前做
• 中序位置，在一个二叉树节点左子树都遍历完，即将开始遍历右子树的时候执行
• 后序位置是离开右节点（收集完该节点所有子树的信息）后做，在回溯到其父节点之前执行的（返回到它的父节点继续之前的遍历过程，继续执行父节点处的递归调用的下一步）

 

快速排序

• 快速排序

 

滚动哈希

• 滚动哈希

 

字典树

• 实现字典树
• 支持通用匹配
• 支持键值映射

 

线段树

• 区间查询
• 区间更新

 

SRQT分解

• 区间查询
• 区间更新

 

二分查找

• 二分查找

 

滑动窗口

• 3.无重复字符的最长子串
• 209.长度最小的子数组
• 219.存在重复元素 II
• [220].存在重复元素 III

 

随机采样算法

• [398]. 随机数索引（一次采样）

• [528]. 按权重随机选择（加权采样）

• [470]. 用 Rand7 实现 Rand10（拒绝采样）

• [384]. 打乱数组（洗牌算法）

• [382]. 链表结点（蓄水池抽样）

 

---

其他题解

• 【刷题目录】：精选200道题 - Java

• 【Kowalski】：华科大佬 - Python

• 【Debroon】：blog - C

• 【负雪明烛】：blog - Python/C++

• 【Yong Su】：骨灰级用户 - JavaScript

• 【lucifer】：资深工程师 - Java

• 【小浩算法】：公众号 - Golang

• 【看图学算法】：公众号 - java/Python

• 【图解面试算法】：公众号 - Java

• 【B站花花酱】：视频 - C++

• 【labuladong的算法小抄】：文章 - Java

Leetcode的题比较实用，如果求新求变求多元，可以去：

• 【算法竞赛】：Codeforces or 《OJ训练：题目如何安排》

• 【安全竞赛】：CTFhub or XCTF

• 【数据竞赛】：Kaggle

• 【生物竞赛】：Rosalind

• 【软件竞赛】：pass

• 【系统竞赛】：pass

• 【机器人赛】：pass

• 【数学建模】：pass