AI 助理
备案控制台
开发者社区 人工智能 文章 正文

LeetCode刷题day46

2022-12-11 69
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： LeetCode刷题day46

78. 子集

题目描述

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]


示例 2：

输入：nums = [0]
输出：[[],[0]]


思路分析

如果把 子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！


子集也是一种组合问题，因为它的集合是无序的，子集{1,2} 和 子集{2,1}是一样的。


那么既然是无序，取过的元素不会重复取，写回溯算法的时候，for就要从startIndex开始，而不是从0开始！


以示例中nums = [1,2,3]为例把求子集抽象为树型结构，如下：


62d3abc6759ece081af10b6b08713e9a.png

回溯三部曲


确定递归参数和返回值

递归参数:需要遍历的数组 vector &nums,每层遍历的起始下标startIndex .


返回值:由于定义全局变量来保存最终结果集以及单一结果,所以并不需要返回值.


确定结束条件

由于这次是寻找所有的组合,所以并不需要结束条件.没递归一层就把对应的结果放入到结果集中.


确定单层递归逻辑

将当前组合数加入单一结果集,递归,回来后进行回溯.进行下一次循环.


参考代码

#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int> &nums,int startIndex){
  result.push_back(path);
  for(int i = startIndex; i < nums.size(); i++){
    path.push_back(nums[i]);
    backtracking(nums,i+1);
    path.pop_back();
  }
}
vector<vector<int>> subsets(vector<int>& nums) {
  result.clear();
  path.clear();
  backtracking(nums,0);
  return result;
}


90. 子集 II

题目描述

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。


示例 1：

输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]


示例 2：

输入：nums = [0]
输出：[[],[0]]


思路分析

这个题的数组nums可能包含重复元素,则需要对树层进行去重. 目前我们有三种去重方法:利用vector used , 利用startIndex, 利用ordered_set ,下面我们将逐一进行演示.


用示例中的[1, 2, 2] 来举例，如图所示： （注意去重需要先对集合排序）


67b4e26eab3a8a3c382dd84d1ceec285.png

本题不再分析递归三部曲了,关键部分将添加相关注释.

参考代码

方法一: 利用vector used 去重

vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int> &nums,int startIndex,vector<bool> &used){//参数相比上次就过个used
  result.push_back(path);
  for(int i = startIndex; i < nums.size(); i++){
    if(i > 0 && nums[i]==nums[i-1] && used[i-1]==false){//如果同一树层元素重复了,则跳过本次循环
      continue;
    }
    path.push_back(nums[i]);
    used[i] = false;
    backtracking(nums,i+1,used);
        //递归后的回溯
    path.pop_back();
    used[i] = true;
  }
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
  vector<bool> used(nums.size());//定义一个used数组,用来树层去重
  result.clear();
  path.clear();
  sort(nums.begin(),nums.end());
  backtracking(nums,0,used);
  return result;
}

方法二:使用startIndex去重

void backtracking(vector<int> &nums,int startIndex){
  result.push_back(path);
  for(int i = startIndex; i < nums.size(); i++){
    if(i > startIndex && nums[i]==nums[i-1]){ //使用startIndex去重也可以. 
      continue;
    }
    path.push_back(nums[i]);
    backtracking(nums,i+1,used);
    path.pop_back();
  }
}

方法三:使用ordered_set uset去重

vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, int startIndex, vector<bool>& used) {
    result.push_back(path);
    unordered_set<int> uset;//定义
    for (int i = startIndex; i < nums.size(); i++) {
        if (uset.find(nums[i]) != uset.end()) {//如果能在uset中找到当前值nums[i],则当前树层重复
            continue;
        }
        uset.insert(nums[i]);//由于uset仅用于去重,所以后文不用进行回溯.不然就无意义了
        path.push_back(nums[i]);
        backtracking(nums, i + 1, used);
        path.pop_back();
    }
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
    result.clear();
    path.clear();
    vector<bool> used(nums.size(), false);
    sort(nums.begin(), nums.end()); // 去重需要排序
    backtracking(nums, 0, used);
    return result;
}

491. 递增子序列

题目描述

给你一个整数数组 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]]


思路分析

本题的一个坑: 不能对nums进行排序, 不然就和示例对不上了.

以[4, 7, 6, 7]这个数组为例，抽象为树形结构如图：

a9be745e0b231f90166f08192d3c712f.png


递归三部曲:


确定递归参数和返回值

递归参数:虽然求的是序列,有顺序,但是因为元素不可以重复,并且有一定的顺序(从前往后的方向),所以需要startIndex. 当然也需要递归的数组: vector&nums


返回值: 因为定义了全局变量,所以并不需要


确定递归结束条件

当元素个数 path.size() >= 2,可将临时组合存入结果集中.


确定单层递归逻辑

由于数组中有重复元素,所以需要进行去重.而且是无序的,所以采用 ordered_set uset. 另外序列也需要递增


每次循环判断当前组合数是否本层重复以及递增,如果是,则放入临时组合集=> uset更新=>递归=>回溯=>循环下一个数. 如果不是,则进入跳过当前的数,进行下一个循环.


备注:因为 -100 <= nums[i] <= 100, 数据范围较小所以我们可以使用 int used[201]去重.这个相比ordered_set效率更高.


参考代码

方法一:使用unordered_set uset去重

vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>&nums,int startIndex) {//因为元素不可以重复,并且有一定的顺序,所以需要 startIndex参数
  if(path.size()>1) {
    result.push_back(path);
        //return; 这里不需要return 哦,因为序列是 >= 2 的.
  }
  unordered_set<int> uset;//用于去重
  for(int i = startIndex; i < nums.size(); i++) {
    if((!path.empty() && nums[i] < path.back() ) || uset.find(nums[i])!=uset.end()) { //元素不是递增  || 元素和之前的重复  都不可
      continue;
    }
    path.push_back(nums[i]);
    uset.insert(nums[i]);//不用进行回溯,只用于判断该元素是否本层中使用过
    backtracking(nums,i+1);
    path.pop_back();
  }
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
  result.clear();
  path.clear();
  backtracking(nums,0);
  return result;
}


方法二:使用int[201] used去重


//方法二,使用int数组来去重 
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>&nums,int startIndex) {//因为元素不可以重复,并且有一定的顺序,所以需要 startIndex参数
  if(path.size()>1) {
    result.push_back(path);
  }
  int used[201] = {0};//用于去重  -100-100   0 200
  for(int i = startIndex; i < nums.size(); i++) {
    if((!path.empty() && nums[i] < path.back() ) || used[nums[i]+100]) { //元素不是递增  || 元素和之前的重复  都不可
      continue;
    }
    path.push_back(nums[i]);
    used[nums[i]+100] = 1;
    backtracking(nums,i+1);
    path.pop_back();
  }
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
  result.clear();
  path.clear();
  backtracking(nums,0);
  return result;
}


46. 全排列

题目描述

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

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]


示例 3：

输入：nums = [1]
输出：[[1]]

思路分析

排列里面的数字有一定顺序性,而组合与顺序无关.这决定了startIndex的起始位置.

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


c1bcae3c39804101fb10c66c95b708e6.png


回溯三部曲


确定递归参数和返回值

递归参数:递归的数组vector&nums ,用于标记元素的数组 vector& used


递归返回值:定义全局变量,无需返回值.


确定递归结束条件

全排列要求排列后的数据和数组里面的数据个数相同. 所以结束条件: path.size()==nums.size()


确定单层递归逻辑

判断当前循环的数是否被使用过,没被使用=>放入临时全排列集=>改变used=>递归=>回溯=>循环下一个数


注意:used数组常用于组合中树层/树枝的去重(常伴随着元素先排序), 也常用于排列中数据的标记. ordered_set常用于进行树层去重.


参考代码


vector<int> path;
vector<vector<int>> result;
void backtracking(vector<int>&nums,vector<bool>& used){//used用于取没有使用过的元素 
  if(path.size()==nums.size()){
    result.push_back(path);
    return;
  }
  for(int i = 0;i < nums.size();i++){
    if(!used[i]){
      path.push_back(nums[i]);
      used[i] = true;
      backtracking(nums,used);
      path.pop_back();
      used[i] = false;
    }
  }
}
vector<vector<int>> permute(vector<int>& nums) {
  path.clear();
  result.clear();
  vector<bool> used(nums.size(),false);
  backtracking(nums,used);
  return result;
}


47. 全排列 II

题目描述

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

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

示例 2：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]


思路分析

这道题目和 46.全排列 的区别在与给定一个可包含重复数字的序列，要返回所有不重复的全排列,牵涉到树层的去重. 我们可以采取 vector used , 利用ordered_set进行去重.


我以示例中的 [1,1,2]为例 ,抽象为一棵树，去重过程如图

ced2339a65deaac3e340244978ddd5d2.png

参考代码

方法一:使用vector used去重

#include<bits/stdc++.h>
using namespace std;
vector<int> path;
vector<vector<int>> result;
void backtracking(vector<int>&nums,vector<bool>& used) {
  if(path.size()==nums.size()) {
    result.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]) {
      path.push_back(nums[i]);
      used[i] = true;
      backtracking(nums,used);
      path.pop_back();
      used[i] = false;
    }
  }
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
  path.clear();
  result.clear();
  sort(nums.begin(),nums.end());//用到同层去重必排序
  vector<bool> used(nums.size(),false);
  backtracking(nums,used);
  return result;
}


方法二:使用ordered_set进行去重

void backtracking (vector<int>& nums, vector<bool>& used) {
    if (path.size() == nums.size()) {
        result.push_back(path);
        return;
    }
    unordered_set<int> uset; // 控制某一节点下的同一层元素不能重复
    for (int i = 0; i < nums.size(); i++) {
        if (uset.find(nums[i]) != uset.end()) {
            continue;
        }
        if (used[i] == false) {
            uset.insert(nums[i]); // 记录元素
            used[i] = true;
            path.push_back(nums[i]);
            backtracking(nums, used);
            path.pop_back();
            used[i] = false;
        }
    }
}
文章标签：
算法
关键词：
LeetCode刷题
爱编程的大李子
目录
相关文章
yantuguiguziPGJ
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案，包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行，每个问题都给出了至少一种实现方法。
yantuguiguziPGJ
56 6
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
BetterBench
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法，用于按照之字形顺序打印二叉树的层次遍历结果，实现了在奇数层正序、偶数层反序打印节点的功能。
BetterBench
56 6
BetterBench
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 26. 树的子结构
这篇文章提供了解决LeetCode上"剑指Offer 26. 树的子结构"问题的Python代码实现和解析，判断一棵树B是否是另一棵树A的子结构。
BetterBench
50 4
BetterBench
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法，提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法，并给出了Python实现代码。
BetterBench
113 2
楠竹11
|
17天前
|
机器学习/深度学习 人工智能 自然语言处理
280页PDF，全方位评估OpenAI o1，Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来，OpenAI的o1模型在大型语言模型（LLMs）中脱颖而出，展现出卓越的推理能力和知识整合能力。基于Transformer架构，o1模型采用了链式思维和强化学习等先进技术，显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
楠竹11
16 1
yantuguiguziPGJ
|
2月前
|
数据采集 负载均衡 安全
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案，包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等，每个问题都给出了至少一种实现方法，涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
yantuguiguziPGJ
38 3
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
BetterBench
|
3月前
|
索引 Python
【Leetcode刷题Python】从列表list中创建一颗二叉树
本文介绍了如何使用Python递归函数从列表中创建二叉树，其中每个节点的左右子节点索引分别是当前节点索引的2倍加1和2倍加2。
BetterBench
56 7
BetterBench
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 30. 包含min函数的栈
本文提供了实现一个包含min函数的栈的Python代码，确保min、push和pop操作的时间复杂度为O(1)。
BetterBench
27 4
BetterBench
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 22. 链表中倒数第k个节点
Leetcode题目"剑指 Offer 22. 链表中倒数第k个节点"的Python解决方案，使用双指针法找到并返回链表中倒数第k个节点。
BetterBench
52 5
BetterBench
|
3月前
|
算法 Python
【Leetcode刷题Python】 LeetCode 2038. 如果相邻两个颜色均相同则删除当前颜色
本文介绍了LeetCode 2038题的解法，题目要求在一个由'A'和'B'组成的字符串中，按照特定规则轮流删除颜色片段，判断Alice是否能够获胜，并提供了Python的实现代码。
BetterBench
50 3