首页 > 编程语言 >代码随想录DAY25 - 回溯算法 - 08/24

代码随想录DAY25 - 回溯算法 - 08/24

时间:2024-08-25 16:23:37浏览次数:19  
标签:24 递归 nums DAY25 isUsed 随想录 back vector 数组

目录

非递减子序列

题干

思路和代码

递归法

递归优化

全排列

题干

思路和代码

递归法

全排列Ⅱ

题干

思路和代码

方法一:用集合 set 去重

方法二:先排序,再用数组去重


非递减子序列

题干

题目:给你一个整数数组 nums ,找出并返回所有该数组中不同的递增子序列,递增子序列中至少有两个元素 。你可以按 任意顺序 返回答案。数组中可能含有重复元素,如出现两个整数相等,也可以视作递增序列的一种特殊情况。

示例 1:

输入:nums = [4,6,7,7] 输出:[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

示例 2:

输入:nums = [4,4,3,2,1] 输出:[[4,4]]

说明:

  • 给定数组的长度不会超过15。

  • 数组中的整数范围是 [-100,100]。

  • 给定数组中可能包含重复数字,相等的数字应该被视为递增的一种情况。

注意:原数组 nums 不一定有序!

链接:. - 力扣(LeetCode)

思路和代码

这道题可以在整数数组中找子集的基础上进行调整,我们可以先找出子集大小大于等于 2 的所有子集,若子集满足非递减序列,则插入结果中。同时,数组中可能含有重复元素,因此我们需要进行去重。和之前的去重操作类似,我们需要在树层去重,而不是树枝去重,即在同一层 for 循环中进行去重,而不是对递归去重。注意:我们不可以对数组 nums 进行排序,不然会改变元素的顺序,求出的递增子序列也不同。

递归法
  • 递归参数和返回值:参数是传入的整数数组和本层递归的起始位置 startIndex,无返回值。

  • 递归结束条件:当遍历完整个数组则返回,写不写终止条件都可以。

  • 递归顺序:先判断当前元素是否满足递增序列,且是否不和之前的元素重复,若满足递增且不重复,则继续递归后续的整数数组寻找递增子序列。

class Solution {
public:
    vector<int> composition;
    vector<vector<int>> result;
    void backTracking(vector<int> &nums, int startIndex){
        if (composition.size() >= 2) result.push_back(composition); // 子集大小大于等于2,才插入结果
		// 写不写终止条件都可以
        unordered_set<int> usedValue; // !!!记录在同一层 for 循环中使用过的 Value
        for (int i = startIndex; i < nums.size(); ++i) {
            if (!composition.empty() && nums[i] < composition.back()){ // 违反递增顺序,continue
                continue; // 因为后续可能还有元素,所以并不 return,而是 continue
            }
            if (usedValue.find(nums[i]) != usedValue.end()) continue; // 去重!
            composition.push_back(nums[i]);
            usedValue.insert(nums[i]); // 插入遍历过的元素
            backTracking(nums,i+1);
            composition.pop_back();
        }
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        backTracking(nums,0);
        return result;
    }
};
递归优化

我们在上一个方法中,用了 unordered_map 来记录遍历过的元素,程序运行的时候对 unordered_set 频繁的insert,相对费时间。而本题中数组的元素范围是[-100,100],范围并不大,因此可以用数组直接做哈希映射,效率会提高。

设定一个大小为 201 的 bool 型数组,下标为 0~200,元素 -100 映射到下标为0的数组空间中,元素 100 映射到下标为200的数组空间。

class Solution {
public:
    vector<int> composition;
    vector<vector<int>> result;
    void backTrack(vector<int> &nums, int startIndex){
        if (composition.size() >= 2) result.push_back(composition);
        // 终止条件写不写都行
        bool isUsed[201] = {false}; // 记录元素在同一层 for 循环是否被使用过,初始化为 false
        for (int i = startIndex; i < nums.size(); ++i) {
            if (!composition.empty() && nums[i] < composition.back()) continue;
            if (isUsed[nums[i]+100]) continue; // 若被使用过,则去重,跳过
            composition.push_back(nums[i]);
            isUsed[nums[i]+100] = true; // 修改当前元素的使用状态
            backTrack(nums,i+1);
            composition.pop_back();
        }
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        backTrack(nums,0);
        return result;
    }
};

全排列

题干

题目:给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

链接:. - 力扣(LeetCode)

思路和代码

递归法

全排列中,每个排列的大小是固定的,我们递归进入下一个排列的位置,for 循环改变该排列位置上的元素。

  • 递归参数和返回值:参数是传入的整数数组和本层递归的起始位置 stratIndex,无返回值。

  • 递归终止条件:当排列的大小已经等于数组的大小时,将排列插入结果集,并返回。

  • 递归顺序:在本层递归中固定好当前元素后,继续递归进行全排列,在下一层递归中将数组中所有其余的元素遍历一遍。因此我们需要用数组 isUsed 记录哪些元素已经被使用过。

class Solution {
public:
    bool isUsed[10]; // 该数组记录元素是否已经被使用过
    vector<int> path;
    vector<vector<int>> result;
    void findPath(vector<int> &nums,int startIndex){
        if (path.size() == nums.size()){
            result.push_back(path);
            return;
        }
        // 每层都要从 0 开始搜索,因为排列是有序的,[1,2]和[2,1]属于两种不同的排列
        for (int i = 0; i < nums.size(); ++i) {
            if (isUsed[i]){ // 该元素已经在排列中被用过,跳过
                continue;
            }
            path.push_back(nums[i]);
            isUsed[i] = true; // 修改当前元素的使用状态
            findPath(nums,i+1);
            path.pop_back();
            isUsed[i] = false;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        findPath(nums,0);
        return result;
    }
};

全排列Ⅱ

题干

题目:给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。

链接:. - 力扣(LeetCode)

思路和代码

本题就是在上一题的思路上进行去重。去重的思路之前说过很多,也就是在当前 for 循环中如果有重复的元素,则跳过。

方法一:用集合 set 去重
class Solution {
public:
    bool isUsed[10];
    vector<int> path;
    vector<vector<int>> result;
    void backTrack(vector<int> &nums){
        if (path.size() == nums.size()){
            result.push_back(path);
            return;
        }
        unordered_set<int> uSet; // 记录当前 for 循环遍历过的元素!!!
        for (int i = 0; i < nums.size(); ++i) {
            if (isUsed[i]) continue;
            if (uSet.find(nums[i]) != uSet.end()) continue; // 去重!!!
            path.push_back(nums[i]);
            isUsed[i] = true;
            uSet.insert(nums[i]);
            backTrack(nums);
            path.pop_back();
            isUsed[i] = false;
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        backTrack(nums);
        return result;
    }
};
方法二:先排序,再用数组去重
class Solution {
public:
    bool isUsed[10];
    vector<int> path;
    vector<vector<int>> result;
    void backTrack(vector<int> &nums){
        if (path.size() == nums.size()){
            result.push_back(path);
            return;
        }
        
        for (int i = 0; i < nums.size(); ++i) {
            if (isUsed[i]) continue;
            if (i > 0 && nums[i] == nums[i-1] && !isUsed[i-1]){ // 对树层去重
                continue; // 去重!!
            }
            path.push_back(nums[i]);
            isUsed[i] = true;
            backTrack(nums);
            path.pop_back();
            isUsed[i] = false;
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        backTrack(nums);
        return result;
    }
};

标签:24,递归,nums,DAY25,isUsed,随想录,back,vector,数组
From: https://blog.csdn.net/chan_lay/article/details/141528919

相关文章

  • FastAdmin目录穿越 CVE-2024-7928
    0x01漏洞描述:FastAdmin是一款基于ThinkPHP+Bootstrap开发的快速后台开发框架。FastAdmin基于Apache2.0开源协议发布,免费且不限制商业使用,目前被广泛应用于各大行业应用后台管理。其接口lang存在目录穿越漏洞,攻击者可通过该漏洞获取系统库敏感信息。0x02影响版本:FastAdmin......
  • 2024暑假总结4(暑假结束总结)
    前言暑假匆匆结束了,现在距军训还有3天时间。回望整个假期,我经历了许多,成长了许多,结识了一些朋友,度过了一个充实、拼搏的集训。现在坐于电脑桌前,感慨万千,我从未想过一个暑假会经历这么多事情。在此感谢成都七中,感谢学校给了我这样一个机会;感谢我的教练hfu,他一直在对我们进行方向......
  • 马克斯CMS4.0原创电影模板-自动采集-简洁蓝色模板-带手机wap模板-特色功能一应俱全202
    马克斯CMS4.0原创电影模板-自动采集-简洁蓝色模板-带手机wap模板-特色功能一应俱全2024电影模板马克斯CMS4.0原创电影模板源码介绍马克斯CMS4.0是一款专为电影网站设计的内容管理系统,提供了丰富的功能和灵活的定制选项。该系统支持自动采集功能,能够自动从互联网上抓取最......
  • 2024.8.25 鲜花
    NTERNETOVERDOSEこの混沌とした令和のインターネットを照らす一筋の光電子の海を漂うオタクに笑顔を未来の平和をお約束躁鬱だけどまかせとけインターネット・エンジェルただいま降臨社会をやめろ家族をやめろ人間関係をやめろ今すぐ薄暗い部屋で青白いライトを浴......
  • 洛谷SCP 2024 第一轮(初赛 J 组)模拟题解析(第三部分:完善程序(1-2))
    完善程序一(补全)#include<bits/stdc++.h>usingnamespacestd;constintMAXN=100000;intn;intvis[MAXN],a[MAXN];vector<int>ans;intcheck(intk){intx=n,top=0;for(inti=0;i<=k;i++)vis[i]=0;while(x......
  • Hitachi Vantara Programming Contest 2024(AtCoder Beginner Contest 368)- C
    题意概述有\(N\)个数,分别为\(H_1,H_2,H_3……H_N\)。你将使用初始化为\(0\)的变量\(T\)重复以下操作,直到所有数的值都变为\(0\)或更少。将\(T\)增加\(1\)。然后,减少最前方\(H_i\)值大于等于\(1\)的值。如果\(T\)是\(3\)的倍数,\(H_i\)的值会减少\(3\);......
  • 每隔10分钟定时关闭并重启夸克网盘电脑客户端,防止下载器卡死宕机死机停止下载的AutoH
     每隔10分钟定时关闭并重启夸克网盘电脑客户端,防止下载器卡死宕机死机停止下载的AutoHotkey脚本2024年8月14日 最近在MicrosoftWindowsServer2022戴尔服务器电脑上下载夸克网盘里的文件夹时发现一个问题,过一段时间后用向日葵控控A2连接服务器发现夸克客户端下载速度为......
  • 跟《经济学人》学英文:2024年08月24日这期 How to attract Indian tourists
    HowtoattractIndiantouristsDestinationsarecompetingforthetravellingrupee原文:INDIANSAREonthemove.In2019internationaldeparturesfromIndiahit27m,anumberthatwillsurelybeexceededthisyearandispredictedtoriseto90mby204......
  • 2024/08/25小记
    给你看看AI实力:问题:如果世界毁灭了人类应该怎么做?(科幻领域)Ai回答:如果世界末日来临,人类应该采取以下措施:紧急行动:疏散到安全地带:识别高点、避难所或其他受保护的区域,并立即疏散。储备基本必需品:搜集足够的食物、水、药品、毯子和其他生存必需品。保持沟通:用电池供电的收音......
  • 题解:P10358 [PA2024] Obrazy
    题解:P10358[PA2024]Obrazy题目传送门即当最小的画框都不可能覆盖整个矩形墙面时,输出−1。[PA2024]Obrazy题目背景PA20243C题目描述题目译自PA2024Runda3Obrazy,感谢Macaronlin提供翻译给定尺寸为$h\timesw$的矩形墙面,以及$n$种尺寸的正方形画框,每种尺寸......