【算法与数据结构】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的一个函数。 其实,…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...
线程与协程
1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指:像函数调用/返回一样轻量地完成任务切换。 举例说明: 当你在程序中写一个函数调用: funcA() 然后 funcA 执行完后返回&…...
spring:实例工厂方法获取bean
spring处理使用静态工厂方法获取bean实例,也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下: 定义实例工厂类(Java代码),定义实例工厂(xml),定义调用实例工厂ÿ…...
Android第十三次面试总结(四大 组件基础)
Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成,用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机: onCreate() 调用时机:Activity 首次创建时调用。…...
Go 语言并发编程基础:无缓冲与有缓冲通道
在上一章节中,我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道,它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好࿰…...
CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝
目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为:一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...
快刀集(1): 一刀斩断视频片头广告
一刀流:用一个简单脚本,秒杀视频片头广告,还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农,平时写代码之余看看电影、补补片,是再正常不过的事。 电影嘛,要沉浸,…...
基于Springboot+Vue的办公管理系统
角色: 管理员、员工 技术: 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能: 该办公管理系统是一个综合性的企业内部管理平台,旨在提升企业运营效率和员工管理水…...
Qemu arm操作系统开发环境
使用qemu虚拟arm硬件比较合适。 步骤如下: 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载,下载地址:https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...
