Day29题目
LeetCode491非递减子序列:
核心思想:也是回溯,但是不能使用排序去重,需要使用set。
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> findSubsequences(int[] nums) {
help(nums,0);
return res;
}
public void help(int[] nums, int start){
if(start > nums.length) return;
if(path.size() > 1){
// 将所有子序列都加入
res.add(new ArrayList<>(path));
}
Set<Integer> set = new HashSet<>();
for(int i = start; i < nums.length; i ++){
// 这里进行去重,当i大于start则是同一树层,如果set中存有这个数字则continue
if(i>start && set.contains(nums[i])){
continue;
}
if(path.isEmpty() || nums[i]>= path.getLast()){
path.add(nums[i]);
set.add(nums[i]);
help(nums,i+1);
// set不用回溯,因为每一树层在上面都自己创建了一个新的
path.removeLast();
}
}
}
}
LeetCode46全排列
核心思想:需要一个Boolean数组记录哪个使用过了,然后每次都从第一位开始遍历,这个没有去重,直接写回溯就ok
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
boolean[] used = new boolean[7];
public List<List<Integer>> permute(int[] nums) {
help(nums);
return res;
}
public void help(int[] nums){
if(path.size() == nums.length){
res.add(new ArrayList(path));
return;
}
for(int i = 0 ; i < nums.length;i++){
if(used[i]){
continue;
}
path.add(nums[i]);
used[i] = true;
help(nums);
path.removeLast();
used[i] = false;
}
}
}
LeetCode47全排列Ⅱ:比上一题加上了去重
核心思想:还是使用了used数组,需要去重
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
boolean[] used = new boolean[9];
Arrays.sort(nums);
help(nums,used,0);
return res;
}
public void help (int[] nums, boolean[] used, int count){
if(count == nums.length) {
res.add(new ArrayList<>(path));
}
for(int i = 0; i < nums.length; i ++){
// 这里进行去重,在全排列中,只要是相同的元素,全排列结果就相同,因此只要有一个相同的元素就行了
// 我空想了一下,比如[1,1,1,2]的元素,最终加入结果集的1112是 nums[2] nums[1] nums[0] nums[3] 其他的被去重。
if( i > 0 && nums[i-1] == nums[i] && used[i-1] == true ){
continue;
}
if(used[i] == false){
path.add(nums[i]);
used[i] = true;
help(nums,used,count+1);
used[i] = false;
path.removeLast();
}
}
}
}