leetcode-77-组合

题目描述:

给定两个整数 n 和 k,返回 1 ... 中所有可能的 k 个数的组合。

示例:

输入: n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

要完成的函数:

vector<vector<int>> combine(int n, int k) 

说明:

1、这道题给定两个int型整数n和k,要求在[1,n]的闭区间中找到k个整数的组合(组合也就是不重复的)。

比如n=4,k=2,那么所有的组合是 [1,2] [1,3] [1 4] [2,3] [2,4] [3,4]。

把每一个组合放在一个一维vector中,所有的组合存储在二维的vector中,最后返回这个二维的vector。

2、这道题目也是一道递归的题目,我们依然用熟悉的方法来做。

代码如下(附详解):

    vector<vector<int>>res;//全局变量,最终要返回的二维vector
    vector<int>res1;//全局变量,存储每一个可能的组合
    void digui(int n,int k,int index)
    {
        if(k==0)//退出条件,当前没有数要加入了
        {
            res.push_back(res1);
            return;
        }
        for(int i=index;i<=n-k+1;i++)//不断地循环,注意i的范围,比如n=4,k=2的时候,i最大也只能取3,不能取4
        {
            res1.push_back(i);
            digui(n,k-1,i+1);//k减1,少了一个要添加的数,i加1,从下一个坐标开始
            res1.pop_back();
        }
    }
    vector<vector<int>> combine(int n, int k) 
    {
        digui(n,k,1);//直接进入递归函数,k表示当前还有几个数要加入,1表示当前要从1开始
        return res;//返回最终的二维vector
    }

上述代码实测56ms,beats 99.55% of cpp submissions。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏人工智能LeadAI

Tensorflow教程: tf.Variable() 和tf.get_variable()

1、使用tf.Variable时,如果检测到命名冲突,系统会自己处理。使用tf.get_variable()时,系统不会处理冲突,而会报错

14230
来自专栏数据结构与算法

洛谷P3391 【模板】文艺平衡树(Splay)(FHQ Treap)

题目背景 这是一道经典的Splay模板题——文艺平衡树。 题目描述 您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:翻转一个区...

32950
来自专栏程序生活

Tensorflow教程(十三) tf.Variable() 和tf.get_variable()1 简介2 区别3 实例

23530
来自专栏前端黑板报

一个数字截取引发的精度问题(四)

这篇是精度问题的最后一篇,要是想看前面的,请看微信历史记录。 做前端的都感觉JS这语言巨坑无比,兼容性让你摸不到头脑,甚至还会让你脱发。一些初学者遇到: 0.1...

257100
来自专栏决胜机器学习

PHP数据结构(五) ——数组的压缩与转置

PHP数据结构(五)——数组的压缩与转置 (原创内容,转载请注明来源,谢谢) 1、数组可以看作是多个线性表组成的数据结构,二维数组可以有两种存储方式:一种是以行...

424110
来自专栏GopherCoder

xpath 和 pyquery

34530
来自专栏云端架构

【云端架构】教你口算MD5算法

对MD5算法简要的叙述可以为:MD5以512位分组来处理输入的信息,且每一分组又被划分为16个32位子分组,经过了一系列的处理后,算法的输出由四个32位分组组成...

603140
来自专栏抠抠空间

逻辑运算

一、逻辑运算符的种类及优先级 ▷逻辑运算符包括 not and or  ▷他们的优先级是 () > not > and > or 二、普通逻辑运算 ▷A and...

29090
来自专栏数据结构与算法

LOJ #108. 多项式乘法

内存限制:256 MiB时间限制:1000 ms标准输入输出 题目类型:传统评测方式:文本比较 上传者: 匿名 提交提交记录统计讨论测试数据 题目描述 这是一道...

37180
来自专栏chenjx85的技术专栏

leetcode-812-Largest Triangle Area

39290

扫码关注云+社区

领取腾讯云代金券