首页 > 其他分享 >Day 22 回溯法part04| LeetCode 491.递增子序列,46.全排列,47.全排列 II

Day 22 回溯法part04| LeetCode 491.递增子序列,46.全排列,47.全排列 II

时间:2024-09-22 20:24:29浏览次数:9  
标签:排列 22 nums 46 int used new path backtraking

491.递增子序列

491. 非递减子序列

    class Solution {
        public  List<Integer> path=new LinkedList<>();
        public  List<List<Integer>> res=new ArrayList<>();
        public List<List<Integer>> findSubsequences(int[] nums) {

            backtraking(nums,0);

            return res;

        }
        void backtraking(int[] nums,int startIndex)
        {
            if(path.size()>=2)

            {
                res.add(new ArrayList<>(path));
            }
        
            HashSet<Integer> hs=new HashSet<>();
            for(int i=startIndex;i<nums.length;i++)
            {
                //去重,树层不能重复
                if(!path.isEmpty()&&path.get(path.size()-1)>nums[i]|| hs.contains(nums[i])) continue;

                hs.add(nums[i]);
                path.add(nums[i]);

                backtraking(nums,i+1);

                path.remove(path.size()-1);

            }

        }
    }

46.全排列

46. 全排列

class Solution {
        public  List<Integer> path=new LinkedList<>();
        public  List<List<Integer>> res=new ArrayList<>();

        public List<List<Integer>> permute(int[] nums) {

            int[] used=new int[nums.length];
            backtraking(nums,used);
            return res;
        }

        void backtraking(int[] nums,int[] used)
        {

            if (path.size()==nums.length)
            {
                res.add(new ArrayList<>(path));
                return;
            }
          for(int i=0;i< nums.length;i++)
          {
              if(used[i]==0)
              {
                  path.add(nums[i]);
                  used[i]=1;
                  backtraking(nums,used);
                  path.remove(path.size()-1);
                  used[i]=0;
              }

          }
        }
    }

47.全排列 II

47. 全排列 II

  class Solution {
        public  List<Integer> path=new LinkedList<>();
        public  List<List<Integer>> res=new ArrayList<>();

        public List<List<Integer>> permuteUnique(int[] nums) {

            Arrays.sort(nums);
            int[] used=new int[nums.length];
            backtraking(nums,used);
            return res;
        }

        void backtraking(int[] nums,int[] used)
        {

            if (path.size()==nums.length)
            {
                res.add(new ArrayList<>(path));
                return;
            }
          for(int i=0;i< nums.length;i++)
          {
             if(i>0&&nums[i]==nums[i-1]&&used[i-1]==0)continue;
              if(used[i]==0)
              {
                  path.add(nums[i]);
                  used[i]=1;
                  backtraking(nums,used);
                  path.remove(path.size()-1);
                  used[i]=0;
              }

          }
        }
  }

332.重新安排行程 (一刷跳过)

51.N皇后(一刷跳过)

37.解数独(一刷跳过)

标签:排列,22,nums,46,int,used,new,path,backtraking
From: https://www.cnblogs.com/FreeDrama/p/18425798

相关文章

  • 9.22 NOIP 模拟赛 R7
    省流:高一rk6,整体rk10。考场上直接用前几天学的map优化dp优化我T2的\(O(n^4)\)代码,然后过了\(4000\)!感觉后面dp的优化是比较好想的,如果想到填表法的话。还要注意处理大小依赖关系,故从小到大加入的trick。T4最后几分钟极限过样例,random_shuffle过\(200\)!(其实当......
  • Cloudflare WARP+ 又能用了!2024年9月22日,新增MASQUE协议
    1.Windows用户1.1WARP+官网下载客户端WARP+官网:进入WARP+官网,下载对应客户端。 双击运行,完成安装。1.2新建mdm.xml文件在C:\ProgramData\Cloudflare目录下,新建文本文件:mdm.xml,复制以下内容进去,并保存<dict><key>warp_tunnel_protocol</key><string>masque......
  • [PTA]7-2 输出全排列
    [PTA]7-2输出全排列请编写程序输出前n个正整数的全排列(n<10),并通过9个测试用例(即n从1到9)观察n逐步增大时程序的运行时间。输入格式:输入给出正整数n(<10)。输出格式:输入样例:3输出样例:123132213231312321代码#include<stdio.h>#defineYES1#defineNO......
  • 【2024潇湘夜雨】WIN 11_Pro_24H2.26120.1843软件选装纯净特别版9.22
    【系统简介】=============================================================1.本次更新母盘来自WIN11_Pro_24H2.26120.1843.2.全程离线精简、无人值守调用优化处理制作。部分优化适配系统可能要重启几次,即使显示适配失败也不要在意,可能部分优化不适用。3.OS版本号为26120.1843。......
  • 【蓝桥杯】2024.9.22算法赛——灵魂问题\全栈项目小组(C++)
    一、灵魂问题题目灵魂问题题目分析1.要求输出一个整数2.题目在玩脑筋急转弯,关键句子标出来了——糖什么的根本不重要。所以咖啡不加糖,答案是0!!!代码#include<iostream>usingnamespacestd;intmain(){ cout<<0; return0;}二、全栈项目小组题目全栈项目小组......
  • 2024.9.22 扩展 centos7的文件系统空间
    从lsblk的输出可以看出,你的磁盘/dev/sda的总大小是30G,但sda3分区只使用了17.7G。要扩展/dev/sda3分区,使其利用整个磁盘上的可用空间,你可以按照以下步骤进行。扩展/dev/sda3分区备份数据在操作分区之前,建议你备份重要数据。进入fdisk调整分区使用fdisk工......
  • P8818 [CSP-S 2022] 策略游戏
    原题链接学习笔记感觉非常复杂?对于现在的我还是有深度的,首先第一个大坑就是并不需要真的求出c矩阵,这个题意就是让你在区间中选数,但要求乘积最大,所以要分讨。你假定\(a_i\ge0\),那这时如果\(min(b_i)\ge0\)取\(max(a_i)\),否则取\(min(a_i\ge0)\),相反的,假定\(a_i<0\),那这时如......
  • 2024.9.22 计划
    项目部分搞清楚声音信号怎么转化为热力图形式如果有时间就搞一下怎么将热力图和光学图或者视频怎么叠加个人学习部分多重背包问题III庆功会总结如果得到了声音的信号,可以经过处理用python绘制出来对应位置的热力图,这里采用随机生成的声音信号,代码如下:importnump......
  • Leetcode 2464. 有效分割中的最少子数组数目
    1.题目基本信息1.1.题目描述给定一个整数数组nums。如果要将整数数组nums拆分为子数组后是有效的,则必须满足:每个子数组的第一个和最后一个元素的最大公约数大于1,且nums的每个元素只属于一个子数组。返回nums的有效子数组拆分中的最少子数组数目。如果不能进......
  • 游戏中的状态控制 适合于全部游戏 scratch 20240922_111017
    完整的游戏游戏封面游戏进行游戏暂停游戏结束预设状态值0欢迎界面1游戏进行2游戏暂停3游戏结束需要定义变量来适时的改变他们变量使用英文stat背景代码在背景的代码里定义了【欢迎画面】的自制积木实现游戏的状态值的初始化等待玩家输入如果玩家输入了1那么......