打开英文网站字体不对,产品推广网站模板,六年级下册数学优化设计答案,如何做网络推广工作java数据结构与算法刷题目录#xff08;剑指Offer、LeetCode、ACM#xff09;-----主目录-----持续更新(进不去说明我没写完)#xff1a;https://blog.csdn.net/grd_java/article/details/123063846 文章目录 解题思路:时间复杂度O( n 2 ∗ n n^2*n n2∗n),空间复杂度O(n) 7…java数据结构与算法刷题目录剑指Offer、LeetCode、ACM-----主目录-----持续更新(进不去说明我没写完)https://blog.csdn.net/grd_java/article/details/123063846 文章目录 解题思路:时间复杂度O( n 2 ∗ n n^2*n n2∗n),空间复杂度O(n) 78题的衍生题不同点在于这道题会有重复元素。所以每个元素入集合时需要判断所以我们先排序让其有序方便我们判断重复元素每个元素有两种状态选和不选每个元素默认不选不选的时候无需进行判断要选择当前元素时要进行判断是否是重复元素和前一个元素是否一样如果是就放弃当前元素的枚举因为必然会重复具体查看代码注释中的例子 LeetCode78. 子集https://blog.csdn.net/grd_java/article/details/136646871
代码 class Solution {/**1 2 2 获得子集不选 不选 不选 []不选 不选 前一个没选而且和前一个一样不选不选 前一个没选和前一个不一样选 不选 [2]不选 选 选 [2,2]选 不选 不选 [1] 选 不选 前一个没选和前一个一样不选选 前一个选了这个也选 不选 [1,2]选 选 前一个选了这个也选 [1,2,2] */int[] nums;int len;ListListInteger ans new ArrayListListInteger();public ListListInteger subsetsWithDup(int[] nums) {Arrays.sort(nums);//先保证有序this.nums nums;this.len nums.length;ListInteger records new ArrayListInteger();//保存当前子集backTracking(false,records,0);return ans;}//其中isPreChoose表示前一个元素是否选择加入集合,start是records的下标public void backTracking(boolean isPreChoose,ListInteger records,int start){if(start len) {//如果当前子集枚举完成就保存ans.add(new ArrayListInteger(records));}else{backTracking(false,records,start1);//不选择当前元素进入集合//如果前一个元素没有被选中并且当前元素确实有前一个元素时//如果当前元素和前一个元素一样就会产生重复的集合。直接return.if(isPreChoose false start0 nums[start-1] nums[start]) return;//选择当前元素进入集合records.add(nums[start]);backTracking(true,records,start1);//不要忘了枚举后将其去除不要影响下一个子集的枚举records.remove(records.size()-1);}}
}
