算法训练营Day26
#Java #全排列 #回溯
Feeling and experiences:
递增子序列:力扣题目链接
给你一个整数数组 nums
,找出并返回所有该数组中不同的递增子序列,递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
数组中可能含有重复元素,如出现两个整数相等,也可以视作递增序列的一种特殊情况。
这道题要注意的点:
目的就是早递增子序列,所以不能对原来的数值进行排列
所以不能像子集II 那个问题一样,先给数组中的元素排好顺序,再来用used数组标记。
class Solution {
List<List<Integer>> ans = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> findSubsequences(int[] nums) {
back(nums,0);
return ans;
}
public void back(int []nums,int startIndex){
//什么时候收集?
if(path.size() >= 2){
ans.add(new ArrayList<>(path));
}
//该题又要去重,又要使其为递增
//建立一个Set集合
Set<Integer> set = new HashSet<>();
for(int i=startIndex;i<nums.length;i++){
if(!path.isEmpty() && path.get(path.size()-1)>nums[i] || set.contains(nums[i])){
continue;
}
set.add(nums[i]);
path.add(nums[i]);
back(nums,i+1);
path.remove(path.size()-1);
}
}
}
?Set集合的使用:(为什么Set集合放在for循环外部?)
1. 去重的目的:
目的是确保在同一递归层级中,不会因为重复选择同一个元素而生成重复的子序列。这是为了防止例如?[1,?2,?2]?这样的数组生成两个相同的子序列?[1,?2]。
2. 作用域的问题:
如果?Set?被放在?for?循环内,那么每次循环时都会创建一个新的?Set。这意味着对于每个元素,Set?都是空的,所以每个元素都会被认为是“新”的,从而无法阻止同一层级中的重复选择。
3. 保持状态:
将?Set?放在?for?循环外部,可以让它在整个递归调用的特定层级中保持状态。这样,当递归到同一层级的不同部分时,Set?中已经包含了该层级中先前考虑过的元素,有效防止重复。
全排列:力扣题目链接
给定一个不含重复数字的数组 nums
,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
经典的模板题
这里引用代码随想录中的图解:
class Solution {
List<List<Integer>> ans = new ArrayList<>();
List<Integer> path = new ArrayList<>();
boolean []used;
public List<List<Integer>> permute(int[] nums) {
used = new boolean[nums.length];
Arrays.fill(used,false);
back(nums);
return ans;
}
public void back(int []nums){
if(path.size() == nums.length){
ans.add(new ArrayList<>(path));
}
for(int i = 0;i<nums.length;i++){
//判断是否用过
if(used[i] == true){
continue;
}
used[i] = true;
path.add(nums[i]);
back(nums);
used[i] = false;
path.remove(path.size()-1);
}
}
}
充分利用了used数组~
全排列 II:力扣题目链接
给定一个可包含重复数字的序列 nums
,按任意顺序 返回所有不重复的全排列。
关键点:树层去重
class Solution {
List<List<Integer>> ans = new ArrayList<>();
List<Integer> path = new ArrayList<>();
boolean []used;
public List<List<Integer>> permuteUnique(int[] nums) {
//把数组进行排列
Arrays.sort(nums);
used = new boolean[nums.length];
Arrays.fill(used,false);
back(nums);
return ans;
}
public void back(int []nums){
if(path.size() == nums.length){
ans.add(new ArrayList<>(path));
return;
}
for(int i =0;i<nums.length;i++){
//去重
if(i>0 && nums[i] == nums[i-1] && used[i-1] == true){
continue;
}
if(used[i] == false){
used[i] = true;
path.add(nums[i]);
//回溯
back(nums);
path.remove(path.size()-1);
used[i] = false;
}
}
}
}
?整体思路:
? 首先,将数组排序。这样,相同的元素会相邻,便于去重。
? 在?back?方法中,使用?if?条件进行去重:
? if?(i?>?0?&&?nums[i]?==?nums[i?-?1]?&&?used[i?-?1]?==?true):这个条件检查当前元素是否与前一个元素相同,并且前一个元素已经被使用过。如果是,就跳过当前元素,避免在同一树层生成重复的排列。
?
此时相望不相闻,
愿逐月华流照君~
Fighting!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!