h5自适应网站建设是什么意思,保险官网,企业微信官网,哈尔滨网站域名备案90 Subsets II leetcode第90题#xff0c;用深度优先搜索的思路写出了三种不同的代码。一道题目#xff0c;同样是深度优先搜索的问题#xff0c;因为看问题角度不同#xff0c;思路不同#xff0c;代码也不一样 /*** [1,2,2,3] [] [1] [1,2] [1,2](重复) 情况#xff1a…90 Subsets II leetcode第90题用深度优先搜索的思路写出了三种不同的代码。一道题目同样是深度优先搜索的问题因为看问题角度不同思路不同代码也不一样 /*** [1,2,2,3] [] [1] [1,2] [1,2](重复) 情况 nums[1]不选择nums[2]选择 [1,3] [1,2,2]* [1,2,3] [1,2,3](重复) 情况 nums[1]不选择nums[2]选择 [1,2,2,3]* * param nums* return*/public ListListInteger subsetsWithDup(int[] nums) {Arrays.sort(nums);ListListInteger result new ArrayListListInteger();ListInteger list new ArrayListInteger();dfs(result, list, nums, 0, false);return result;}private void dfs(ListListInteger result, ListInteger list, int[] nums, int idx, boolean selected) {if (idx nums.length) {result.add(new ArrayListInteger(list));return;}if (idx 0 nums[idx - 1] nums[idx] !selected) {dfs(result, list, nums, idx 1, false);} else {dfs(result, list, nums, idx 1, false);list.add(nums[idx]);dfs(result, list, nums, idx 1, true);list.remove(list.size() - 1);}}/*** 使用下标记录的方式深度优先搜素思路* * param nums* return*/public ListListInteger subsetsWithDupV2(int[] nums) {Arrays.sort(nums);ListListInteger result new ArrayListListInteger();boolean[] visit new boolean[nums.length];// 记录是否选择dfsV2(result, visit, nums, 0);return result;}private void dfsV2(ListListInteger result, boolean[] visit, int[] nums, int idx) {if (idx nums.length) {ListInteger list new ArrayListInteger();for (int i 0; i visit.length; i) {if (visit[i]) {list.add(nums[i]);}}result.add(list);return;}if (idx 0 nums[idx - 1] nums[idx] visit[idx - 1] false) {dfsV2(result, visit, nums, idx 1);} else {dfsV2(result, visit, nums, idx 1);visit[idx] true;dfsV2(result, visit, nums, idx 1);visit[idx] false;}}/*** 深度优先搜素思路另一种不同的实现* 上面的思路是当我遍历到nums[i]的时候我是不是选择这个元素* 这个的思路是第0个位置可以没有元素或者选择的元素nums的0-(n-1)第二个位置可以没有元素或者是从某个下标-(n-1)选择元素* * * param nums* return*/public ListListInteger subsetsWithDupV3(int[] nums) {Arrays.sort(nums);ListListInteger result new ArrayListListInteger();ListInteger each new ArrayListInteger();dfsV3(nums, result, each, 0);return result;}private void dfsV3(int[] nums, ListListInteger result, ListInteger each, int startPos) {if (startPos nums.length) {result.add(new ArrayListInteger(each));}for (int i startPos; i nums.length; i) {if (i startPos nums[i] nums[i - 1])continue;each.add(nums[i]);// 选择i位置dfsV3(nums, result, each, i 1);each.remove(each.size() - 1);}}
