青柠

题目给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的 子集（幂集）。 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。 示例 1： 12输入：nums = [1,2,2]输出：[[],[1],[1,2],[1,2,2],[2],[2,2]] 示例 2： 12输入：nums = [0]输出：[[],[0]] 提示： 1 <= nums.length <= 10 -10 <= nums[i] <= 10 实现代码 使用DFS实现回溯算法，因为元素会重复，所以需要判断每个节点下的子节点必须只能处理一个 123456789101112131415161718192021222324252627class Solution { List<List<Integer>> traceList = new LinkedList<>(); LinkedList<Integer> trace = new LinkedList<>(); ...

题目给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 示例 1： 12输入：nums = [1,2,3]输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 示例 2： 12输入：nums = [0,1]输出：[[0,1],[1,0]] 示例 3： 12输入：nums = [1]输出：[[1]] 提示： 1 <= nums.length <= 6 -10 <= nums[i] <= 10 nums 中的所有整数 互不相同 实现代码 使用DFS实现回溯算法 1234567891011121314151617181920212223242526272829303132333435class Solution { List<List<Integer>> traceList = new LinkedList<>(); LinkedList<Integer> trace = new L...

题目给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。 示例 1： 12345678910输入：n = 4, k = 2输出：[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4],] 示例 2： 12输入：n = 1, k = 1输出：[[1]] 提示： 1 <= n <= 20 1 <= k <= n 实现代码 使用DFS实现回溯算法 12345678910111213141516171819202122232425class Solution { List<List<Integer>> traceList = new LinkedList<>(); // 记录回溯算法的递归路径 LinkedList<Integer> trace = new LinkedList<>(); public List<List<Integer>>...

题目给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 示例 1： 12输入：nums = [1,2,3]输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] 示例 2： 12输入：nums = [0]输出：[[],[0]] 提示： 1 <= nums.length <= 10 -10 <= nums[i] <= 10 nums 中的所有元素 互不相同 实现代码 使用DFS实现回溯算法 1234567891011121314151617181920212223class Solution { List<List<Integer>> result = new LinkedList<>(); LinkedList<Integer> path = new LinkedList<>(); public List<List<...

题目你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。 锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。 列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。 字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。 示例 1: 123456输入：deadends = ["0201","0101","0102","1...

题目在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示。一次 移动 定义为选择 0 与一个相邻的数字（上下左右）进行交换. 最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。 给出一个谜板的初始状态 board ，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。 示例 1： 123输入：board = [[1,2,3],[4,0,5]]输出：1解释：交换 0 和 5 ，1 步完成 示例 2: 123输入：board = [[1,2,3],[5,4,0]]输出：-1解释：没有办法完成谜板 示例 3: 1234567891011输入：board = [[4,1,2],[5,0,3]]输出：5解释：最少完成谜板的最少移动次数是 5 ，一种移动路径:尚未移动: [[4,1,2],[5,0,3]]移动 1 次: [[4,1,2],[0,5,3]]移动 2 次: [[0,1,2],[4,5,3]]移动 3 次: [[1,0,2],[4,5,3]]移动 4 次: [[1,2,...

回溯算法模板伪代码 回溯算法本质上还是DFS算法 12345678910111213LinkedList<Integer> trace = new LinkedList<>();private void backtrack(int[] candidates) { for (int i = 0; i < candidates.length; i++) { // 前进 trace.addLast(candidates[i]); backtrack(candidates); // 回退 trace.removeLast(); }} 回溯算法解决的问题 回溯算法主要用于解决子集、组合和排列问题，通过对所经过的节点路径进行追踪 子集问题 子集问题只能不可重复使用 元素不重复假设存在数组candidates = [2, 6 ,7]，对应子集如下： [[], [2], [6], [7], [2,6], [2,7], ...

题目零钱兑换： 给定金额amount和硬币面额值coins[]，求组成金额amount所用的最少硬币数量； 条件 每种面额硬币值的数量不限； 思路 首先确定好状态、选择和状态转换方程式 1、判断是否动态规划问题 最优子结构 全局最优解包含子问题最优解 比如：求组成金额100所用的最少硬币数？ 主问题： ​ 组成金额100所用的最少硬币数； 子问题： ​ 组成金额99所用的最少硬币数 ​ 组成金额98所用的最少硬币数 ​ …… 主问题最优解答案是最少硬币数，子问题最优解答案也是最少硬币数，求主问题的答案可通过子问题答案进行推导得出 存在最优子结构的问题不一定是动态规划问题，但动态规划问题一定存在最优子结构； 存在重叠子问题 同一个子问题被多次计算 比如在计算金额100的时候，需要计算金额99、98，但是计算金额99的时候也需要计算金额98，计算金额98子问题被多次计算； 2、定义状态 明确动态规划状态函数dp 关键在于定义dp函数表示什么： dp(i) = 组成金额i所需的最少硬币数 3、推导状态转移方程根据状态函数的定义d...

题目给你一棵二叉树的根节点，返回该树的 直径 。 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。 两节点之间路径的 长度 由它们之间边数表示。 示例 1： 123输入：root = [1,2,3,4,5]输出：3解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。 示例 2： 12输入：root = [1,2]输出：1 提示： 树中节点数目在范围 [1, 104] 内 -100 <= Node.val <= 100 实现代码 通过二叉树的递归遍历（DFS）实现 123456789101112131415161718192021222324252627282930313233343536373839/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() &...

题目给你二叉树的根节点 root ，返回它节点值的 前序 遍历。 示例 1： **输入：**root = [1,null,2,3] 输出：[1,2,3] 解释： 示例 2： **输入：**root = [1,2,3,4,5,null,8,null,null,6,7,9] 输出：[1,2,4,5,6,7,3,8,9] 解释： 示例 3： **输入：**root = [] 输出：[] 示例 4： **输入：**root = [1] 输出：[1] 提示： 树中节点数目在范围 [0, 100] 内 -100 <= Node.val <= 100 实现代码 通过二叉树的递归遍历（DFS）实现 1234567891011121314151617181920212223242526272829303132333435/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * ...