代码随想录算法训练营:26/60

非科班学习算法day26 | LeetCode491:非递减子序列 ,Leetcode46:全排列 ,Leetcode47:全排列|| 


介绍

包含LC的两道题目,还有相应概念的补充。

相关图解和更多版本:

代码随想录 (programmercarl.com)https://programmercarl.com/#%E6%9C%AC%E7%AB%99%E8%83%8C%E6%99%AF


一、LeetCode题目

1.LeetCode491:非递减子序列 

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

题目解析

       和前面问题(子集||)最大的区别在于这里不能够排序,所以去重采用更为普遍的set方法;同时关于中止和收集条件要格外注意。

 c++代码如下:

class Solution {
public:
    // 有重复-不能排序->使用set去重-判断非递减-路径中至少包含2个
    // 结果
    vector<vector<int>> res;
    // 路径
    vector<int> path;
    // 回溯函数
    void backtracking(vector<int>& nums, int index) {
        if (path.size() >= 2) {
            res.push_back(path); // 不要return
        }
        // 创建set
        unordered_set<int> uset;
        for (int i = index; i < nums.size(); i++) {
            // 不满足剪枝
            if (!path.empty() && path.back() > nums[i])
                continue;
            // 树层去重
            if (uset.find(nums[i]) != uset.end())
                continue;

            uset.insert(nums[i]);
            path.push_back(nums[i]);
            backtracking(nums, i + 1);
            path.pop_back();
        }
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        backtracking(nums, 0);
        return res;
    }
};

注意点1:首先是收集路径,这里是有条件的,要求路径里的元素至少有两个;这里不需要额外写中止条件

注意点2:选用set去重的逻辑是一样的,关键在于理解这个set的位置,set是每一层递归进入时新建的,就负责本层的元素去重记录,所以不需要回溯。

 2.Leetcode46: 全排列 

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

题目解析

       排列和组合的区别在于有顺序要求

 C++代码如下: 

class Solution {
public:
    // 顺序要求-没有重复-收集叶子节点
    // 结果
    vector<vector<int>> res;
    // 路径
    vector<int> path;
    // 回溯函数-不需要index
    void backtracking(vector<int>& nums, vector<bool> used) {
        if (path.size() == nums.size()) {
            res.push_back(path); // 需要return结束本层
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (used[i])
                continue;
            path.push_back(nums[i]);
            used[i] = true;
            backtracking(nums, used);
            path.pop_back();
            used[i] = false;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<bool> used = vector<bool>(nums.size(), false);
        backtracking(nums, used);
        return res;
    }
};

注意点1:首先明确需求就是,不需要排序也不需要index,因为没有重复元素,而且收集的是叶子节点,内容包含所有元素所以不需要index,借助used数组可以在遍历过程中跳过已经选过的元素。

3.Leetcode47:全排列||

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

题目解析

       参考子集||还有全排列

C++代码如下:

class Solution {
public:
    // 有重复-排序去重-排列-无index
    // 结果
    vector<vector<int>> res;
    // 路径
    vector<int> path;
    // 回溯函数
    void backtracking(vector<int>& nums, vector<bool> used) {
        if (path.size() == nums.size()) {
            res.push_back(path);
            return;
        }

        for (int i = 0; i < nums.size(); i++) {
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])
                continue;
            if (used[i])
                continue;

            used[i] = true;
            path.push_back(nums[i]);
            backtracking(nums, used);
            used[i] = false;
            path.pop_back();
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<bool> used = vector<bool>(nums.size(), false);
        sort(nums.begin(),nums.end());
        backtracking(nums, used);
        return res;
    }
};

注意点1:一定要记得排序

 

总结


打卡第 26天,坚持!!!

相关推荐

  1. 代码随想算法训练

    2024-07-09 22:08:07       42 阅读
  2. 代码随想算法训练

    2024-07-09 22:08:07       42 阅读
  3. 代码随想算法训练总结

    2024-07-09 22:08:07       32 阅读
  4. 代码随想算法训练总结

    2024-07-09 22:08:07       26 阅读
  5. 代码随想算法训练总结

    2024-07-09 22:08:07       24 阅读
  6. 代码随想训练

    2024-07-09 22:08:07       18 阅读
  7. 代码随想训练

    2024-07-09 22:08:07       15 阅读
  8. 代码随想训练

    2024-07-09 22:08:07       16 阅读

最近更新

  1. matlab中feval()的用法

    2024-07-09 22:08:07       0 阅读
  2. 【Linux常用命令】之mkdir命令

    2024-07-09 22:08:07       0 阅读
  3. 在 macOS 上使用 Jadx 进行 APK 反编译

    2024-07-09 22:08:07       0 阅读
  4. C++生成随机数的两种方法

    2024-07-09 22:08:07       0 阅读
  5. Blazor Webassembly多标签页实现非iframe的实现

    2024-07-09 22:08:07       0 阅读
  6. Lianwei 安全周报|2024.07.22

    2024-07-09 22:08:07       0 阅读

热门阅读

  1. leetcode77组合——经典回溯算法

    2024-07-09 22:08:07       5 阅读
  2. 算法训练营day67

    2024-07-09 22:08:07       8 阅读
  3. 代码随想录第7天 454 、 383 、15、18

    2024-07-09 22:08:07       7 阅读
  4. react中jsx的语法规则

    2024-07-09 22:08:07       6 阅读
  5. transformer的了解

    2024-07-09 22:08:07       8 阅读
  6. Pytest中的钩子函数

    2024-07-09 22:08:07       6 阅读
  7. Vue-插值表达式

    2024-07-09 22:08:07       8 阅读
  8. json数据

    2024-07-09 22:08:07       8 阅读
  9. 小型简易GIT服务器搭建和使用

    2024-07-09 22:08:07       7 阅读
  10. 开源许可(Open Source License)

    2024-07-09 22:08:07       7 阅读
  11. 使用 HAProxy 进行 MySQL 负载均衡

    2024-07-09 22:08:07       7 阅读