关注Java领域相关技术 记录有趣的事情

回溯

LeetCode-78. 子集

问题地址 LeetCode每日一题/2020-09-20 LeetCode78. 子集 问题描述 规则 给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。 说明 解集不能包含重复的子集。 示例 示例一: 输入: nums = 输出: ,   ,   ,   ,   ,   ,   ,   [] ] 解析 解题思路 每个元素都有两个选项,选择、不选择; 题目示例,元素1可以考虑选择或不选择,然后考察2,以此类推; 其递归树为: 一个子树就是一个递归调用,对当前枚举的数,选和不选可以分出两个分支,分别对应两个递归的子调用,在子调用中,考察下一个数。 当 inx 越界(in…
US-B.Ralph
10 months ago

LeetCode-47. 全排列 II

问题地址 LeetCode每日一题/2020-09-18 LeetCode47. 全排列 II 问题描述 规则 给定一个可包含重复数字的序列,返回所有不重复的全排列。 示例 示例1 输入: 输出: , , ] 解析 解题思路 根据题目规则本题有两点约束: 数字不可以被重复选择; 找到的排列不能重复,由于本题所给的输入中包含重复数字,故$$与$$属重复排列; 数据操作分析 本题对排列组合结果的顺序没有要求,我们为了后边去重更方便首先对给定数组排序,对于排序后的数组进行全排列时,使用如下规则对重复排列去重: $nums = $; $visited = true$; 对于第一条约束我们需要判断 $v…
US-B.Ralph
10 months ago

LeetCode-37. 解数独

问题地址 LeetCode每日一题/2020-09-15 LeetCode37. 解数独 问题描述 规则 编写一个程序,通过已填充的空格来解决数独问题。 一个数独的解法需遵循如下规则: 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 空白格用 '.' 表示。 示例 示例 数独答案(答案被标成红色) 提示 给定的数独序列只包含数字 1-9 和字符 '.' 。 你可以假设给定的数独只有唯一解。 给定数独永远是 9x9 形式的。 解析 解题思路 数据操作分析 编码实现 官方解法 前言 我们可以考虑按照「行优…
US-B.Ralph
10 months ago

LeetCode-216. 组合总和 III

问题地址 LeetCode每日一题/2020-09-11 LeetCode216. 组合总和 III 问题描述 规则 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。 说明 所有数字都是正整数。 解集不能包含重复的组合。 示例 示例一: 输入: k = 3, n = 7 输出: ] 示例二: 输入: k = 3, n = 9 输出: , , ] 解析 解题思路 今天的题目和前两天的每日一题类似,都可可以尝试用「搜索回溯」的方法来解决。 相似题目: 39. 组合总和 40. 组合总和 II 46. 全排列 47. 全排列 II …
US-B.Ralph
10 months ago

LeetCode-40. 组合总和 II

问题地址 LeetCode每日一题/2020-09-10 LeetCode40. 组合总和 II 问题描述 规则 给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用一次。 说明 所有数字(包括目标数)都是正整数。 解集不能包含重复的组合。 示例 示例一: 输入: candidates = , target = 8, 所求解集为: , , , ] 示例二: 输入: candidates = , target = 5, 所求解集为: , ] 解析 解题思路…
US-B.Ralph
10 months ago

LeetCode-39. 组合总和

问题地址 LeetCode每日一题/2020-09-09 LeetCode39. 组合总和 问题描述 规则 给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的数字可以无限制重复被选取。 说明 所有数字(包括 target)都是正整数。 解集不能包含重复的组合。 示例 示例一: 输入:candidates = , target = 7, 所求解集为: , ] 示例二: 输入:candidates = , target = 8, 所求解集为: , , ] 提示 $1 &l…
US-B.Ralph
10 months ago

LeetCode-77. 组合

问题地址 LeetCode每日一题/2020-09-08 LeetCode77. 组合 问题描述 规则 给定两个整数 $n$ 和 $k$,返回 $1 ... n$ 中所有可能的 $k$ 个数的组合。 示例 示例一: 输入: n = 4, k = 2 输出: , , , , , , ] 解析 解题思路 使用递归思路来解题; 题目的结果可以理解为: 从n个里面先选1个; 从n-1个里面选出剩下的k-1个; 数据操作分析 复杂度分析 时间复杂度 空间复杂度 编码实现 public class LeetCode0077_Combinations { List<List<Integer>…
US-B.Ralph
10 months ago

LeetCode-60. 第k个排列

问题地址 LeetCode每日一题/2020-09-05 LeetCode60. 第k个排列 问题描述 规则 给出集合 ,其所有元素共有 n! 种排列。 按大小顺序列出所有排列情况,并一一标记,当 n = 3 时, 所有排列如下: "123" "132" "213" "231" "312" "321" 给定 n 和 k,返回第 k 个排列。 说明: 给定 n 的范围是 。 给定 k 的范围是。 示例1 输入: n = 3, k = 3 输出: "213" 输入: n = 4, k = 9 输出: "2314" 解析 解题思路 复杂度分析 数据操作分析 编码实现 官方解法 数学 + 缩小问题规模…
US-B.Ralph
10 months ago