当前位置: 首页 > news >正文

leetcode每日一题35

90. 子集 II

回溯嘛
子集啊排列组合啊棋盘啊都是回溯
回溯三部曲走起
跟78.子集比,本题给出的数组里存在重复元素了
所以在取元素时,如果同一层里取过某个元素,那么在该层就不能取重复的该元素了
如给出的数组[1,2,2]
可以在某一次递归中第一个取2放进子集,但后面的递归就不允许第一个取2放进子集里了
详情可以看代码随想录的图
代码随想录
所以要有一个数组used记录该层里取过的数

  1. 递归函数参数
    回溯问题一般涉及两个全局变量:
    保存本次递归中符合条件的结果path
    保存所有符合条件的结果的集合result
    以及回溯函数backtracking,因为是求子集问题,所以取过的元素不能重复取,所以回溯时,for循环要从startIndex开始,而不是从0开始
vector<int> path;
vector<vector<int>> result;
void backtracking(vector<int>& nums, int startIndex, vector<bool>& used)
  1. 递归终止条件
    当此时的startIndex已经大于数组长度时,就没有没取过的数组元素了,本次递归就终止了
if(startIndex>=nums.size()){return;
}
  1. 单层搜索逻辑
    单层的搜索逻辑是
    先将取出来的数存入path,再递归调用自身,然后回溯,删掉刚才取出来的数
path.push_back(nums[i]);
backtracking(……);
path.pop_back();

本题中,要判断取的nums[i]有没有使用过
如果没有,那么在backtracking要传入used数组,所以要递归前标记nums[i]已经被使用过了而递归后,需要回溯,从path中删除nums[i],所以要恢复为nums[i]未被使用

if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {continue;
}//判定nums[i]有没有使用过
path.push_back(nums[i]);
used[i]=true;
backtracking(nums, i+1,used);
used[i]=false;
path.pop_back();

所以,回溯算法模板为

void backtracking(参数) {收集子集result.push_back(path);if (终止条件) {存放结果;return;}for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {处理节点;backtracking(路径,选择列表); // 递归回溯,撤销处理结果}
}

那么组合起来,本题的回溯函数为

vector<int> path;
vector<vector<int>> result;
void backtracking(vector<int>& nums, int startIndex, vector<bool>& used){result.push_back(path);//收集子集if(startIndex>=nums.size()){return;}for(int i =startIndex;i<nums.size();i++){if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {continue;}//判定nums[i]有没有使用过path.push_back(nums[i]);used[i]=true;backtracking(nums, i+1,used);used[i]=false;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;}

整理一下,得到最终代码:

class Solution {
private:vector<int> path;vector<vector<int>> result;void backtracking(vector<int>& nums, int startIndex, vector<bool>& used){result.push_back(path);//收集子集,要放在判定停止条件前,防止漏数if(startIndex>=nums.size()){return;}for(int i =startIndex;i<nums.size();i++){if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {continue;}//判定nums[i]有没有使用过path.push_back(nums[i]);used[i]=true;backtracking(nums, i+1,used);used[i]=false;path.pop_back();}}
public: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;}
};

相关文章:

leetcode每日一题35

90. 子集 II 回溯嘛 子集啊排列组合啊棋盘啊都是回溯 回溯三部曲走起 跟78.子集比&#xff0c;本题给出的数组里存在重复元素了 所以在取元素时&#xff0c;如果同一层里取过某个元素&#xff0c;那么在该层就不能取重复的该元素了 如给出的数组[1,2,2] 可以在某一次递归中第一…...

第二十章——多线程

一.线程简介 线程的特点 1.进程是资源分配的最小单位&#xff0c;线程是最小的执行单位 2.一个进程可以有多个线程 3.线程共享进程资源 二.创建线程 1.继承Thread类 1.Thread类是java.lang包中的一个类&#xff0c;从这个类实例化的对象代表线程&#xff0c;程序员启动一个新…...

【FGPA】Verilog:JK 触发器 | D 触发器 | T 触发器 | D 触发器的实现

0x00 JK 触发器 JK 触发器是 RS 触发器和 T 触发器的组合&#xff0c;有两个输入端 J 和 K&#xff0c;如果两个输入端都等于 1&#xff0c;则将当前值反转。 行为表 状态图 Timing Diagram Circuit JK 触发器的设计目的是防止 RS 触发器在输入 S 和 R 均等于 …...

【人工智能】人工智能的技术研究与安全问题的深入讨论

前言 人工智能&#xff08;Artificial Intelligence&#xff09;&#xff0c;英文缩写为AI。 它是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。人工智能是新一轮科技革命和产业变革的重要驱动力量。 &#x1f4d5;作者简介&#x…...

苹果提醒事项怎么用?几个简单步骤就能学会!

苹果提醒事项可以帮助你轻松管理待办事项&#xff0c;让你更好地安排自己的时间和工作。但是&#xff0c;有些小伙伴可能对如何使用这个功能还有一些疑问。苹果提醒事项怎么用&#xff1f;不要担心&#xff0c;小编将为大家提供使用提醒事项的方法&#xff0c;帮助你学会如何使…...

<HarmonyOS第一课>从简单的页面开始 【课后考核】

判断题 在Column容器中的子组件默认是按照从上到下的垂直方向布局的&#xff0c;其主轴的方向是垂直方向&#xff0c;在Row容器中的组件默认是按照从左到右的水平方向布局的&#xff0c;其主轴的方向是水平方向。 正确(True)List容器可以沿水平方向排列&#xff0c;也可以沿垂…...

如何实现按需加载

如何实现按需加载 实现按需引入的步骤&#xff1a; ES6模块语法&#xff1a; 确保你的组件库使用了ES6模块语法&#xff0c;这是按需引入的基础。 拆分组件&#xff1a; 将组件库拆分成独立的模块&#xff0c;每个模块包含一个组件。这样&#xff0c;只有需要的组件才会被引入…...

Vue3-admin-template的表格合计计算

直接上代码&#xff1a; <el-table:data"lists"style"width: 100%"max-height"500":header-cell-style"{ textAlign: center }":cell-style"{ textAlign: center }"show-summary:summary-method"getSummaries"…...

spring JdbcTemplate 快速入门

概述 Spring JDBC Template 是 Spring Framework 提供的一个简化 JDBC 操作的模板类。它封装了一些常见的 JDBC 操作&#xff0c;使得开发者在使用 JDBC 时能够更加便捷、简洁&#xff0c;同时也提供了异常处理和资源管理等功能。 导入pom 使用C3P0作为数据源 <project x…...

leetcode:用队列实现栈(后进先出)

题目描述 题目链接&#xff1a;225. 用队列实现栈 - 力扣&#xff08;LeetCode&#xff09; 题目分析 我们先把之前写的队列实现代码搬过来 用队列实现栈最主要的是实现栈后进先出的特点&#xff0c;而队列的特点是先进先出&#xff0c;那么我们可以用两个队列来实现 一个队…...

使用opencv实现更换证件照背景颜色

1 概述 生活中经常要用到各种要求的证件照电子版&#xff0c;红底&#xff0c;蓝底&#xff0c;白底等&#xff0c;大部分情况我们只有其中一种&#xff0c;本文通过opencv实现证件照背景的颜色替换。 1.1 opencv介绍 OpenCV&#xff08;Open Source Computer Vision Librar…...

Unity打出的安卓包切换后台再恢复前台,卡顿许久问题记录

连接AndroidStudio发现当切换后台时提示&#xff1a;D/Unity: Multi-casting "[IP] 192.168.31.231 [Port] 55000 [Flags] 19 [Guid] 1268732307 [EditorId] 264356214 [Version] 1048832 [Id] AndroidPlayer(11,Xiaomi_M2012K11AC192.168.31.231) [Debug] 0 [PackageName…...

Linux常用命令----shutdown命令

文章目录 命令概述参数解释使用示例及解释 命令概述 shutdown 命令用于安全地关闭或重启 Linux 系统。它允许管理员指定一个时间点执行操作&#xff0c;并可发送警告信息给所有登录的用户。 参数解释 时间参数 ([时间]): now: 立即执行关闭或重启操作。m: 在 m 分钟后执行操作…...

美创科技受邀亮相第二届全球数字贸易博览会

11月23日-27日&#xff0c;由浙江省人民政府、商务部共同主办的第二届全球数字贸易博览会&#xff08;以下简称“数贸会”&#xff09;圆满落幕。围绕“国家级、国际性、数贸味”的目标定位&#xff0c;以“数字贸易 商通全球”为主题&#xff0c;数贸会重点展示数字贸易全产业…...

有n件物品,每件物品都有一个花费,要求每m个中必须至少选2个,求最小花费

题目 #include<bits/stdc.h> using namespace std; #define int long long #pragma GCC optimize(2) const int maxn 2e4 5, maxm 2e3 5, inf 1e9; int a[maxn]; int f[maxm][maxm];//f[i][j]表示选了第i个&#xff0c;上一个选的是第i-j个&#xff08;每m个中选2个…...

Hive数据库与表操作

文章目录 一、准备工作二、Hive数据库操作&#xff08;一&#xff09;Hive数据存储&#xff08;二&#xff09;创建数据库&#xff08;三&#xff09;查看数据库&#xff08;四&#xff09;修改数据库信息 一、准备工作 二、Hive数据库操作 &#xff08;一&#xff09;Hive数据…...

C语言数据结构之顺序表(上)

前言&#xff1a; ⭐️此篇博文主要分享博主在学习C语言的数据结构之顺序表的知识点时写的笔记&#xff0c;若有错误&#xff0c;还请佬指出&#xff0c;一定感谢&#xff01;制作不易&#xff0c;若觉得内容不错可以点赞&#x1f44d;收藏❤️&#xff0c;这是对博主最大的认可…...

详解原生Spring中的控制反转和依赖注入-构造注入和Set注入

&#x1f609;&#x1f609; 学习交流群&#xff1a; ✅✅1&#xff1a;这是孙哥suns给大家的福利&#xff01; ✨✨2&#xff1a;我们免费分享Netty、Dubbo、k8s、Mybatis、Spring...应用和源码级别的视频资料 &#x1f96d;&#x1f96d;3&#xff1a;QQ群&#xff1a;583783…...

数组中的第 K 个最大元素(C++实现)

数组中的第 K 个最大元素 题目思路代码 题目 数组中的第 K 个最大元素 思路 通过使用优先队列&#xff08;最大堆&#xff09;来找到数组中第k大的元素。通过弹出最大堆中的前k-1个元素&#xff0c;留下堆中的顶部元素作为结果返回。 代码 class Solution { public:int find…...

C++ day42背包理论基础01 + 滚动数组

背包问题的重中之重是01背包 01背包 有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]&#xff0c;得到的价值是value[i] 。每件物品只能用一次&#xff0c;求解将哪些物品装入背包里物品价值总和最大。 每一件物品其实只有两个状态&#xff0c;取或者不…...

Appium+python自动化(十六)- ADB命令

简介 Android 调试桥(adb)是多种用途的工具&#xff0c;该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具&#xff0c;其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利&#xff0c;如安装和调试…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

服务器硬防的应用场景都有哪些?

服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式&#xff0c;避免服务器受到各种恶意攻击和网络威胁&#xff0c;那么&#xff0c;服务器硬防通常都会应用在哪些场景当中呢&#xff1f; 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...

CMake控制VS2022项目文件分组

我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南

精益数据分析&#xff08;97/126&#xff09;&#xff1a;邮件营销与用户参与度的关键指标优化指南 在数字化营销时代&#xff0c;邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天&#xff0c;我们将深入解析邮件打开率、网站可用性、页面参与时…...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)

Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败&#xff0c;具体原因是客户端发送了密码认证请求&#xff0c;但Redis服务器未设置密码 1.为Redis设置密码&#xff08;匹配客户端配置&#xff09; 步骤&#xff1a; 1&#xff09;.修…...