【Leetcode笔记】40.组合总和II

1. 题目要求

在这里插入图片描述
这道题目和39.组合总和不一样的地方在于:数组中含有相同的元素。同样地,结果不能含有重复组合。
拿第一个示例来看,

candidates = [1, 1, 2, 5, 6, 7, 10]

问题在于:第一个path=[1(index = 0), 2],绝不能出现另一个path=[1(index = 1), 2]!
如何去重?
卡哥使用了两种办法,第一种引入了used数组,在深度搜索中将上一个使用过的元素的used位置置一(即used[i]==true),这样当出现 candidates[i] == candidates[i - 1] 并且 used[i - 1] == false 就可以说明上面提到的第一个path已经完成;第二种办法是直接使用for循环的起始条件startIndex是否小于i,如果小于的话,就说明上一条路径的深度搜索完成了,我们此时在同一数层上的其他元素上重新开始搜索,此时可以跳过循环。

2. ACM模式代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& candidates, 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(); i++) {if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {continue;}sum += candidates[i];path.push_back(candidates[i]);used[i] = true;backtracking(candidates, target, sum, i + 1, used);sum -= candidates[i];path.pop_back();used[i] = false;}}
public:vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {result.clear();path.clear();vector<bool> used(candidates.size(), false);sort(candidates.begin(), candidates.end());backtracking(candidates, target, 0, 0, used);return result;}
};int main() {Solution solution;vector<int> candidates = {10,1,2,7,6,1,5};int target = 8;vector<vector<int>> result = solution.combinationSum2(candidates, target);for (auto& combination : result) {for (int num : combination) {cout << num << " ";}cout << endl;}return 0;
}
/* 不使用used数组进行去重,可以把for循环改成如下。 */
for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) 
{if (i > startIndex && candidates[i] == candidates[i - 1]) {continue;}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/338902.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

0、机器学习知识点

机器学习知识点 知识点汇总 知识点汇总 https://blog.csdn.net/seagal890/article/details/105352987 https://blog.csdn.net/fengdu78/article/details/115878843

[数据集][目标检测]脑溢血检测数据集VOC+YOLO格式767张2类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;767 标注数量(xml文件个数)&#xff1a;767 标注数量(txt文件个数)&#xff1a;767 标注类别…

unity2D跑酷游戏

项目成果 项目网盘 导入资源包 放入Assets文件Assets资源文件 游戏流程分析 摄像机size调小&#xff0c;让图片占满屏幕 人跑本质&#xff0c;相对运动&#xff0c;图片无限向右滚动 图片720&#xff0c;缩小100倍第二个图片x为7.2每unit px100两张图片刚好挨着连贯 空对象Bg…

友善RK3399v2平台利用rkmpp实现硬件编解码加速

测试VPU 编译mpp sudo apt update sudo apt install gcc g cmake make cd ~ git clone https://github.com/rockchip-linux/mpp.git cd mpp/build/linux/aarch64/ sed -i s/aarch64-linux-gnu-gcc/gcc/g ./arm.linux.cross.cmake sed -i s/aarch64-linux-gnu-g/g/g ./arm.lin…

Python 入门教程详细版全集(两周速成)

一、初始Python 打开CMD&#xff08;命令提示符&#xff09;程序&#xff0c;输入Python并回车。然后&#xff0c;在里面输入代码回车即可立即执行。 Tip1:找不到“命令提示符”程序在哪里&#xff1f; 使用快捷键&#xff1a;win r;打开运行框&#xff0c;输入cmd后回车即可…

942. 增减字符串匹配 - 力扣

1. 题目 由范围 [0,n] 内所有整数组成的 n 1 个整数的排列序列可以表示为长度为 n 的字符串 s &#xff0c;其中: 如果 perm[i] < perm[i 1] &#xff0c;那么 s[i] I 如果 perm[i] > perm[i 1] &#xff0c;那么 s[i] D 给定一个字符串 s &#xff0c;重构排列 pe…

【LeetCode算法】第111题:二叉树的最小深度

目录 一、题目描述 二、初次解答 三、官方解法 四、总结 一、题目描述 二、初次解答 1. 思路&#xff1a;二叉树的先序遍历。求出左子树的最小高度&#xff0c;求出右子树的最小高度&#xff0c;最终返回左子树和右子树的最小高度1。关键&#xff1a;若左子树的高度为0&…

springboot发送短信验证码,结合redis 实现限制,验证码有效期2分钟,有效期内禁止再次发送,一天内发送超3次限制

springboot结合redis发送短信验证码,实现限制发送操作 前言(可忽略)实现思路正题效果图示例手机号不符合规则校验图成功发送验证码示例图redis中缓存随机数字验证码&#xff0c;2分钟后失效删除redis缓存图验证码有效期内 返回禁止重复发送图验证码24小时内发送达到3次&#xf…

[深度学习]使用python部署yolov10的onnx模型

测试环境&#xff1a; onnxruntime1.15.1 opencv-python4.8.0.76 部分实现代码&#xff1a; parser argparse.ArgumentParser()parser.add_argument("--model", typestr, default"yolov10n.onnx", help"Input your ONNX model.")parser.add_arg…

ChatGPT AI专题资料合集【65GB】

介绍 ChatGPT & AI专题资料合集【65GB】 &#x1f381;【七七云享】资源仓库&#xff0c;海量资源&#xff0c;无偿分享√

网络监听技术

网络监听技术 网络监听概述网络监听环境 流量劫持网络环境共享式网络监听原理交换式网络监听交换机的工作方式交换网络监听&#xff1a;交换机集线器交换网络监听&#xff1a;端口镜像交换网络监听&#xff1a;MAC洪泛交换网络监听&#xff1a;MAC洪泛交换网络监听&#xff1a;…

7-15 位模式(dump_bits)---PTA实验C++

一、题目描述 为方便调试位运算相关程序&#xff0c;先做个展现位模式的小工具。 建议参照以下接口实现&#xff1a; // 利用函数重载特性&#xff1a;string dump_bits(char x);string dump_bits(short x);string dump_bits(int x);string dump_bits(long long x);// 或用函…

Windows10系统中安装与配置PyTorch(无GPU版本)

文章目录 1. 什么是PyTorch2. PyTorch的安装与配置&#xff08;无GPU&#xff09;2.1 创建环境2.2 安装pytorch库&#xff08;无GPU&#xff09;2.3 验证安装结果 1. 什么是PyTorch PyTorch 是一种用于构建深度学习模型且功能完备的开源框架&#xff0c;通常用于处理图像识别和…

安装zookeeper

一、搭建前准备 192.168.1.99 sdw1 192.168.1.98 sdw2 192.168.1.97 sdw3 二、搭建 1、各主机修改/etc/hosts&#xff0c;/etc/hostname文件 /etc/hosts 127.0.0.1 localhost localhost.localdomain localhost4 localhost4.localdomain4 ::1 localhos…

【人工智能】第二部分:ChatGPT的架构设计和训练过程

人不走空 &#x1f308;个人主页&#xff1a;人不走空 &#x1f496;系列专栏&#xff1a;算法专题 ⏰诗词歌赋&#xff1a;斯是陋室&#xff0c;惟吾德馨 目录 &#x1f308;个人主页&#xff1a;人不走空 &#x1f496;系列专栏&#xff1a;算法专题 ⏰诗词歌…

考研数学考到110+分,到底有多难?

很难&#xff01; 大家平时在网上上看到很多人说自己考了130&#xff0c;其实这些人只占参加考研数学人数的极少部分&#xff0c;有个数据可以展示出来考研数学到底有多难&#xff1a; 在几百万考研大军中&#xff0c;能考到120分以上的考生只有2%。绝大多数人的分数集中在30…

通过非欧几何体改变 AI 嵌入

目录 一、说明 二、LLM嵌入的形势 三、了解一些背景信息 3.1 什么是嵌入&#xff1f; 3.2 为什么嵌入在 NLP 中很重要&#xff1f; 3.3 复数Complex 几何的角色 3.4 C主动学习 3.5 角度嵌入 &#xff08;AE&#xff09;&#xff1a;解锁稳健排序 3.6 RotatE&#xff1a;将关系…

浏览器运行原理:网页被解析过程、script元素和页面解析的关系、defer和async使用;V8引擎执行原理(执行js)

一、浏览器渲染页面的流程 1.如何找到服务器 2.找到服务器如何下载对应的静态资源 输入完服务器地址&#xff0c;下载下来的一般是html文件&#xff0c;在解析html文件过程中&#xff0c;遇到link引用了css文件&#xff0c;就下载对应的css文件&#xff0c;js文件同理 3.一个…

IDEA 学习之 命令行太长问题

现象 Error running App Command line is too long. In order to reduce its length classpath file can be used. Would you like to enable classpath file mode for all run configurations of your project?解决办法 办法一 .idea\workspace.xml ——> <compone…

关于IDEA创建Maven一直爆红无法下载的问题

你能看到这我就知道你肯定已经试过了网上的很多方法了&#xff0c;我之前也是&#xff0c;试过了很多一直无法正常下载&#xff0c;我也是找人给 线下看了看解决了&#xff0c;我总结一下从头到尾排除问题&#xff0c;试到最后要是还解决不了你直接私信我&#xff0c;我给你看看…