leetcode77.组合

news/2024/7/20 21:56:35 标签: 深度优先, 回溯, 递归

编写CPP代码感悟:
能用vector就别用普通数组,如果是用vector的话,debug的时候clion的调试界面会更加友好,如果是数组的话,好像没有便捷查看数组元素的方式,比较F*&&*k,而且写vector引用比编写数组引用便捷!
回溯算法感悟
伪代码如下

class Solution {
public:
    vector<vector<int>> paths;
    vector<int> path;

    vector<vector<int>> combine(int n, int k) {
        vector<bool> visit(k+1);
        dfs(params....);
        return paths;
    }
    void dfs(vector<bool>& visit,int idx,int n,int k){
        if(path.size()==k){
            paths.push_back(path);
            return;
        }
        for(int i=idx;i<=n;++i){
            if(!visit[i]){
                visit[i]=1;//组合问题标记
                path.push_back(i);//添加元素
                dfs(visit,i+1,n,k);//一定要记得i+1不要瞎搞成i,一定要往下一层深度遍历
                path.pop_back();//删除尾部
                visit[i]=0;//组合问题解除标记
            }
        }
    }
};

完整代码如下:

class Solution {
public:
    vector<vector<int>> paths;
    vector<int> path;

    vector<vector<int>> combine(int n, int k) {
        vector<bool> visit(k+1);
        dfs(visit,1,n,k);
        //delete[] visit;
        return paths;
    }
    void dfs(vector<bool>& visit,int idx,int n,int k){
        if(path.size()==k){
            paths.push_back(path);
            // path.clear();
            return;
        }
        for(int i=idx;i<=n;++i){
            if(!visit[i]){
                visit[i]=1;
                path.push_back(i);
                dfs(visit,i+1,n,k);
                path.pop_back();
                visit[i]=0;
            }
        }
    }
};

http://www.niftyadmin.cn/n/5452031.html

相关文章

【Entity Framework】Code First 数据批注

【Entity Framework】Code First 数据批注 文章目录 【Entity Framework】Code First 数据批注一、概述二、模型二、键Key三、组合键四、外键-ForeigKey第一种&#xff1a;指定导航属性&#xff0c;会自动生成外键&#xff0c;命名规则为&#xff1a;“对象名称_主键名“第二种…

JAVA后端开发面试题库

一、计算机基础&编程语言 1.1 操作系统 ● 1. 进程的有哪几种状态&#xff0c;状态转换图&#xff0c;及导致转换的事件。 ● 2. 进程与线程的区别。 ● 3. 进程通信的几种方式。 ● 4. 线程同步几种方式。(一定要会写生产者、消费者问题&#xff0c;完全消化理解) ● 5.…

【数据结构与算法】java有向带权图最短路径算法-Dijkstra算法(通俗易懂)

目录 一、什么是Dijkstra算法二、算法基本步骤三、java代码四、拓展&#xff08;无向图的Dijkstra算法&#xff09; 一、什么是Dijkstra算法 Dijkstra算法的核心思想是通过逐步逼近的方式&#xff0c;找出从起点到图中其他所有节点的最短路径。算法的基本步骤如下&#xff1a;…

中国人民大学加拿大女王大学金融硕士——金融行业学历真的很重要

在当今这个竞争激烈的社会&#xff0c;拥有一份高学历已经成为了许多人追求的目标。尤其是在金融行业&#xff0c;学历的重要性更是不言而喻。那么&#xff0c;如何在短时间内提升自己的学历和专业能力呢&#xff1f;中国人民大学与加拿大女王大学金融硕士项目或许是一个不错的…

java算法第31天 | 贪心算法 part01 ● 理论基础 ● 455.分发饼干 ● 376. 摆动序列 ● 53. 最大子序和

理论基础 贪心算法没有固定的套路&#xff0c;贪心的本质是选择每一阶段的局部最优&#xff0c;从而达到全局最优。 贪心算法一般分为如下四步&#xff1a; 将问题分解为若干个子问题 找出适合的贪心策略 求解每一个子问题的最优解 将局部最优解堆叠成全局最优解 这个四步其…

C程序编译、链接与项目构建

C程序编译、链接与项目构建 摘要C编译环境静、动态库介绍gcc与g和程序编译、链接Visual Studio创建和链接库动态库的显示调用Windows下显示动态库的加载/查找方式 Make介绍安装使用 CMake介绍安装使用构建方式内部构建外部构建构建使用静/动态库常用[系统]变量常用指令CMake模块…

向开发板上移植 can-utils 工具(为了测试CAN通信需要)

一. 简介 can0 网卡已经出现了&#xff0c;但是工作正不正常还不知道&#xff0c;必须要进行数据收发测试。这里我们使用 can-utils 这个工具来对 can0 网卡进行测试&#xff0c;因此&#xff0c;要先移植 can-utils 到我们的开发板根文件 统中。can-utils就是一个小的工…

封装的charts使用 vue2

//组件 <template><div ref"chartRef" class"echart"></div> </template><script> import * as echarts from echartsexport default {data() {return {chart: null}},methods: {init() {if (!this.chart) {this.chart ech…