代碼隨想錄算法刷題訓練營day29：LeetCode(491)遞增子序列、LeetCode(46)全排列、LeetCode(47)全排列 II
LeetCode(491)遞增子序列
題目
代碼
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;class Solution {//先取出來再定義一個函數進行判斷public Set<List<Integer>> tempResult=new HashSet<>();public List<Integer> path=new ArrayList<>();public List<List<Integer>> findSubsequences(int[] nums) {int startIndex=0;backtracking(nums,startIndex);List<List<Integer>> result=new ArrayList<>(tempResult);return result;}public void backtracking(int[] nums,int startIndex){if(isSubsequences(path)){List<Integer> tempPath=Arrays.asList(new Integer[path.size()]);Collections.copy(tempPath, path);tempResult.add(tempPath);//子集問題不能加return}for(int i=startIndex;i<nums.length;i++){path.add(nums[i]);backtracking(nums, i+1);path.remove(path.size()-1);}}public boolean isSubsequences(List<Integer> path){boolean flag=true;if(path.size()<2){flag=false;}List<Integer> testPath=Arrays.asList(new Integer[path.size()]);Collections.copy(testPath, path);Collections.sort(testPath);for(int i=0;i<path.size();i++){if(testPath.get(i)!=path.get(i)){flag=false;}}return flag;}
}
LeetCode(46)全排列
題目
代碼
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;class Solution {public List<List<Integer>> result=new ArrayList<>();public List<Integer> path=new ArrayList<>();public List<List<Integer>> permute(int[] nums) {int[] used=new int[nums.length];//記錄元素是否被使用int startIndex=0;backtracking(nums,used); return result;}public void backtracking(int[] nums,int[] used){if(path.size()==nums.length){List<Integer> tempPath=Arrays.asList(new Integer[path.size()]);Collections.copy(tempPath, path);result.add(tempPath);return;}for(int i=0;i<nums.length;i++){if(used[i]==1){continue;//1-1這個分支直接沒有了，直此時就能到1-2了--重點}path.add(nums[i]);used[i]=1;backtracking(nums, used);path.remove(path.size()-1);used[i]=0;//彈出來狀態也得改變}}
}
LeetCode(47)全排列 II
題目
代碼
java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;class Solution {public Set<List<Integer>> tempResult=new HashSet<>();//用set集合做public List<Integer> path=new ArrayList<>();public List<List<Integer>> permuteUnique(int[] nums) {int[] used=new int[nums.length];backtracking(nums,used);List<List<Integer>> result=new ArrayList<>(tempResult);return result;}public void backtracking(int[] nums,int[] used){if(path.size()==nums.length){List<Integer> tempPath=Arrays.asList(new Integer[path.size()]);Collections.copy(tempPath, path);tempResult.add(tempPath);return;}for(int i=0;i<nums.length;i++){if(used[i]==1){continue;}path.add(nums[i]);used[i]=1;backtracking(nums, used);path.remove(path.size()-1);used[i]=0;}}
}
)
