温州网站建设首选国鼎网络,wordpress word粘贴,网站建设开发原代码归属,如何在微信小程序上开店文章目录 491.递增子序列思路#xff1a;代码 思路#xff1a;优化代码#xff1a; 46.全排列思路代码一#xff1a;使用used数组代码二#xff1a;使用path判断元素 47.全排列 II思路一#xff1a;层节点和路径都是用used数组做记录思路二#xff1a;层通过排序后是否重… 文章目录 491.递增子序列思路代码 思路优化代码 46.全排列思路代码一使用used数组代码二使用path判断元素 47.全排列 II思路一层节点和路径都是用used数组做记录思路二层通过排序后是否重复过滤 491.递增子序列 思路 代码
class Solution {ListListInteger res new ArrayList();ListInteger pathnew LinkedList();public ListListInteger findSubsequences(int[] nums) {backtracking(nums,0);return res;}public void backtracking(int[] nums,int startIndex){// if(startIndexnums.length-1)return;if(path.size()1){res.add(new ArrayList(path));}int[] used new int[201];for(int istartIndex;inums.length;i){if(!path.isEmpty()path.getLast() nums[i]|| (used[nums[i]100]1)){continue;}used[nums[i]100]1;path.add(nums[i]);backtracking(nums,i1);path.removeLast();}}
}思路优化
通过数组去重取代hashset
代码
class Solution {ListListInteger res new ArrayList();ListInteger pathnew ArrayList();public ListListInteger findSubsequences(int[] nums) {backtracking(nums,0);return res;}public void backtracking(int[] nums,int startIndex){// if(startIndexnums.length-1)return;if(path.size()1){res.add(new ArrayList(path));}int[] used new int[201];for(int istartIndex;inums.length;i){if(!path.isEmpty()path.get(path.size() -1 ) nums[i]|| (used[nums[i]100]!0)){continue;}used[nums[i]100]1;path.add(nums[i]);backtracking(nums,i1);path.remove(path.size() -1);}}
}46.全排列 思路 代码一使用used数组
class Solution {ListListInteger res new ArrayList();ListInteger path new ArrayList();public ListListInteger permute(int[] nums) {boolean[] usednew boolean[nums.length];backtracking(nums,used);return res;}public void backtracking(int[] nums,boolean[] used){if(path.size()nums.length){res.add(new ArrayList(path));return;}for(int i0;inums.length;i){// System.out.println(数值nums[i]布尔值used[nums[i]10]);if(used[i]){continue;}path.add(nums[i]);used[i]true;backtracking(nums,used);used[i]false;path.remove(path.size()-1);}}
}代码二使用path判断元素
path是linkedlist
class Solution {ListListInteger res new ArrayList();ListInteger path new LinkedList();public ListListInteger permute(int[] nums) {// boolean[] usednew boolean[nums.length];backtracking(nums);return res;}public void backtracking(int[] nums){if(path.size()nums.length){res.add(new ArrayList(path));return;}for(int i0;inums.length;i){// System.out.println(数值nums[i]布尔值used[nums[i]10]);if(path.contains(nums[i])){continue;}path.add(nums[i]);backtracking(nums);path.removeLast();}}
}47.全排列 II 思路一层节点和路径都是用used数组做记录
class Solution {ListListInteger res new ArrayList();ListInteger path new ArrayList();public ListListInteger permuteUnique(int[] nums) {boolean[] usednew boolean[nums.length];backtracking(nums,used);return res;}public void backtracking(int[] nums,boolean[] used){if(path.size()nums.length){res.add(new ArrayList(path));return;}int[] cengusednew int[21];for(int i0;inums.length;i){// System.out.println(数值nums[i]布尔值used[nums[i]10]);if(used[i]||cengused[nums[i]10]1){continue;}path.add(nums[i]);cengused[nums[i]10]1;used[i]true;backtracking(nums,used);used[i]false;path.remove(path.size()-1);}}
}思路二层通过排序后是否重复过滤 class Solution {//存放结果ListListInteger result new ArrayList();//暂存结果ListInteger path new ArrayList();public ListListInteger permuteUnique(int[] nums) {boolean[] used new boolean[nums.length];Arrays.fill(used, false);Arrays.sort(nums);backTrack(nums, used);return result;}private void backTrack(int[] nums, boolean[] used) {if (path.size() nums.length) {result.add(new ArrayList(path));return;}for (int i 0; i nums.length; i) {// used[i - 1] true说明同⼀树⽀nums[i - 1]使⽤过// used[i - 1] false说明同⼀树层nums[i - 1]使⽤过// 如果同⼀树层nums[i - 1]使⽤过则直接跳过if (i 0 nums[i] nums[i - 1] used[i - 1] false) {continue;}//如果同⼀树⽀nums[i]没使⽤过开始处理if (used[i] false) {used[i] true;//标记同⼀树⽀nums[i]使⽤过防止同一树枝重复使用path.add(nums[i]);backTrack(nums, used);path.remove(path.size() - 1);//回溯说明同⼀树层nums[i]使⽤过防止下一树层重复used[i] false;//回溯}}}
}
