LeetcodeTop100 刷题总结（二）
LeetCode 热题 100：https://leetcode.cn/studyplan/top-100-liked/
文章目录
- 八、二叉树
- 94. 二叉树的中序遍历（递归与非递归）
- 补充：144. 二叉树的前序遍历（递归与非递归）
- 补充：145. 二叉树的后序遍历（递归与非递归）
- 104. 二叉树的最大深度
- 226. 翻转二叉树
- 101. 对称二叉树
- 543. 二叉树的直径
- 102. 二叉树的层序遍历
- 108. 将有序数组转换为二叉搜索树
- 98. 验证二叉搜索树
- 230. 二叉搜索树中第 K 小的元素
- 199. 二叉树的右视图
- 114. 二叉树展开为链表
- 105. 从前序与中序遍历序列构造二叉树
- 补充：106. 从中序与后序遍历序列构造二叉树
- 437. 路径总和 III
- 补充：112. 路径总和
- 补充：113. 路径总和 II
- 236. 二叉树的最近公共祖先
- 124. 二叉树中的最大路径和
- 九、图论
- 十、回溯
八、二叉树
二叉树的定义：
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
94. 二叉树的中序遍历（递归与非递归）
递归方式：
class Solution {
List<Integer> res = new ArrayList<>();
/**
* 输入：root = [1,null,2,3]
* 输出：[1,3,2]
*/
public List<Integer> inorderTraversal(TreeNode root) {
InOrder(root);
return res;
}
public void InOrder(TreeNode root){
if(root != null){
InOrder(root.left);
res.add(root.val);
InOrder(root.right);
}
}
}
非递归方式：
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
Deque<TreeNode> stack = new LinkedList<>(); // 双端队列模拟栈
List<Integer> list = new ArrayList<>();
TreeNode p = root;
while(p != null || !stack.isEmpty()){
if(p != null){
stack.push(p);
p = p.left;
}else{
p = stack.pop();
list.add(p.val);
p = p.right;
}
}
return list;
}
}
补充：144. 二叉树的前序遍历（递归与非递归）
题目链接：https://leetcode.cn/problems/binary-tree-preorder-traversal/description/
递归做法：
class Solution {
List<Integer> list = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
preOrder(root);
return list;
}
public void preOrder(TreeNode root){
if(root != null){
list.add(root.val);
preOrder(root.left);
preOrder(root.right);
}
}
}
非递归做法：
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
Deque<TreeNode> stack = new LinkedList<>(); // 双端队列模拟栈
List<Integer> list = new ArrayList<>();
TreeNode p = root;
while(p != null || !stack.isEmpty()){
if(p != null){
list.add(p.val);
stack.push(p);
p = p.left;
}else{
p = stack.pop();
p = p.right;
}
}
return list;
}
}
补充：145. 二叉树的后序遍历（递归与非递归）
题目链接：https://leetcode.cn/problems/binary-tree-postorder-traversal/description/
递归做法：
class Solution {
List<Integer> list = new ArrayList<>();
public List<Integer> postorderTraversal(TreeNode root) {
postOrder(root);
return list;
}
public void postOrder(TreeNode root){
if(root != null){
postOrder(root.left);
postOrder(root.right);
list.add(root.val);
}
}
}
非递归做法：
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Deque<TreeNode> stack = new LinkedList<>();
TreeNode p, r;
p = root;
r = null;
while(p != null || !stack.isEmpty()){
if(p != null){ // 走到最左边
stack.push(p);
p = p.left;
}else{ // 向右
p = stack.peek(); // 得到栈顶元素
if(p.right != null && p.right != r){ // 右子树存在，且未访问
p = p.right;
}else{ // 否则弹出节点并访问
p = stack.pop();
list.add(p.val);
r = p; // 记录最近访问节点
p = null; // 节点访问后，重置 p
}
}
}
return list;
}
}
104. 二叉树的最大深度
class Solution {
/**
* 输入：root = [3,9,20,null,null,15,7]
* 输出：3
*/
public int maxDepth(TreeNode root) {
return getMaxDepth(root);
}
private int getMaxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int left = getMaxDepth(root.left);
int right = getMaxDepth(root.right);
return Math.max(left, right) + 1;
}
}
226. 翻转二叉树
class Solution {
public TreeNode invertTree(TreeNode root) {
reverseTree(root);
return root;
}
private void reverseTree(TreeNode root) {
if (root == null) {
return;
}
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
reverseTree(root.left);
reverseTree(root.right);
}
}
101. 对称二叉树
class Solution {
/**
* 输入：root = [1,2,2,3,4,4,3]
* 输出：true
*/
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return recur(root.left, root.right);
}
public boolean recur(TreeNode l, TreeNode r) {
if (l == null && r == null) {
return true;
}
if (l == null || r == null || l.val != r.val) {
return false;
}
return recur(l.left, r.right) && recur(l.right, r.left);
}
}
543. 二叉树的直径
class Solution {
int diam;
/**
* 输入：root = [1,2,3,4,5]
* 输出：3
* 解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
*/
public int diameterOfBinaryTree(TreeNode root) {
getMaxDepth(root);
return diam;
}
public int getMaxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int left = getMaxDepth(root.left);
int right = getMaxDepth(root.right);
diam = Math.max(diam, left + right);
return Math.max(left, right) + 1;
}
}
102. 二叉树的层序遍历
思路：使用 Deque 模拟队列数据结构，每次进队将一层节点出队，并将下一层节点进队。
class Solution {
/**
* 输入：root = [3,9,20,null,null,15,7]
* 输出：[[3],[9,20],[15,7]]
*/
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
Deque<TreeNode> queue = new LinkedList<>();
if (root != null) {
queue.add(root);
}
while (!queue.isEmpty()) {
int size = queue.size(); // 当前队列中节点数量 size
List<Integer> list = new ArrayList<>();
for (int i = size; i > 0; i--) { // 循环 size 次，存储该层节点
TreeNode node = queue.remove();
list.add(node.val);
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
res.add(list);
}
return res;
}
}
注意：每次循环提前求出队列中节点数量，是因为如果没有提前求出 for (int i = 0; i < queue.size; i++)，由于队列的节点数量是变化的，循环结束的条件会发生变化。
108. 将有序数组转换为二叉搜索树
题意要求：将有序数组转换为 平衡 二叉搜索树，这里可以借鉴二分查找的思路。
class Solution {
/**
* 输入：nums = [-10,-3,0,5,9]
* 输出：[0,-3,9,-10,null,5]
* 解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案
*/
public TreeNode sortedArrayToBST(int[] nums) {
return buildBST(nums, 0, nums.length - 1);
}
private TreeNode buildBST(int[] nums, int left, int right) {
if (left > right) {
return null;
}
int mid = left - (left - right) / 2; // 防溢出
TreeNode node = new TreeNode(nums[mid]);
node.left = buildBST(nums, left, mid - 1);
node.right = buildBST(nums, mid + 1, right);
return node;
}
}
98. 验证二叉搜索树
思路：二叉搜索树中序遍历是递增的，因此可以利用栈辅助完成中序遍历的同时来验证是否是二叉搜索树。
class Solution {
/**
* 输入：root = [2,1,3]
* 输出：true
*/
public boolean isValidBST(TreeNode root) {
Deque<TreeNode> stack = new LinkedList<>();
long val = Long.MIN_VALUE;
TreeNode p = root;
while (!stack.isEmpty() || p != null) {
if (p != null) {
stack.push(p);
p = p.left;
} else {
TreeNode top = stack.pop();
if (val >= top.val) {
return false;
}
val = top.val;
p = top.right;
}
}
return true;
}
}
也可使用递归的思路：
class Solution {
long max = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
if(root == null){
return true;
}
if(!isValidBST(root.left)){
return false;
}
if(root.val <= max){
return false;
}else{
max = root.val;
}
return isValidBST(root.right);
}
}
230. 二叉搜索树中第 K 小的元素
思路同上，使用栈进行中序遍历的同时，查询第 K 小的元素。
class Solution {
/**
* 输入：root = [3,1,4,null,2], k = 1
* 输出：1
*/
public int kthSmallest(TreeNode root, int k) {
Deque<TreeNode> stack = new LinkedList<>();
TreeNode p = root;
while (!stack.isEmpty() || p != null) {
if (p != null) {
stack.push(p);
p = p.left;
} else {
p = stack.pop();
if (--k == 0) {
return p.val;
}
p = p.right;
}
}
return 0;
}
}
199. 二叉树的右视图
借鉴层序遍历算法，每次取每一层最后一个元素。
class Solution {
/**
* 输入: [1,2,3,null,5,null,4]
* 输出: [1,3,4]
*/
public List<Integer> rightSideView(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
Deque<TreeNode> queue = new LinkedList<>();
List<Integer> res = new ArrayList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = size; i > 0; i--) {
TreeNode node = queue.remove();
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
if (i == 1) {
res.add(node.val);
}
}
}
return res;
}
}
114. 二叉树展开为链表
思路：
① 将左子树的最右节点指向右子树的根节点；
② 将左子树接到右子树的位置；
③ 处理右子树的根节点。
一直重复上边的过程，直到新的右子树为 null。
class Solution {
/**
* 输入：root = [1,2,5,3,4,null,6]
* 输出：[1,null,2,null,3,null,4,null,5,null,6]
*/
public void flatten(TreeNode root) {
TreeNode p = root;
while (p != null) {
if (p.left != null) {
TreeNode pLeft = p.left;
TreeNode pLeftRight = p.left;
while (pLeftRight.right != null) { // 查询左子树的最右节点
pLeftRight = pLeftRight.right;
}
pLeftRight.right = p.right;
p.right = pLeft;
p.left = null;
}
p = p.right;
}
}
}
105. 从前序与中序遍历序列构造二叉树
思路：团体程序设计天梯赛-练习集 L2-011 玩转二叉树 (25分) 先序中序建树 思路详解
class Solution {
/**
* 输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
* 输出: [3,9,20,null,null,15,7]
*/
public TreeNode buildTree(int[] preorder, int[] inorder) { // 先序，中序
return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
}
/**
* 先序中序构建二叉树
*
* @param preorder 先序遍历
* @param preLeft 先序左边界
* @param preRight 先序右边界
* @param inorder 中序遍历
* @param inLeft 中序左边界
* @param inRight 中序右边界
* @return 根节点
*/
public TreeNode build(int[] preorder, int preLeft, int preRight, int[] inorder, int inLeft, int inRight) {
if (inLeft > inRight || preLeft > preRight) {
return null;
}
TreeNode root = new TreeNode(preorder[preLeft]); // 先序遍历的第一个节点是根节点
int rootInd = inLeft; // root 代表中序遍历数组中的根节点的索引
for (int i = inLeft; i <= inRight; i++) {
if (inorder[i] == preorder[preLeft]) {
rootInd = i;
break;
}
}
int len = rootInd - inLeft; // 左子树的长度
// 先序（根左右）：左边界+1、左边界+长度，中序（左根右）：左边界、根节点位置-1
root.left = build(preorder, preLeft + 1, preLeft + len, inorder, inLeft, rootInd - 1);
// 先序（根左右）：左边界+长度+1、右边界，中序（左根右）：根节点位置+1、右边界
root.right = build(preorder, preLeft + len + 1, preRight, inorder, rootInd + 1, inRight);
return root;
}
}
补充：106. 从中序与后序遍历序列构造二叉树
题目链接：https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/
class Solution {
/**
* 输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
* 输出：[3,9,20,null,null,15,7]
*/
public TreeNode buildTree(int[] inorder, int[] postorder) {
return build(postorder, 0, postorder.length - 1, inorder, 0, inorder.length - 1);
}
/**
* 后序中序构建二叉树
*
* @param postorder 后序遍历
* @param postLeft 后序左边界
* @param postRight 后序右边界
* @param inorder 中序遍历
* @param inLeft 中序左边界
* @param inRight 中序右边界
* @return 根节点
*/
private TreeNode build(int[] postorder, int postLeft, int postRight, int[] inorder, int inLeft, int inRight) {
if (postLeft > postRight || inLeft > inRight) {
return null;
}
TreeNode root = new TreeNode(postorder[postRight]);
int rootInd = inLeft;
for (int i = inLeft; i <= inRight; i++) {
if(inorder[i] == postorder[postRight]){
rootInd = i;
break;
}
}
int len = rootInd - inLeft; // 左子树节长度
// 后序（左右根）：左边界、左边界+长度-1；中序（左根右）：左边界、根节点位置-1
root.left = build(postorder, postLeft, postLeft + len -1, inorder, inLeft, rootInd-1);
// 后序（左右根）：左边界+长度、右边界-1，中序（左根右）：根节点位置+1、右边界
root.right = build(postorder, postLeft + len, postRight-1, inorder, rootInd + 1, inRight);
return root;
}
}
437. 路径总和 III
思路：以当前节点为止，每次去查看之前的的 map 集合中是否还存在目标前缀和。
①
/
②
/
③
假设目标和为 5，节点 1 的前缀和为：1，节点 3 的前缀和为: 1+2+3 = 6，那么 pre(3) - pre(1) = 5
所以从节点 1 到节点 3 之间有一条路径长度为 5。
class Solution {
// key:前缀和，value:前缀和的数量（状态会恢复）
Map<Long, Integer> map;
/**
* 输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
* 输出：3
* 解释：和等于 8 的路径有 3 条
*/
public int pathSum(TreeNode root, int targetSum) {
map = new HashMap<>();
map.put(0l, 1);
return backtrack(root, 0L, targetSum);
}
private int backtrack(TreeNode root, Long curr, int target) {
if (root == null) {
return 0;
}
int res = 0;
curr += root.val;
// 以当前节点为止，去查看从前的 map 集合中是否还存在目标前缀和
res += map.getOrDefault(curr - target, 0);
// 存储路径的原因是可能节点的前缀和存在相等的情况：
// 2
// /
// 0
// /
// 4
// 从节点 2 到节点 4 有两条路径长度等于2
map.put(curr, map.getOrDefault(curr, 0) + 1);
int left = backtrack(root.left, curr, target);
int right = backtrack(root.right, curr, target);
res += left + right;
// 状态恢复
map.put(curr, map.get(curr) - 1);
return res;
}
}
补充：112. 路径总和
题目链接：https://leetcode.cn/problems/path-sum/description/
class Solution {
/**
* 输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
* 输出：true
* 解释：等于目标和的根节点到叶节点路径如上图所示
*/
public boolean hasPathSum(TreeNode root, int targetSum) {
return backtrack(root, 0, targetSum);
}
private boolean backtrack(TreeNode root, int curr, int target) {
if (root == null) {
return false;
}
curr += root.val;
if (root.left == null && root.right == null) {
return curr == target;
}
boolean left = backtrack(root.left, curr, target);
boolean right = backtrack(root.right, curr, target);
return left || right;
}
}
补充：113. 路径总和 II
题目链接：https://leetcode.cn/problems/path-sum-ii/description/
class Solution {
List<List<Integer>> res;
/**
* 输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
* 输出：[[5,4,11,2],[5,8,4,5]]
*/
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
res = new ArrayList<>();
backtrack(root, 0, targetSum, new ArrayList<>());
return res;
}
private void backtrack(TreeNode root, int curr, int target, List<Integer> path) {
if (root == null) {
return;
}
curr += root.val;
path.add(root.val);
if (root.left == null && root.right == null && curr == target) {
res.add(new ArrayList<>(path));
}
backtrack(root.left, curr, target, path);
backtrack(root.right, curr, target, path);
path.remove(path.size() - 1); // 恢复状态
}
}
236. 二叉树的最近公共祖先
思路参考：236. 二叉树的最近公共祖先（DFS ，清晰图解）
class Solution {
/**
* 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
* 输出：3
* 解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
*/
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
return dfs(root, p, q);
}
private TreeNode dfs(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return null;
}
if (root == p || root == q) {
return root;
}
TreeNode left = dfs(root.left, p, q);
TreeNode right = dfs(root.right, p, q);
if (left != null && right != null) {
return root;
} else if (left != null) {
return left;
} else if (right != null) {
return right;
} else {
return null;
}
}
}
124. 二叉树中的最大路径和
class Solution {
private int maxPath = Integer.MIN_VALUE;
/**
* 输入：root = [-10,9,20,null,null,15,7]
* 输出：42
* 解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
*/
public int maxPathSum(TreeNode root) {
getMaxPath(root);
return maxPath;
}
private int getMaxPath(TreeNode root) {
if (root == null) {
return 0;
}
int leftMaxPath = Math.max(0, getMaxPath(root.left));
int rightMaxPath = Math.max(0, getMaxPath(root.right));
maxPath = Math.max(leftMaxPath + root.val + rightMaxPath, maxPath);
return Math.max(leftMaxPath, rightMaxPath) + root.val;
}
}
九、图论
200. 岛屿数量
class Solution {
/**
* 输入：grid = [
* ["1","1","1","1","0"],
* ["1","1","0","1","0"],
* ["1","1","0","0","0"],
* ["0","0","0","0","0"]
* ]
* 输出：1
*/
public int numIslands(char[][] grid) {
int m = grid.length;
int n = grid[0].length;
int res = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
dfs(grid, i, j, m, n);
res++;
}
}
}
return res;
}
private void dfs(char[][] grid, int x, int y, int m, int n) {
if (0 <= x && x < m && 0 <= y && y < n && grid[x][y] == '1') {
grid[x][y] = '0';
dfs(grid, x, y - 1, m, n); // 左上右下
dfs(grid, x - 1, y, m, n);
dfs(grid, x, y + 1, m, n);
dfs(grid, x + 1, y, m, n);
}
}
}
994. 腐烂的橘子
思路：遍历的方式参考树的层序遍历，区别在于题目刚开始的入队的节点可能有多个。
class Solution {
/**
* 输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
* 输出：4
*/
public int orangesRotting(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
Deque<Point> queue = new LinkedList<>();
int flesh = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) {
queue.add(new Point(i, j));
}
if (grid[i][j] == 1) {
flesh++;
}
}
}
if (flesh == 0) {
return 0;
}
int res = 0;
int[][] dirs = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}}; // 左上右下四个方向
while (!queue.isEmpty() && flesh > 0) { // 注意：如果不用 flesh 做判断，队列中还存在节点，因此还会再循环一轮
int size = queue.size();
res++;
for (int i = size; i > 0; i--) {
Point point = queue.remove();
int x = point.x;
int y = point.y;
for (int[] dir : dirs) {
int newX = x + dir[0];
int newY = y + dir[1];
if (0 <= newX && newX < m && 0 <= newY && newY < n && grid[newX][newY] == 1) {
grid[newX][newY] = 2;
flesh--;
queue.add(new Point(newX, newY));
}
}
}
}
return flesh == 0 ? res : -1;
}
class Point {
int x;
int y;
public Point() {
}
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
}
207. 课程表
思路：拓扑排序
class Solution {
/**
* 输入：numCourses = 2, prerequisites = [[1,0]]
* 输出：true
* 解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
*/
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<List<Integer>> neighborTable = buildNeighborTable(numCourses, prerequisites);
Deque<Integer> stack = new LinkedList<>(); // 用来存储入度为0的节点
int count = 0; // 用来记录拓扑排序中的节点数量
int[] indegree = new int[numCourses]; // 存储每个节点的入度
for (int[] prerequisite : prerequisites) {
indegree[prerequisite[0]]++;
}
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) {
stack.push(i);
}
}
while (!stack.isEmpty()) {
Integer pop = stack.pop();
count++;
for (Integer ind : neighborTable.get(pop)) { // 邻接表中当前节点所关联的节点入度-1
indegree[ind]--;
if (indegree[ind] == 0) {
stack.push(ind);
}
}
}
return count == numCourses;
}
private List<List<Integer>> buildNeighborTable(int numCourses, int[][] prerequisites) {
List<List<Integer>> neighborTable = new ArrayList<>(numCourses);
for (int i = 0; i < numCourses; i++) {
neighborTable.add(new ArrayList<>());
}
for (int i = 0; i < prerequisites.length; i++) { // 构造邻接表
neighborTable.get(prerequisites[i][1]).add(prerequisites[i][0]);
}
return neighborTable;
}
}
补充：210. 课程表 II
题目链接：https://leetcode.cn/problems/course-schedule-ii/description/
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
List<List<Integer>> neighborTable = buildNeighborTable(numCourses, prerequisites);
Deque<Integer> stack = new LinkedList<>(); // 用来存储入度为0的节点
int count = 0; // 用来记录拓扑排序中的节点数量
int[] topologies = new int[numCourses];
int[] indegree = new int[numCourses]; // 存储每个节点的入度
for (int[] prerequisite : prerequisites) {
indegree[prerequisite[0]]++;
}
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) {
stack.push(i);
}
}
while (!stack.isEmpty()) {
Integer pop = stack.pop();
topologies[count++] = pop;
for (Integer ind : neighborTable.get(pop)) { // 邻接表中当前节点所关联的节点入度-1
indegree[ind]--;
if (indegree[ind] == 0) {
stack.push(ind);
}
}
}
return count == numCourses ? topologies : new int[0];
}
private List<List<Integer>> buildNeighborTable(int numCourses, int[][] prerequisites) {
List<List<Integer>> neighborTable = new ArrayList<>(numCourses);
for (int i = 0; i < numCourses; i++) {
neighborTable.add(new ArrayList<>());
}
for (int i = 0; i < prerequisites.length; i++) { // 构造邻接表
neighborTable.get(prerequisites[i][1]).add(prerequisites[i][0]);
}
return neighborTable;
}
}
208. 实现 Trie (前缀树)
class Trie {
class Node {
Boolean isEnd;
Node[] next;
public Node() {
this.isEnd = false;
this.next = new Node[26];
}
}
private final Node root;
public Trie() {
root = new Node();
}
public void insert(String word) {
Node node = root;
for (char ch : word.toCharArray()) {
if (node.next[ch - 'a'] == null) {
node.next[ch - 'a'] = new Node();
}
node = node.next[ch - 'a'];
}
node.isEnd = true;
}
public boolean search(String word) {
Node node = root;
for (char ch : word.toCharArray()) {
if (node.next[ch - 'a'] == null) {
return false;
}
node = node.next[ch - 'a'];
}
return node.isEnd;
}
public boolean startsWith(String prefix) {
Node node = root;
for (char ch : prefix.toCharArray()) {
if (node.next[ch - 'a'] == null) {
return false;
}
node = node.next[ch - 'a'];
}
return true;
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* boolean param_2 = obj.search(word);
* boolean param_3 = obj.startsWith(prefix);
*/
十、回溯
46. 全排列
题目：给定一个 不含重复数字 的数组 nums ，返回其所有可能的全排列。你可以按任意顺序返回答案。
class Solution {
/**
* 输入：nums = [1,2,3]
* 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
*/
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
int len = nums.length;
boolean[] visited = new boolean[len];
dfs(res, nums, visited, new ArrayList<>());
return res;
}
private void dfs(List<List<Integer>> res, int[] nums, boolean[] visited, List<Integer> list) {
if (list.size() == nums.length) {
res.add(new ArrayList<>(list));
return;
}
for (int i = 0; i < nums.length; i++) {
if (!visited[i]) {
list.add(nums[i]);
visited[i] = true;
dfs(res, nums, visited, list);
list.remove(list.size() - 1);
visited[i] = false;
}
}
}
}
补充：47. 全排列 II
题目链接：https://leetcode.cn/problems/permutations-ii/
题目：给定一个 包含重复数字 的数组 nums ，返回其所有可能的全排列。你可以按任意顺序返回答案。
class Solution {
/**
* 输入：nums = [1,1,2]
* 输出：[[1,1,2],[1,2,1],[2,1,1]]
*/
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums); // 排序
boolean[] visited = new boolean[nums.length];
backtrack(visited, nums, new ArrayList<>(), res);
return res;
}
private void backtrack(boolean[] visited, int[] nums, List<Integer> list, List<List<Integer>> res) {
if (list.size() == nums.length) {
res.add(new ArrayList<>(list));
return;
}
for (int i = 0; i < nums.length; i++) {
if (!visited[i]) {
if (i > 0 && nums[i] == nums[i - 1] && visited[i - 1] == false) { // 剪枝
continue;
}
visited[i] = true;
list.add(nums[i]);
backtrack(visited, nums, list, res);
list.remove(list.size() - 1);
visited[i] = false;
}
}
}
}
78. 子集
class Solution {
/**
* 输入：nums = [1,2,3]
* 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
*/
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
int len = nums.length;
boolean[] visited = new boolean[len];
dfs(nums, 0, new ArrayList<>(), res);
return res;
}
private void dfs(int[] nums, int ind, List<Integer> list, List<List<Integer>> res) {
if (ind >= nums.length) {
res.add(new ArrayList<>(list));
return;
}
list.add(nums[ind]);
dfs(nums, ind + 1, list, res);
list.remove(list.size() - 1);
dfs(nums, ind + 1, list, res);
}
}
17. 电话号码的字母组合
class Solution {
Map<Character, String> map = new HashMap<>();
String digits;
/**
* 输入：digits = "23"
* 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
*/
public List<String> letterCombinations(String digits) {
if (digits.length() == 0) {
return new ArrayList<>();
}
map.put('2', "abc");
map.put('3', "def");
map.put('4', "ghi");
map.put('5', "jkl");
map.put('6', "mno");
map.put('7', "pqrs");
map.put('8', "tuv");
map.put('9', "wxyz");
this.digits = digits;
List<String> res = new ArrayList<>();
backtrack(0, new StringBuilder(), res);
return res;
}
private void backtrack(int ind, StringBuilder builder, List<String> res) {
if (ind == digits.length()) {
res.add(new String(builder));
return;
}
String words = map.get(digits.charAt(ind));
for (char ch : words.toCharArray()) {
builder.append(ch);
backtrack(ind+1, builder, res);
builder.deleteCharAt(builder.length() - 1);
}
}
}
39. 组合总和
题目： 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
class Solution {
int[] candidates;
/**
* 输入：candidates = [2,3,6,7], target = 7
* 输出：[[2,2,3],[7]]
* 解释：
* 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
* 7 也是一个候选， 7 = 7 。
* 仅有这两种组合。
*/
public List<List<Integer>> combinationSum(int[] candidates, int target) {
this.candidates = candidates;
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(candidates);
backtrack(target, 0, new ArrayList<>(), res);
return res;
}
private void backtrack(int target, int ind, List<Integer> temp, List<List<Integer>> res) {
if (target < 0) {
return;
}
if (target == 0) {
res.add(new ArrayList<>(temp));
return;
}
for (int i = ind; i < candidates.length; i++) {
if (target - candidates[i] < 0) {
break;
}
temp.add(candidates[i]);
backtrack(target - candidates[i], i, temp, res);
temp.remove(temp.size() - 1);
}
}
}
补充：40. 组合总和 II
题目链接：https://leetcode.cn/problems/combination-sum-ii/description/
与上道题目不同的是，解集不能包含重复的组合， 参考：全排列 II：
class Solution {
int[] candidates;
/**
* 输入: candidates = [10,1,2,7,6,1,5], target = 8,
* 输出: [[1,1,6],[1,2,5],[1,7],[2,6]]
*/
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
this.candidates = candidates;
List<List<Integer>> res = new ArrayList<>();
boolean[] visited = new boolean[candidates.length];
Arrays.sort(candidates);
backtrack(target, 0, visited, new ArrayList<>(), res);
return res;
}
private void backtrack(int target, int ind, boolean[] visited, List<Integer> list, List<List<Integer>> res) {
if (target < 0) {
return;
}
if (target == 0) {
res.add(new ArrayList<>(list));
return;
}
for (int i = ind; i < candidates.length; i++) {
if (!visited[i]) {
if (target - candidates[i] < 0) {
break;
}
if (i != 0 && candidates[i - 1] == candidates[i] && !visited[i - 1]) {
continue;
}
list.add(candidates[i]);
visited[i] = true;
backtrack(target - candidates[i], i + 1, visited, list, res);
visited[i] = false;
list.remove(list.size() - 1);
}
}
}
}
补充：216. 组合总和 III
题目链接：https://leetcode.cn/problems/combination-sum-iii/description/
题目：找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
① 只使用数字 1 到 9
② 每个数字最多使用一次
③ 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
class Solution {
List<List<Integer>> res;
int size;
/**
* 输入: k = 3, n = 7
* 输出: [[1,2,4]]
* 解释: 1 + 2 + 4 = 7 没有其他符合的组合了。
*/
public List<List<Integer>> combinationSum3(int k, int n) {
this.res = new ArrayList<>();
this.size = k;
backtrack(1, n, new ArrayList<>());
return res;
}
private void backtrack(int ind, int target, List<Integer> list) {
if (target == 0) {
if (size == list.size()) {
res.add(new ArrayList<>(list));
}
return;
}
for (int i = ind; i < 10; i++) {
if (target - i < 0) {
break;
}
list.add(i);
backtrack(i + 1, target - i, list);
list.remove(list.size() - 1);
}
}
}
22. 括号生成
思路：每次优先选左括号，然后再选右括号。
class Solution {
/**
* 输入：n = 3
* 输出：["((()))","(()())","(())()","()(())","()()()"]
*/
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
backtrack(n, n, new StringBuilder(), res);
return res;
}
private void backtrack(int left, int right, StringBuilder builder, List<String> res) {
if (left > right) { // 左括号少，剪枝
return;
}
if (left == 0 && right == 0) {
res.add(builder.toString());
return;
}
if (left != 0) { // 优先选左
builder.append('(');
backtrack(left - 1, right, builder, res);
builder.deleteCharAt(builder.length() - 1);
}
builder.append(')');
backtrack(left, right - 1, builder, res);
builder.deleteCharAt(builder.length() - 1);
}
}
79. 单词搜索
class Solution {
/**
* 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
* 输出：true
*/
public boolean exist(char[][] board, String word) {
int m = board.length;
int n = board[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == word.charAt(0) && dfs(word, i, j, 0, board)) {
return true;
}
}
}
return false;
}
private boolean dfs(String word, int x, int y, int ind, char[][] board) {
if (ind >= word.length()) {
return true;
}
if (0 <= x && x < board.length && 0 <= y && y < board[0].length && board[x][y] == word.charAt(ind)
&& board[x][y] != '\0') {
char ch = board[x][y];
board[x][y] = '\0';
boolean left = dfs(word, x, y - 1, ind + 1, board); // 左上右下
boolean up = dfs(word, x - 1, y, ind + 1, board);
boolean right = dfs(word, x, y + 1, ind + 1, board);
boolean down = dfs(word, x + 1, y, ind + 1, board);
board[x][y] = ch;
return left || up || right || down;
}
return false;
}
}
131. 分割回文串
class Solution {
List<List<String>> res;
public List<List<String>> partition(String s) {
res = new ArrayList<>();
backtrack(s, 0, new ArrayList<>());
return res;
}
private void backtrack(String s, int ind, List<String> list) {
if (ind >= s.length()) {
res.add(new ArrayList<>(list));
return;
}
for (int i = ind; i < s.length(); i++) {
if (isPalindrome(s, ind, i)) {
list.add(s.substring(ind, i + 1));
backtrack(s, i + 1, list);
list.remove(list.size() - 1);
}
}
}
private boolean isPalindrome(String s, int start, int end) {
while (start <= end) {
if (s.charAt(start) != s.charAt(end)) {
return false;
}
start++;
end--;
}
return true;
}
}
51. N 皇后
class Solution {
/**
* 输入：n = 4
* 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
* 解释：如上图所示，4 皇后问题存在两个不同的解法。
*/
public List<List<String>> solveNQueens(int n) {
List<List<String>> res = new ArrayList<>();
int[] queenCols = new int[n]; // {1,3,0,2} 存储第i行的皇后在第 queenCols.get(i) 列
dfs(0, n, queenCols, res);
return res;
}
private List<String> convert(int[] queenCols, int n) {
List<String> solution = new ArrayList<>();// {1,3,0,2} -> [".Q..","...Q","Q...","..Q."],
for (Integer col : queenCols) {
char[] temp = new char[n];
Arrays.fill(temp, '.');
temp[col] = 'Q';
solution.add(new String(temp));
}
return solution;
}
private void dfs(int row, int n, int[] queenCols, List<List<String>> res) {
if (row == n) {
res.add(convert(queenCols, n));
return;
}
for (int col = 0; col < n; col++) { // 对当前行的每一列进行遍历
if (!isValid(queenCols, row, col)) {
continue;
}
queenCols[row] = col;
dfs(row + 1, n, queenCols, res);
queenCols[row] = -1;
}
}
private boolean isValid(int[] queenCols, int row, int col) {
for (int i = 0; i < row; i++) {
if (queenCols[i] == col || row - i == col - queenCols[i] || row - i == queenCols[i] - col) {
// 同一列；同'\'方向，“行-皇后所在行 == 列-皇后所在列”；同'/'方向，“行-皇后所在行 == 皇后所在列-列”
return false;
}
}
return true;
}
}
以上解决方案也适用于：
面试题 08.12. 八皇后：https://leetcode.cn/problems/eight-queens-lcci/description/
52. N 皇后 II：https://leetcode.cn/problems/n-queens-ii/description/
原文地址：https://blog.csdn.net/weixin_43819566/article/details/142344292
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！