【算法与数据结构】40、LeetCode组合总和 II
文章目录
- 一、题目
- 二、解法
- 三、完整代码
所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。
一、题目

二、解法
思路分析:【算法与数据结构】39、LeetCode组合总和的基础之上,这道题变成了candidates中有重复元素,而且每个元素只能使用一次。如果直接使用39题的代码会出现重复的组合,需要去重,但这样一来leetcode可能运行超时。因此我们需要再找组合的时候就进行去重的操作。引入一个used布尔数组,标记candidates中的元素是否使用过。在这之前首先需要对candidates数组进行排序。
例如, target=7, candidates = [1 1 2 4 5 7], 第一种情况:candidates[0] +candidates[2] + candidates[3] = candidates[1] +candidates[2] + candidates[3]= 1 + 2 + 4, 因此出现重复的组合。第二种情况:candidates[0] +candidates[1] + candidates[4]= 1 + 1 + 5是无重复的组合。因此用used标记使用过的数,当candidates[i] == candidates[i - 1]时,出现重复元素。进行第i次循环时,第一种情况used[i-1]=false就是出现重复组合, 在第i-1次循环时已经考虑过了,直接continue。第二种情况就是重复数字都利用到了used[i-1]=true,这种需要考虑。
程序如下:
class Solution {
private:vector<vector<int>> result; // 结果合集vector<int> path;void backtracking(const vector<int>& candidates, const int target, int sum, int startIndex, vector<bool>& used) {if (sum > target) return; // 剪枝if (sum == target) {result.push_back(path);return;}for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) { // 剪枝优化if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) { // 去重continue; }sum += candidates[i];used[i] = true;path.push_back(candidates[i]); // 处理节点backtracking(candidates, target, sum, i+1, used); // 递归used[i] = false;sum -= candidates[i];path.pop_back(); // 回溯,撤销处理的节点}}
public:vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {vector<bool>used(candidates.size(), 0);sort(candidates.begin(), candidates.end());backtracking(candidates, target, 0, 0, used);return result;}
};
复杂度分析:
- 时间复杂度: O ( n ∗ 2 n ) O(n*2^n) O(n∗2n)。
- 空间复杂度: O ( n ) O(n) O(n)。
三、完整代码
# include <iostream>
# include <vector>
# include <string>
# include <algorithm>
using namespace std;class Solution {
private:vector<vector<int>> result; // 结果合集vector<int> path;void backtracking(const vector<int>& candidates, const int target, int sum, int startIndex, vector<bool>& used) {if (sum > target) return; // 剪枝if (sum == target) {result.push_back(path);return;}for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) { // 剪枝优化if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) { // 去重continue; }sum += candidates[i];used[i] = true;path.push_back(candidates[i]); // 处理节点backtracking(candidates, target, sum, i+1, used); // 递归used[i] = false;sum -= candidates[i];path.pop_back(); // 回溯,撤销处理的节点}}
public:vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {vector<bool>used(candidates.size(), 0);sort(candidates.begin(), candidates.end());backtracking(candidates, target, 0, 0, used);return result;}
};int main() {vector<int> candidates = { 10,1,2,7,6,1,5 };int target = 8;Solution s1;vector<vector<int>> result = s1.combinationSum2(candidates, target);for (vector<vector<int>>::iterator it = result.begin(); it != result.end(); it++) {for (vector<int>::iterator jt = (*it).begin(); jt != (*it).end(); jt++) {cout << *jt << " ";}cout << endl;}system("pause");return 0;
}
end
相关文章:
【算法与数据结构】40、LeetCode组合总和 II
文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析:【算法与数据结构】39、LeetCode组合总和的基础之上,这道题变成了candidates中有重复元素&…...
Flink SQL -- 命令行的使用
1、启动Flink SQL 首先启动Flink的集群,选择独立集群模式或者是session的模式。此处选择是时session的模式:yarn-session.sh -d 在启动Flink SQL的client: sql-client.sh 2、kafka SQL 连接器 在使用kafka作为数据源的时候需要上传jar包到…...
asp.net core把所有接口和实现类批量注入到容器
要将所有接口和实现类批量注入到容器,可以使用反射和循环来实现自动批量注册。下面是一种示例方法: 创建一个扩展方法,用于批量注册接口和实现类。 public static class ServiceCollectionExtensions {public static IServiceCollection Re…...
SPSS曲线回归
前言: 本专栏参考教材为《SPSS22.0从入门到精通》,由于软件版本原因,部分内容有所改变,为适应软件版本的变化,特此创作此专栏便于大家学习。本专栏使用软件为:SPSS25.0 本专栏所有的数据文件请点击此链接下…...
软件之禅(七)面向对象(Object Oriented)
黄国强 2023/11/11 前文提到面向对象构建的模块控制器,根据第一性原理,从图灵机的角度,面向对象不是最基本的元素。那么面向对象是不是不重要呢? 答案是否定的,面向对象非常非常重要。当我们面对一个具体的领域…...
汽车之家车型_车系_配置参数数据抓取
// 导入所需的库 #include <iostream> #include <fstream> #include <string> #include <curl/curl.h> #include <regex>// 声明全局变量 std::string htmlContent; std::regex carModelRegex("\\d{4}-\\d{2}-\\d{2}"); std::regex ca…...
RabbitMQ的 五种工作模型
RabbitMQ 其实一共有六种工作模式: 简单模式(Simple)、工作队列模式(Work Queue)、 发布订阅模式(Publish/Subscribe)、路由模式(Routing)、通配符模式(Topi…...
原型制作神器ProtoPie的使用Unity与网页跨端交互
什么是ProtoPie? ProtoPie是一款面向设计师的软件原型设计工具,例如制作App界面交互展示,制作好的原型可以一键发布到Web服务器,就可以浏览器访问。由于其内置了大量常用交互类型,以及"程序化"模块…...
另辟奚径-Android Studio调用Delphi窗体
大家都知道Delphi能调用安卓SDK,比如jar、aar等, 但是反过来,能在Android Studio中调用Delphi开发的窗体吗? 想想不太可能吧, Delphi用的是Pascal,Android Studio用的是Java,这两个怎么能混用…...
SOLID 原则,程序设计五大原则,设计模式
SOLID 是让软件设计更易于理解、更加灵活和更易于维护的五个原则的简称。 单一职责(Single Responsibility Principle):修改一个类的原因只能有一个。开闭原则(Open/Closed Principle):对于扩展,类应该是“开放”的;对于修改&…...
Java基础——数组(一维数组与二维数组)
文章目录 一维数组声明初始化与赋值内存图解 二维数组声明初始化与赋值内存图解 数组练习 数组是多个相同类型的数据按一定顺序排列的集合。 说明: 数组是引用数据类型,数组的元素是同一类型的任何数据类型,包括基本数据类型和引用数据类型…...
Python爬虫抓取微博数据及热度预测
首先我们需要安装 requests 和 BeautifulSoup 库,可以使用以下命令进行安装: pip install requests pip install beautifulsoup4然后,我们需要导入 requests 和 BeautifulSoup 库: import requests from bs4 import BeautifulSou…...
Qt QTableWidget表格的宽度
默认值 QTableWIdget的表格宽度默认是一个给定值,可以手动调整每列的宽度,也不填满父窗口 MainWindow::MainWindow(QWidget *parent): QMainWindow(parent) {this->resize(800,600);QStringList contents{"11","111111111111",&…...
OpenCV(opencv_apps)在ROS中的视频图像的应用(重点讲解哈里斯角点的检测)
1、引言 通过opencv_apps,你可以在ROS中以最简单的方式运行OpenCV提供的许多功能,也就是说,运行一个与功能相对应的launch启动文件,就可以跳过为OpenCV的许多功能编写OpenCV应用程序代码,非常的方便。 对于想熟悉每个…...
常见排序算法之插入排序类
插入排序,是一种简单直观的排序算法,工作原理是将一个记录插入到已经排好序的有序表中,从而形成一个新的、记录数增1的有序表。在实现过程中,它使用双层循环,外层循环对除了第一个元素之外的所有元素,内层循…...
Dubbo服务消费端远程调用过程剖析
1 Dubbo服务消费端远程调用过程概述 (1)当消费方调用远程服务的方法时,会被InvokerInvocationHandler拦截,执行其invoke()方法,创建RpcInvocation对象; (2)接着会选择远程调用的负…...
华硕荣获“EPEAT Climate+ Champion”永续先驱称号
华硕持续深耕永续理念,努力提供低碳排放、高效能产品,并被全球电子委员会授予“EPEAT Climate Champion”称号。这一荣誉再次表明了华硕在永续管理方面的承诺,并凸显了华硕在追求永续发展上的决心。 华硕通过设立“科学基础减碳目标”、“再生…...
基于QT使用OpenGL,加载obj模型,进行鼠标交互
目录 功能分析(需求分析)技术点分析OpenGL立即渲染模式可编程渲染管线模式 QOpenGLWidget派生类 glwidget逻辑glwidget.hglwidget.cpp 鼠标交互功能obj格式介绍 效果bunnyCayman_GT 功能分析(需求分析) 基于QT平台,使…...
三大赛题指南发布!2023 冬季波卡黑客松本周末开启 Workshop
2023 年一众黑客松赛事中,为什么我们建议您选择波卡黑客松大赛?或许答案在于——作为开发者极度友好的技术生态,波卡能够从参赛者的立场出发,为大家提供从 0 到 1 实现项目孵化成长的机会。这里聚集了一线技术专家的资源力量&…...
数据结构与算法(Java版) | 算法的空间复杂度简介
关于算法的空间复杂度,下面我给大家作一个简单介绍。 类似于时间复杂度的讨论,一个算法的空间复杂度(Space Complexity)定义为该算法所耗费的存储空间,同样,它也是问题规模n的一个函数。 其实,…...
基于大模型的 UI 自动化系统
基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...
【机器视觉】单目测距——运动结构恢复
ps:图是随便找的,为了凑个封面 前言 在前面对光流法进行进一步改进,希望将2D光流推广至3D场景流时,发现2D转3D过程中存在尺度歧义问题,需要补全摄像头拍摄图像中缺失的深度信息,否则解空间不收敛…...
Ascend NPU上适配Step-Audio模型
1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统,支持多语言对话(如 中文,英文,日语),语音情感(如 开心,悲伤)&#x…...
C++ 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)
升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点,但无自动故障转移能力,Master宕机后需人工切换,期间消息可能无法读取。Slave仅存储数据,无法主动升级为Master响应请求ÿ…...
Typeerror: cannot read properties of undefined (reading ‘XXX‘)
最近需要在离线机器上运行软件,所以得把软件用docker打包起来,大部分功能都没问题,出了一个奇怪的事情。同样的代码,在本机上用vscode可以运行起来,但是打包之后在docker里出现了问题。使用的是dialog组件,…...
LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf
FTP 客服管理系统 实现kefu123登录,不允许匿名访问,kefu只能访问/data/kefu目录,不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...
【C++特殊工具与技术】优化内存分配(一):C++中的内存分配
目录 一、C 内存的基本概念 1.1 内存的物理与逻辑结构 1.2 C 程序的内存区域划分 二、栈内存分配 2.1 栈内存的特点 2.2 栈内存分配示例 三、堆内存分配 3.1 new和delete操作符 4.2 内存泄漏与悬空指针问题 4.3 new和delete的重载 四、智能指针…...
群晖NAS如何在虚拟机创建飞牛NAS
套件中心下载安装Virtual Machine Manager 创建虚拟机 配置虚拟机 飞牛官网下载 https://iso.liveupdate.fnnas.com/x86_64/trim/fnos-0.9.2-863.iso 群晖NAS如何在虚拟机创建飞牛NAS - 个人信息分享...
django blank 与 null的区别
1.blank blank控制表单验证时是否允许字段为空 2.null null控制数据库层面是否为空 但是,要注意以下几点: Django的表单验证与null无关:null参数控制的是数据库层面字段是否可以为NULL,而blank参数控制的是Django表单验证时字…...
