首页 > 其他分享 >全排列树层/树枝去重

全排列树层/树枝去重

时间:2024-03-14 17:37:10浏览次数:14  
标签:排列 nums 元素 树枝 树层 && 使用

去重:1.对数组进行排序,保证相同数据能放在一起

Arrays.sort(nums);

2.进行去重:当这个元素与前一个元素相等,且i>0,并且前一个元素没被使用的时候进行去重。

树层去重为什么前一个元素没被使用就可以去重:

在回溯操作中,树层上的变化一直都是前一个元素的使用变成这个元素的使用。而树枝上的变化则是前一个元素使用的同时,这个元素也使用了.

if(i>0&&nums[i]==nums[i-1]&&!isVisited[i-1])
    continue;

上面代码为树层去重//这个效率更高,他会剪掉更多的分枝

if(i>0&&nums[i]==nums[i-1]&&isVisited[i-1])
    continue;

上述代码为树枝去重

标签:排列,nums,元素,树枝,树层,&&,使用
From: https://www.cnblogs.com/kun1790051360/p/18073357

相关文章

  • 数字排列 - 华为OD统一考试(C卷)
    OD统一考试(C卷)分值:200分题解:Java/Python/C++题目描述小明负责公司年会,想出一个趣味游戏:屏幕给出1−9中任意4个不重复的数字,大家以最快时间给出这几个数字可拼成的数字从小到大排列位于第n位置的数字,其中n为给出数字中最大的(如果不到这么多数字则......
  • leetcode回溯法典型例题:39.组合总和、40组合总和 II、46.全排列、47.全排列 II
    leetcode回溯法典型例题:39.组合总和、40组合总和II、46.全排列、47.全排列II39.组合总和39.组合总和-力扣(LeetCode)思路构建组合使用递归的方式构建出所有组合。由题意可知,元素可以无限取用,所以我们构建的时候每确定一个数字,进入更深层递归的时候,每个数字都可以取用(此......
  • 力扣--深度优先算法/回溯算法47.全排列 Ⅱ
    思路分析:使用DFS算法进行全排列,递归地尝试每个可能的排列方式。使用path向量保存当前正在生成的排列,当其大小达到输入数组的大小时,将其加入结果集。使用numvisited向量标记每个数字是否已经被访问过,以确保每个数字在一个排列中只使用一次。在递归过程中,对于每个未访问的......
  • 567. 字符串的排列(中)
    目录题目题解:滑动窗口题目给你两个字符串s1和s2,写一个函数来判断s2是否包含s1的排列。如果是,返回true;否则,返回false。换句话说,s1的排列之一是s2的子串示例1:输入:s1="ab"s2="eidbaooo"输出:true解释:s2包含s1的排列之一("ba").示例2:输入:s1=......
  • 47. 全排列 IIc
    我宣布我已经参透了套路,一次AC/***Returnanarrayofarraysofsize*returnSize.*Thesizesofthearraysarereturnedas*returnColumnSizesarray.*Note:Bothreturnedarrayand*columnSizesarraymustbemalloced,assumecallercallsfree().*/int......
  • 46. 全排列c
    出息了!一次AC/***Returnanarrayofarraysofsize*returnSize.*Thesizesofthearraysarereturnedas*returnColumnSizesarray.*Note:Bothreturnedarrayand*columnSizesarraymustbemalloced,assumecallercallsfree().*/inttemp[10];intvi......
  • 【力扣】排列问题(回溯法)
    问题描述排列问题的难点在于排列要求有序,并且在写的时候发现,如何在选择后面的元素后回过头去选择前面的元素,这是很难处理的,在前面的组合问题中,我们都是用startindex来处理,而在这里就行不通了。容易想到的一种解决方法就是另外设置一个与nums长度相同的used数组来记录元素的遍历......
  • uniapp开发微信小程序,动态排列组件的解决方案。
    微信小程序开发里面,并不支持<component:is="item",虽然微信小程序提供了WXML提供模板(template),对于uniapp并不管用,编译后,所以解决方案,只有目前(截止2022-04-15)只有两个:1.使用v-if,遍历组件,判断位置,来显示组件,达到排列要求2.第二种没那么麻烦,比较神奇,使用flex布局的order属性,外层......
  • AC475B 2024省选联测26 排列
    题意对于所有满足\(1\lea<b\len\)的\((a,b)\)的排列,需要满足:对于\(1\lea<b<c\len\),\((a,c)\)处在\((a,b)\)和\((b,c)\)之间。另外再给出\(m\)个限制,形如\((a,b,c,d)\)要求\((a,b)\)在\((c,d)\)的前面。Sol其实这道题没有那么hard......
  • P2606 [ZJOI2010] 排列计数 题解
    题意:求有多少个排列满足:对于每一个\(2\lei\len\),\(a_i>a_{\frac{i}{2}}\)。首先我们会发现这些数之间的大小关系形成了一个完全二叉树,因为每一个\(a_i\)都必须小于\(a_{2\timesi}\)和\(a_{2\timesi+1}\)。会发现本题的方案和每个位置具体的值并没有关系,而只......