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. 二叉树中的最大路径和
  • 九、图论
    • 200. 岛屿数量
    • 994. 腐烂的橘子
    • 207. 课程表
    • 补充:210. 课程表 II
    • 208. 实现 Trie (前缀树)
  • 十、回溯
    • 46. 全排列
    • 补充:47. 全排列 II
    • 78. 子集
    • 17. 电话号码的字母组合
    • 39. 组合总和
    • 补充:40. 组合总和 II
    • 补充:216. 组合总和 III
    • 22. 括号生成
    • 79. 单词搜索
    • 131. 分割回文串
    • 51. N 皇后


八、二叉树

二叉树的定义:

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(); // 当前队列中节点数量 sizeList<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、左边界+长度,中序(左根右):左边界、根节点位置-1root.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;中序(左根右):左边界、根节点位置-1root.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 有两条路径长度等于2map.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)) { // 邻接表中当前节点所关联的节点入度-1indegree[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)) { // 邻接表中当前节点所关联的节点入度-1indegree[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;/*** 输入:s = "aab"* 输出:[["a","a","b"],["aa","b"]]*/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/

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/431181.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

移动数组中数字的方法(c语言)

1.移动一维数组中的内容;若数组中有n个整数&#xff0c;要求把下标从0到p(含p&#xff0c;p小于等于n-1&#xff09;的数组元素平移到数组的最后。 例如&#xff0c;一维数组中的原始内容为:1,2,3,4,5,6,7,8,9,10;p的值为3。 移动后&#xff0c;一维数组中的内容应为:5,6,7,8…

qm 命令:管理PVE虚拟机

一、命令简介 ​qm​ 是 Proxmox Virtual Environment (PVE) 中用于管理虚拟机的命令行工具。它允许用户创建、启动、停止、删除虚拟机&#xff0c;以及管理虚拟机的配置和状态。 ‍ 介绍 PVE Proxmox Virtual Environment (PVE) 是一个开源的虚拟化管理平台&#xff0c;专…

设计模式 享元模式(Flyweight Pattern)

享元模式 简绍 享元模式&#xff08;Flyweight Pattern&#xff09;是一种结构型设计模式&#xff0c;它的目的是通过共享技术来有效地支持大量细粒度的对象。享元模式可以极大地减少内存的使用&#xff0c;从而提高程序的性能。它特别适用于需要创建大量相似对象的场景&#…

QT 数据加密

一.使用环境 应该是通用的,此测试版本为如图 二.使用代码 1. 运行代码 QString data = "123abcAbc.-+";qDebug() << "加密:" << QAESEncryption::encodedText(data, "填入自己秘钥");qDebug() << "解密:" <…

C++STL的Stack的使用:STL栈和队列的使用介绍、leecode---最小栈、nowcoder---栈的压入、弹出序列等的介绍

文章目录 前言一、STL栈和队列的使用二、leetcode---最小栈三、nowcoder---栈的压入、弹出序列四、逆波兰表达式求值总结 前言 CSTL的Stack的使用&#xff1a;STL栈和队列的使用介绍、leecode—最小栈、nowcoder—栈的压入、弹出序列等的介绍 一、STL栈和队列的使用 #include …

服务器安装pytorch_geometric torch_scatter踩坑记录

conda create -n pyg python3.8.12 pip install torch1.13.0安装的版本如下 pip install torch-scatter pip install torch-sparse pip install torch-cluster pip install torch-spline-conv pip install torch-geometric2.2.0 pip install ipykernel python -m ipykernel i…

Adobe Illustrator吸管工具提取的颜色与原色之间存在色差

问题原因&#xff1a; 被提取颜色的对象是外部链接图片&#xff0c;对其提取的颜色会与AI中看到的颜色不同 如下图所示&#xff0c;中间的矩形与外部矩形的内部颜色存在色差 解决办法&#xff1a; 方法一&#xff1a;将该外部图片利用屏幕截图的形式&#xff0c;粘贴到AI中。…

2.以太网

局域网 局域网: Local Area Networks (LAN) 网络大小分类 局域网园区网(可以理解为企业网)城域网 广域网是一个网络连接的技术&#xff0c;并非多大范围的网络 网关 为局域网内的用户提供了一扇门&#xff0c;通过网关可以访问到别的网络。这个门&#xff0c;就叫网关 以…

部标(JT/T1078)流媒体对接说明

1.前言 最近在配合客户开发流媒体相关的服务的时候&#xff0c;整理了一些对接过程资料&#xff0c;这里做个分享与记录。流媒体的对接主要牵扯到4个方面&#xff1a; &#xff08;1&#xff09;平台端&#xff1a;业务端系统&#xff0c;包含前端呈现界面。 &#xff08;2&a…

物联网实践教程:微信小程序结合OneNET平台MQTT实现STM32单片机远程智能控制 远程上报和接收数据——STM32代码实现篇

STM32代码实现 开启本章节需要完成下方的前置任务&#xff1a; 点击跳转&#xff1a; 物联网实践教程&#xff1a;微信小程序结合OneNET平台MQTT实现STM32单片机远程智能控制 远程上报和接收数据——汇总 目标 1.连接OneNET&#xff1a;STM32使用串口与ESP8266/01s连接发送…

Linux网络命令:用于请求和配置网络地址的命令dhclient详解

目录 一、概述 二、功能描述 三、基本使用 1. 命令格式 2. 常用选项 3. 获取帮助 ​编辑 4. 基本操作 四、工作原理 1. 发送DHCP请求 2. 接收DHCP响应 3. 请求IP地址 4. 确认IP地址 5. 配置网络接口 五、功能特点 六、配置文件 七、常用命令和示例 1、启动…

QT客户端发送HTTP请求此时服务器到底收到了哪些数据?

一个Http请求包括 请求行 请求头 空行 请求体 下面是示例&#xff1a; 1,2,3,4分别代表上面的四个部分&#xff0c;我只是做了一些解析&#xff0c;具体可以结合代码 1. post / HTTP/1.1 2.GET请求头包括Host(主机名),user-agent&#xff08;客户端标识符&#xff09;&am…

SiMBA:基于FFT变换和Mamba的图像分类模型算法解析

目录 1 算法原理1 EinFFT&#xff1a;1.1 频谱变换1.2 频域通道混频 & 频谱门控网络1.3 逆频谱变换 2 整体计算公式3 SiMBA&#xff1a;4 小结 2 代码大致逻辑EinFFT模块MambaBlock模块MambaLayer模块PVT2FFN和FFN模块ClassBlock和Block_mamba模块DownSamples模块Stem模块定…

统信服务器操作系统【targetcli部署】

targetcli部署方案 文章目录 功能概述功能介绍1.安装targetcli2.targetcli语法及参数说明3.示例1. 配置2.访问功能概述 SCSI 即小型计算机系统接口(Small Computer System Interface;简写:SCSI) iSCSI,internet SCSI 网络磁盘 ,提供一对一的网络存储, 主机A 提供xx存储设…

gitlab 的CI/CD (二)

前言 上文完成了gitlab-runner的基础配置及将gitlab的制品上传至软件包库&#xff08;产品库&#xff09;的脚本编写&#xff1b; 本文实现gitlab的ci/cd对远程服务器的操作&#xff1b; 介绍 要让Gitlab Runner部署到远程机器&#xff0c;远程机器必须信任gitlab runner账…

当大语言模型应用到教育领域时会有什么火花出现?

当大语言模型应用到教育领域时会有什么火花出现&#xff1f; LLM Education会出现哪些机遇与挑战? 今天笔者分享一篇来自New York University大学的研究论文&#xff0c;另外一篇则是来自Michigan State University与浙江师范大学的研究论文&#xff0c;希望对这个话题感兴趣…

构建高效企业客户管理系统:SpringBoot应用

1 绪论 1.1研究背景 随着网络不断的普及发展&#xff0c;企业客户管理系统依靠网络技术的支持得到了快速的发展&#xff0c;首先要从员工的实际需求出发&#xff0c;通过了解员工的需求开发出具有针对性的首页、个人中心、员工管理、客户信息管理、行业类型管理、项目信息管理、…

读取t x t文件生成exce

读取t x t文件生成excel package com.moka.api.custom.core.controller; import com.google.gson.Gson; import com.google.gson.reflect.TypeToken; import org.apache.poi.ss.usermodel.Row; import org.apache.poi.ss.usermodel.Sheet; import org.apache.poi.ss.usermode…

JetBrains系列产品无限重置免费试用方法

JetBrains系列产品无限重置免费试用方法 写在前面安装插件市场安装插件 写在前面 支持的产品&#xff1a; IntelliJ IDEA AppCode CLion DataGrip GoLand PhpStorm PyCharm Rider RubyMine WebStorm为了保证无限重置免费试用方法的稳定性&#xff0c;推荐下载安装2021.2.2及其…

基于milvus数据库的RAG-Demo

1.上传文本并将文本向量化 import os from django.conf import settings from langchain.document_loaders import TextLoader from langchain.text_splitter import RecursiveCharacterTextSplitter, CharacterTextSplitter from langchain.vectorstores import Chroma from l…