首页 > 其他分享 >代码随想录刷题day25丨491.递增子序列 ,46.全排列 ,47.全排列 II

代码随想录刷题day25丨491.递增子序列 ,46.全排列 ,47.全排列 II

时间:2024-09-07 18:52:58浏览次数:13  
标签:排列 nums day25 ArrayList 随想录 int used new path

代码随想录刷题day25丨491.递增子序列 ,46.全排列 ,47.全排列 II

1.题目

1.1递增子序列

  • 题目链接:491. 非递减子序列 - 力扣(LeetCode)

    在这里插入图片描述

  • 视频讲解:回溯算法精讲,树层去重与树枝去重 | LeetCode:491.递增子序列_哔哩哔哩_bilibili

  • 文档讲解:https://programmercarl.com/0491.%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97.html

  • 解题思路:回溯

    • 用[4, 7, 6, 7]这个数组来举例,抽象为树形结构如图:

      在这里插入图片描述

  • 代码:

    class Solution {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
    
        public List<List<Integer>> findSubsequences(int[] nums) {
            backtracking(nums, 0);
            return result;
        }
    
        void backtracking(int[] nums, int startIndex) {
    
            if(path.size() >= 2){
                result.add(new ArrayList<>(path));
            }
    
            Set<Integer> tempSet = new HashSet<>();// 使用set对本层元素进行去重
    
            for (int i = startIndex; i < nums.length; i++) {
                if((!path.isEmpty() && nums[i] < path.get(path.size() - 1)) || tempSet.contains(nums[i])){
                    continue;
                }
                tempSet.add(nums[i]);
                path.add(nums[i]);
                backtracking(nums,i + 1);
                path.remove(path.size() - 1);
            }
        }
    }
    
  • 总结:

    • 本题求自增子序列,是不能对原数组进行排序的,排完序的数组都是自增子序列了。所以不能使用之前的去重逻辑!
    • 数组,set,map都可以做哈希表,而且数组干的活,map和set都能干,但如果数值范围小的话能用数组尽量用数组

1.2全排列

  • 题目链接:46. 全排列 - 力扣(LeetCode)

    在这里插入图片描述

  • 视频讲解:组合与排列的区别,回溯算法求解的时候,有何不同?| LeetCode:46.全排列_哔哩哔哩_bilibili

  • 文档讲解:https://programmercarl.com/0046.%E5%85%A8%E6%8E%92%E5%88%97.html

  • 解题思路:回溯

    • 以[1,2,3]为例,抽象成树形结构如下:

      在这里插入图片描述

    • 回溯三部曲

      • 递归函数参数

        List<List<Integer>> result = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        void backtracking(int[] nums,boolean[] used)
        
      • 递归终止条件

        if(path.size() == nums.length){
            result.add(new ArrayList<>(path));
            return;
        }
        
      • 单层搜索的逻辑

        for(int i = 0;i < nums.length;i++){
            if(used[i] == true){
                continue;
            }
            path.add(nums[i]);
            used[i] = true;
            backtracking(nums,used);
            used[i] = false;
            path.remove(path.size() - 1);
        }
        
  • 代码:

    class Solution {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        public List<List<Integer>> permute(int[] nums) {
            boolean[] used = new boolean[nums.length];
            backtracking(nums,used);
            return result;
        }
    
        void backtracking(int[] nums,boolean[] used){
            if(path.size() == nums.length){
                result.add(new ArrayList<>(path));
                return;
            }
    
            for(int i = 0;i < nums.length;i++){
                if(used[i] == true){
                    continue;
                }
                path.add(nums[i]);
                used[i] = true;
                backtracking(nums,used);
                used[i] = false;
                path.remove(path.size() - 1);
            }
        }
    }
    
  • 总结:

    • 每层都是从0开始搜索而不是startIndex
    • 需要used数组记录path里都放了哪些元素了

1.3全排列 II

  • 题目链接:47. 全排列 II - 力扣(LeetCode)

    在这里插入图片描述

  • 视频讲解:回溯算法求解全排列,如何去重?| LeetCode:47.全排列 II_哔哩哔哩_bilibili

  • 文档讲解:https://programmercarl.com/0047.%E5%85%A8%E6%8E%92%E5%88%97II.html

  • 解题思路:回溯

    • 去重一定要对元素进行排序,这样我们才方便通过相邻的节点来判断是否重复使用了

    • 以示例中的 [1,1,2]为例 (为了方便举例,已经排序)抽象为一棵树,去重过程如图:

      在这里插入图片描述

    • 图中我们对同一树层,前一位(也就是nums[i-1])如果使用过,那么就进行去重。

  • 代码:

    class Solution {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
    
        public List<List<Integer>> permuteUnique(int[] nums) {
            boolean[] used = new boolean[nums.length];
            Arrays.sort(nums);
            backtracking(nums, used);
            return result;
        }
    
        void backtracking(int[] nums, boolean[] used) {
            if (path.size() == nums.length) {
                result.add(new ArrayList<>(path));
                return;
            }
    
            for (int i = 0; i < nums.length; i++) {
                if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                    continue;
                }
                if (used[i] == true) {
                    continue;
                }
                path.add(nums[i]);
                used[i] = true;
                backtracking(nums, used);
                used[i] = false;
                path.remove(path.size() - 1);
            }
        }
    }
    
  • 总结:

    • 一般来说:组合问题和排列问题是在树形结构的叶子节点上收集结果,而子集问题就是取树上所有节点的结果

标签:排列,nums,day25,ArrayList,随想录,int,used,new,path
From: https://blog.csdn.net/m0_75195038/article/details/142000389

相关文章

  • 代码随想录day 53 || 图论4
    字符串接龙varqueue*list.ListvarvisitMapmap[string]boolfuncmain(){ varcountint fmt.Scanf("%d",&count) varstartStr,endStrstring fmt.Scanf("%s%s",&startStr,&endStr) varstrList=make([]string,count) fo......
  • 代码随想录算法训练营第五十天 | 98. 所有可达路径
    目录98.所有可达路径思路图的存储邻接矩阵         邻接表深度优先搜索1.确认递归函数,参数2.确认终止条件3.处理目前搜索节点出发的路径方法一:邻接矩阵写法方法二:邻接表写法98.所有可达路径题目链接:卡码网题目链接(ACM模式)文章讲解:代码随想录 ......
  • 排列组合(一)
    目录排列组合示例题目题目答案与解析开学后的第一篇博文,太不容易了。。。。。今后我会做更多关于我要打的比赛要考的一些知识,也方便自己回顾。最后有很多例题给大家练练手哦。前言排列组合是CCF(中国计算机学会(ChinaComputerFederation),大家可以去看看它的官网:http......
  • 代码随想录算法训练营第十天| 232.用栈实现队列 、 225. 用队列实现栈 、20. 有效的括
    学习文章链接:代码随想录文章目录一、232.用栈实现队列二、225.用队列实现栈三、20.有效的括号四、1047.删除字符串中的所有相邻重复项一、232.用栈实现队列题目链接:232.用栈实现队列栈的操作:stack<int>s;s.empty();//如果栈为空则返回true,......
  • 代码随想录day52 || 图论3
    岛屿最大的孤岛面积packagemainimport"fmt"vardirPath=[4][2]int{{0,-1},{1,0},{0,1},{-1,0}}varvisited[][]boolvarflagboolvarresintfuncmain(){ varx,yint fmt.Scanf("%d%d",&x,&y) //x行y列初始化临界矩阵 vargra......
  • 【代码随想录训练营第42期 Day51打卡 - 岛屿问题 - 卡码网 99. 岛屿数量 100. 岛屿的
    目录一、做题心得二、题目与题解题目一:99.岛屿数量题目链接题解1:DFS 题解2:BFS 题目二:100.岛屿的最大面积题目链接题解:DFS 三、小结一、做题心得今天打卡的是经典的岛屿问题:分别从两个方向进行探讨--深搜(DFS)与广搜(BFS)。作为这两大基本搜索最经典的例题,今天......
  • 代码随想录day52 || 图论搜索 岛屿数量,岛屿的最大面积
    图遍历dfs深度优先搜索bfs广度优先搜索200岛屿数量(dfs)vardirPath=[][]int{{0,-1},{1,0},{0,1},{-1,0}}//上,右,下,左varvisited[][]boolfuncnumIslands(grid[][]byte)int{ //dfs深度优先遍历,对于每一个节点,按照上下左右四个固定顺序遍历,然后到下......
  • 代码随想录算法训练营|Day07 LeetCode 344.反转字符串 ,541.反转字符串||,卡玛网54.替换
    344.反转字符串344.反转字符串-力扣(LeetCode)classSolution{public:voidreverseString(vector<char>&s){intlens=s.size();intright,left;if(lens%2!=0)//奇数个{right=lens/2+1;left=l......
  • 代码随想录训练营 Day50打卡 图论part01 理论基础 98. 所有可达路径
    代码随想录训练营Day50打卡图论part01一、理论基础DFS(深度优先搜索)和BFS(广度优先搜索)在图搜索中的核心区别主要体现在搜索策略上:1、搜索方向:DFS:深度优先,一条路走到黑。DFS从起点开始,选择一个方向深入到底,遇到死胡同再回溯,换一个方向继续探索。这种方式适合解决路径......
  • 给自己复盘的随想录笔记-字符串练习题
    反转字符串344.反转字符串-力扣(LeetCode)双指针+元素交换 classSolution{publicvoidreverseString(char[]s){chartemp;intl=0,r=s.length-1;while(l<r){temp=s[l];s[l]=s[r];s[r]=temp;l++;......