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

回溯

LeetCode-78. 子集

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

LeetCode-47. 全排列 II

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

LeetCode-37. 解数独

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

LeetCode-40. 组合总和 II

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