文章目录
第一题: 剑指 Offer II 079. 所有子集
LeetCode: 剑指 Offer II 079. 所有子集
描述:
给定一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
解题思路:
代码实现:
class Solution {
List<List<Integer>> result = new ArrayList<>();
List<Integer> ret = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
dfs(nums,0);
return result;
}
public void dfs(int[] nums, int start) {
result.add(new ArrayList<>(ret));
// 剪枝1: i=start 就是确保了不包含重复子集
for(int i = start; i < nums.length; i++) {
ret.add(nums[i]);
// 剪枝2: 这里传 i+1 确保了不重复使用同一个元素
dfs(nums,i+1);
ret.remove(ret.size()-1);
}
}
}
第二题: 剑指 Offer II 080. 含有 k 个元素的组合
LeetCode: 剑指 Offer II 080. 含有 k 个元素的组合
描述:
给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
解题思路:
代码实现:
class Solution {
List<List<Integer>> result = new ArrayList<>();
List<Integer> ret = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
int[] arr = new int[n];
for(int i = 0; i < n; i++) {
arr[i] = i+1;
}
dfs(arr,0,k);
return result;
}
public void dfs(int[] arr,int start, int k) {
if(ret.size() == k) {
result.add(new ArrayList<>(ret));
return;
}
// 剪枝1: 让i=start 确保了没有重复的子集
for(int i = start; i < arr.length; i++) {
ret.add(arr[i]);
// 剪枝2: 传入 i+1 确保了不使用重复元素
dfs(arr,i+1,k);
ret.remove(ret.size() - 1);
}
}
}
第三题: 剑指 Offer II 081. 允许重复选择元素的组合
LeetCode: 剑指 Offer II 081. 允许重复选择元素的组合
描述:
给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。
candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的唯一组合数少于 150 个。
解题思路:
代码实现:
class Solution {
List<List<Integer>> result = new ArrayList<>();
List<Integer> ret = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
dfs(candidates,0,target);
return result;
}
public void dfs(int[] candidates, int start, int target) {
if (target == 0) {
result.add(new ArrayList<>(ret));
return;
}
// 剪枝1: i = start 确保不会重复子集
for(int i = start; i < candidates.length; i++) {
if(candidates[i] <= target){
ret.add(candidates[i]);
// 传入i 就会重复使用当前元素
dfs(candidates,i,target-candidates[i]);
ret.remove(ret.size()-1);
}
}
}
}
第四题: 剑指 Offer II 082. 含有重复元素集合的组合
LeetCode: 剑指 Offer II 082. 含有重复元素集合的组合
描述:
给定一个可能有重复数字的整数数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次，解集不能包含重复的组合。
解题思路:
代码实现:
class Solution {
List<List<Integer>> result = new ArrayList<>();
List<Integer> ret = new ArrayList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
boolean[] tmp = new boolean[candidates.length];
dfs(candidates,0,target,tmp);
return result;
}
public void dfs(int[] candidates, int start, int target,boolean[] tmp) {
if(target == 0) {
result.add(new ArrayList<>(ret));
return;
}
// 剪枝1: i=start确保不会出现重复组合
for (int i = start; i < candidates.length; i++) {
// 剪枝3: 使用boolean数组来标记,确保了出现重复元素的情况
if(i>0 && candidates[i] == candidates[i-1] && !tmp[i-1]){
continue;
}
if(candidates[i] <= target) {
ret.add(candidates[i]);
tmp[i] = true;
// 剪枝2: i+1就是为了确保不会出现使用自己, 但是可以使用别人
dfs(candidates,i+1,target-candidates[i],tmp);
tmp[i] = false;
ret.remove(ret.size()-1);
}
}
}
}
第五题: 剑指 Offer II 083. 没有重复元素集合的全排列
LeetCode: 剑指 Offer II 083. 没有重复元素集合的全排列
描述:
给定一个不含重复数字的整数数组 nums ，返回其 所有可能的全排列 。可以 按任意顺序 返回答案。
解题思路:
代码实现:
class Solution {
List<List<Integer>> result = new ArrayList<>();
List<Integer> ret = new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
boolean[] tmp = new boolean[nums.length];
dfs(nums,tmp);
return result;
}
public void dfs(int[] nums, boolean[] tmp) {
if (ret.size() == nums.length) {
result.add(new ArrayList<>(ret));
return;
}
for (int i = 0; i < nums.length; i++) {
// 剪枝1: 使用boolean数组来标记, 如果当前下标是false就是没用过
if (!tmp[i]) {
tmp[i] = true;
ret.add(nums[i]);
dfs(nums,tmp);
tmp[i] = false;
ret.remove(ret.size()-1);
}
}
}
}
第六题: 剑指 Offer II 084. 含有重复元素集合的全排列
LeetCode: 剑指 Offer II 084. 含有重复元素集合的全排列
描述:
给定一个可包含重复数字的整数集合 nums ，按任意顺序 返回它所有不重复的全排列。
解题思路:
代码实现:
class Solution {
List<List<Integer>> result = new ArrayList<>();
List<Integer> ret = new ArrayList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);
boolean[] tmp = new boolean[nums.length];
dfs(nums,tmp);
return result;
}
public void dfs(int[] nums, boolean[] tmp) {
if (ret.size() == nums.length) {
result.add(new ArrayList<>(ret));
return;
}
for (int i = 0; i < nums.length; i++) {
// 剪枝2: 从第二个元素开始, 如果当前元素和前一个元素是一样的,且前一个元素没有使用, 直接跳过
if(i > 0 && nums[i] == nums[i-1] && !tmp[i-1]){
continue;
}
// 剪枝1: 使用boolean数组来标记, 如果当前下标是false就是没用过
if(!tmp[i]){
tmp[i] = true;
ret.add(nums[i]);
dfs(nums,tmp);
tmp[i] = false;
ret.remove(ret.size()-1);
}
}
}
}
第七题: 剑指 Offer II 085. 生成匹配的括号
LeetCode: 剑指 Offer II 085. 生成匹配的括号
描述:
正整数 n 代表生成括号的对数，请设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
解题思路:
代码实现:
class Solution {
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
backstrack(result,"",n,n);
return result;
}
public void backstrack(List<String> result,String str,int left, int right) {
// 剪枝1
if(left < 0 || right <0) return;
// 剪枝2
if(left > right) return;
if(left == 0 && right == 0 ) {
result.add(str);
return;
}
backstrack(result,str+"(",left-1,right);
backstrack(result,str+")",left,right-1);
}
}
第八题: 剑指 Offer II 086. 分割回文子字符串
LeetCode: 剑指 Offer II 086. 分割回文子字符串
描述:
给定一个字符串 s ，请将 s 分割成一些子串，使每个子串都是 回文串 ，返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
解题思路
代码实现:
class Solution {
List<List<String>> result = new ArrayList<>();
List<String> ret = new ArrayList<>();
public String[][] partition(String s) {
bfs(s,0);
String[][] str = new String[result.size()][];
int i = 0;
for(List<String> list : result){
str[i++] = list.toArray(new String[list.size()]);
}
return str;
}
public void dfs(String s,int start) {
if(s.length() == start) {
result.add(new ArrayList<>(ret));
return;
}
// 剪枝1: 不能出现重复组合
for(int i = start; i < s.length(); i++) {
// 剪枝3: 必须是回文
if(isHui(s,start,i)) {
// 剪枝2: 不能重复使用同一个元素
ret.add(s.substring(start,i+1));
bfs(s,i+1);
ret.remove(ret.size()-1);
}
}
}
public boolean isHui(String s,int left, int right) {
while(left<right) {
if(s.charAt(left) == s.charAt(right)){
left++;
right--;
}else{
return false;
}
}
return true;
}
}