C++数据结构与算法——回溯算法组合问题

C++第二阶段——数据结构和算法,之前学过一点点数据结构,当时是基于Python来学习的,现在基于C++查漏补缺,尤其是树的部分。这一部分计划一个月,主要利用代码随想录来学习,刷题使用力扣网站,不定时更新,欢迎关注!

文章目录

  • 一、77. 组合
  • 二、216. 组合总和 III
  • 三、17. 电话号码的字母组合
  • 四、39. 组合总和
  • 五、40. 组合总和 II

一、77. 组合

在这里插入图片描述

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    vector<vector<int>> combine(int n, int k) {
        insertVector(n,k,1);
        return result;
    }
    void insertVector(int n,int k,int startIndex){
        if(path.size()==k){
            result.push_back(path);
            return;
        }
        for(int i=startIndex;i<=n;i++){
            path.push_back(i);
            insertVector(n,k,i+1);
            path.pop_back();
        }
    }
};

在这里插入图片描述

二、216. 组合总和 III

在这里插入图片描述

class Solution {
public:
    int targetSum;
    vector<int> path;
    vector<vector<int>> result;
    vector<vector<int>> combinationSum3(int k, int n) {
        insertVector(k,n,1);
        return result;
    }
    void insertVector(int k,int n,int startIndex){
        if(path.size()==k){
            if(targetSum==n){
                result.push_back(path);
                return;
            }
        }
        for(int i=startIndex;i<=9;i++){
            path.push_back(i);
            targetSum+=i;
            insertVector(k,n,i+1);
            path.pop_back();
            targetSum-=i;
        }
    }
};

在这里插入图片描述

三、17. 电话号码的字母组合

在这里插入图片描述

class Solution {
public:
    vector<string> result;
    string s="";
    string stringV[10] = {
        "",
        "",
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz"
    };
    vector<string> letterCombinations(string digits) {
        insertString(digits,0);
        return result;
    }
    void insertString(string digits,int index){
        if(index==digits.size()){
            // 收获结果
            if(s==""){
                return;
            }
            result.push_back(s);
            return ;
        }
        int digit = digits[index]-'0';
        string nextS = stringV[digit];
        // 遍历
        for(int i=0;i<nextS.size();i++){
            s+= nextS[i];
            insertString(digits,index+1);
            s.pop_back();
        }
    }
};

在这里插入图片描述

四、39. 组合总和

在这里插入图片描述

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    int Asum =0;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        insertV(candidates,target,0);
        return result;
    }
    void insertV(vector<int> candidates,int target,int startIndex){
        if(Asum==target){
            // 收获结果
            result.push_back(path);
            return;
        }
        else if(Asum>target){
            return;
        }
        for(int i=startIndex;i<candidates.size();i++){
            path.push_back(candidates[i]);
            Asum+=candidates[i];
            insertV(candidates,target,i);
            // 回溯
            path.pop_back();
            Asum-=candidates[i];
        }
    }
};

在这里插入图片描述

五、40. 组合总和 II

在这里插入图片描述

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    int Asum;
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        // 首先进行排序
        sort(candidates.begin(),candidates.end());
        vector<bool> used(candidates.size(),false); // 和candidates等长,并且全为0;
        insertS(candidates,target,0,used);
        return result;
    }
    void insertS(vector<int> candidates,int target,int startIndex,vector<bool> used){
        if(Asum==target){
            result.push_back(path);
            return;
        }
        if(Asum>target){
            return;
        }
        // 用一个used数组表示是否使用过
        for(int i=startIndex;i<candidates.size();i++){
            if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {
                continue;
            }
            path.push_back(candidates[i]);
            Asum+= candidates[i];
            used[i] = true;
            insertS(candidates,target,i+1,used);
            used[i] =false;
            path.pop_back();
            Asum-= candidates[i];
        }
    }
};

在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

SD-WAN如何解决更有性价比地跨境网络问题

云桥通SD-WAN利用智能路由和负载均衡技术&#xff0c;优化数据传输路径&#xff0c;提高网络性能和可靠性。这意味着数据在跨国传输时可以更快到达目的地&#xff0c;减少延迟和丢包率。跨境SD-WAN提高了网络连接速度和质量&#xff0c;使用户能够更快地访问跨国业务所需的资源…

索引的概念

索引的概念    1.索引是一种可选的与表相关的数据库对象&#xff0c;用于提高数据的查询效率。    2.索引是一种有序的数据结构。    3.如果一个表没有创建索引&#xff0c;则对该表进行查询时需要进行全表扫描&#xff1b;如果创建了索引&#xff0c;则在有条件查询时…

应用性能分析工具CPU Profiler

简介 本文档介绍应用性能分析工具CPU Profiler的使用方法&#xff0c;该工具为开发者提供性能采样分析手段&#xff0c;可在不插桩情况下获取调用栈上各层函数的执行时间&#xff0c;并展示在时间轴上。 开发者可通过该工具查看TS/JS代码及NAPI代码执行过程中的时序及耗时情况…

福州装修答疑 | 飘窗能不能砸掉?福州中宅装饰,福州装修

装修中的飘窗是一种常见的装饰元素&#xff0c;它不仅可以增加室内的采光和通风效果&#xff0c;还能为居室增添一份雅致和温馨。然而&#xff0c;很多业主在装修中都会遇到一个共同的问题&#xff1a;装修中的飘窗到底能不能砸&#xff1f;什么情况下可以砸&#xff1f;什么情…

IO流【带有缓冲区的字节输入、输出流;字符输入、输出流 转换流】

day35 学习注意事项 按照流的发展历史去学习注意流与流之间的继承关系举一反三 IO流 继day36 字节流继承图 字节流 应用场景&#xff1a;操作二进制数据&#xff08;音频、视频、图片&#xff09; abstract class InputStream – 字节输入流的基类&#xff08;抽象类&#xff0…

基于R、Python的Copula变量相关性分析及AI大模型应用

在工程、水文和金融等各学科的研究中&#xff0c;总是会遇到很多变量&#xff0c;研究这些相互纠缠的变量间的相关关系是各学科的研究的重点。虽然皮尔逊相关、秩相关等相关系数提供了变量间相关关系的粗略结果&#xff0c;但这些系数都存在着无法克服的困难。例如&#xff0c;…

Anaconda环境命令样例

启动命令行Anaconda Powershell Prompt 查看环境列表 (base) PS C:\Users\Administrator> conda env list # conda environments: # base * G:\ProgramData\anaconda3 MoneyprinterTurbo G:\ProgramData\anaconda3\envs\MoneyprinterTurbo pytorc…

C++ 标准库类型stackqueue

C/C总述&#xff1a;Study C/C-CSDN博客 栈与队列详解&#xff08;数据结构&#xff09;&#xff1a;栈与队列_禊月初三-CSDN博客 stack&#xff08;栈&#xff09; stack的常用函数 函数说明功能说明stack()构造空栈push(T& val)将元素val压入栈中size()返回栈中元素个…

数据结构之二叉树由浅入深最终章!

题外话 我说清明节想放松一下没更新大家信吗? 博客毕竟是文字不是视频,大家如果有不明白的地方,可以使用数形结合的方式,画图一边通过图片,一边通过对照代码进行推导一下,有什么问题都可以私信我或者写在评论区 正题 第一题 寻找二叉树中p,q最近公共祖先 第一题思路 先…

【C++】红黑树讲解及实现

前言&#xff1a; AVL树与红黑树相似&#xff0c;都是一种平衡二叉搜索树&#xff0c;但是AVL树的平衡要求太严格&#xff0c;如果要对AVL树做一些结构修改的操作性能会非常低下&#xff0c;比如&#xff1a;插入时要维护其绝对平衡&#xff0c;旋转的次数比较多&#xff0c;更…

【Claude 3】This organization has been disabled.此组织已被禁用。(Claude无法对话的原因和解决办法)

Claude对话提示 This organization has been disabled.此组织已被禁用。 This organization has been disabled.此组织已被禁用。 This organization has been disabled.此组织已被禁用。 问题截图 问题原因 出现该页面&#xff0c;表示您的账户已经无法使用&#xff0c;可能…

顺序表相关习题

&#x1f308; 个人主页&#xff1a;白子寰 &#x1f525; 分类专栏&#xff1a;python从入门到精通&#xff0c;魔法指针&#xff0c;进阶C&#xff0c;C语言&#xff0c;C语言题集&#xff0c;C语言实现游戏&#x1f448; 希望得到您的订阅和支持~ &#x1f4a1; 坚持创作博文…

Jenkins (三) - 拉取编译

Jenkins (三) - 拉取编译 通过Jenkins平台 git 拉取github上项目&#xff0c;通过maven编译并打包。 Jenkins 安装 git 插件 Manager Jenkins -> Plugins -> Available plugins -> Git 打包编译检验 FressStyle 风格编译 New Item输入 item name Spring-Cloud-1…

回溯法(一)——全排列 全组合 子集问题

全排列问题 数字序列 [ l , r ] [l,r] [l,r]​区间内元素的全排列问题 extern int ans[],l,r,num;//num&#xff1a;方案数 extern bool flag[]; void dfs(int cl){//cl:current left&#xff0c;即为当前递归轮的首元素if(cl r 1){//数组已越界&#xff0c;本轮递归结束for…

IDEA2023创建SpringMVC项目

✅作者简介&#xff1a;大家好&#xff0c;我是Leo&#xff0c;热爱Java后端开发者&#xff0c;一个想要与大家共同进步的男人&#x1f609;&#x1f609; &#x1f34e;个人主页&#xff1a;Leo的博客 &#x1f49e;当前专栏&#xff1a; 开发环境篇 ✨特色专栏&#xff1a; M…

SpringBoot整合Spring Data JPA

✅作者简介:大家好,我是Leo,热爱Java后端开发者,一个想要与大家共同进步的男人😉😉🍎个人主页:Leo的博客💞当前专栏: 循序渐进学SpringBoot ✨特色专栏: MySQL学习 🥭本文内容: SpringBoot整合Spring Data JPA 📚个人知识库: Leo知识库,欢迎大家访问 1.…

智慧牧场数据 7

1 体征数据采集 需求:获取奶牛记步信息 三轴加速度测量&#xff1a;加速度测量计反应的加速向量与当前的受力方向是相反&#xff0c;单位为g 陀螺仪&#xff0c;是用来测量角速度的&#xff0c;单位为度每秒&#xff08;deg/s&#xff09; 2000deg/s 相当于1秒钟多少转 1.1…

Vue关键知识点

watch侦听器 Vue.js 中的侦听器&#xff08;Watcher&#xff09;是 Vue提供的一种响应式系统的核心机制之一。 监听数据的变化&#xff0c;并在数据发生变化时执行相应的回调函数。 目的:数据变化能够自动更新到视图中 原理&#xff1a; Vue 的侦听器通过观察对象的属性&#…

正排索引 vs 倒排索引 - 搜索引擎具体原理

阅读导航 一、正排索引1. 概念2. 实例 二、倒排索引1. 概念2. 实例 三、正排 VS 倒排1. 正排索引优缺点2. 倒排索引优缺点3. 应用场景 三、搜索引擎原理1. 宏观原理2. 具体原理 一、正排索引 1. 概念 正排索引是一种索引机制&#xff0c;它将文档或数据记录按照某种特定的顺序…

分布式锁实战

4、分布式锁 4.1 、基本原理和实现方式对比 分布式锁&#xff1a;满足分布式系统或集群模式下多进程可见并且互斥的锁。 分布式锁的核心思想就是让大家都使用同一把锁&#xff0c;只要大家使用的是同一把锁&#xff0c;那么我们就能锁住线程&#xff0c;不让线程进行&#x…