文档章节

力扣算法题—039组合求和

o
 osc_y8yehimr
发布于 2019/03/20 17:35
字数 656
阅读 0
收藏 0

精选30+云产品,助力企业轻松上云!>>>

  1 #include "000库函数.h"
  2 
  3 //第一感觉使用回溯比较快
  4 //好激动,第一次使用回溯成功 96ms,37.1M
  5 
  6 
  7 class Solution {
  8 public:
  9     vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
 10         vector<vector<int>>Res;
 11         if (candidates.size() == 0)return Res;            
 12         vector<int>v;//临时存放解            
 13         Combin(candidates, Res,v, target, 0, 0);        
 14         return Res;
 15     }
 16 
 17     void Combin(vector<int>candidates, vector<vector<int>>&Res, vector<int>&v, int target, int start, int sum) {
 18         if (sum == target) {
 19             Res.push_back(v);
 20             return;
 21         }
 22         else if (sum > target)
 23             return;
 24         for (int i = start; i < candidates.size(); ++i) {
 25             v.push_back(candidates[i]);
 26             Combin(candidates, Res, v, target, i, sum + candidates[i]);
 27             v.pop_back();//将数字退出
 28         }
 29     }
 30 
 31 };
 32 
 33 
 34 //博客答案
 35 //解法一
 36 class Solution {
 37 public:
 38     vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
 39         vector<vector<int>> res;
 40         sort(candidates.begin(), candidates.end());
 41         for (int i = 0; i < candidates.size(); ++i) {
 42             if (candidates[i] > target) break;
 43             if (candidates[i] == target) { res.push_back({ candidates[i] }); break; }
 44             vector<int> vec = vector<int>(candidates.begin() + i, candidates.end());
 45             vector<vector<int>> tmp = combinationSum(vec, target - candidates[i]);
 46             for (auto a : tmp) {
 47                 a.insert(a.begin(), candidates[i]);
 48                 res.push_back(a);
 49             }
 50         }
 51         return res;
 52     }
 53 };
 54 
 55 //解法二
 56 //建立一个三维数组dp,这里dp[i]表示目标数为i的所有解法集合。
 57 //这里的i就从1遍历到target即可,对于每个i,我们都新建一个二维数组cur,
 58 //然后遍历candidates数组,如果遍历到的数字大于i,说明当前及之后的数字都无法组成i,
 59 //直接break掉。否则如果相等,那么把当前数字自己组成一个数组,并且加到cur中。
 60 //否则就遍历dp[i - candidates[j] - 1] 中的所有数组,如果当前数字大于数组的首元素,
 61 //则跳过,因为我们的结果要求是要有序的。否则就将当前数字加入数组的开头,
 62 //并且将数组放入cur之中即可,参见代码如下:
 63 
 64 class Solution {
 65 public:
 66     vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
 67         vector<vector<vector<int>>> dp;
 68         sort(candidates.begin(), candidates.end());
 69         for (int i = 1; i <= target; ++i) {
 70             vector<vector<int>> cur;
 71             for (int j = 0; j < candidates.size(); ++j) {
 72                 if (candidates[j] > i) break;
 73                 if (candidates[j] == i) { cur.push_back({ candidates[j] }); break; }
 74                 for (auto a : dp[i - candidates[j] - 1]) {
 75                     if (candidates[j] > a[0]) continue;
 76                     a.insert(a.begin(), candidates[j]);
 77                     cur.push_back(a);
 78                 }
 79             }
 80             dp.push_back(cur);
 81         }
 82         return dp[target - 1];
 83     }
 84 };
 85 
 86 void T039() {
 87     vector<int> v;    
 88     vector<vector<int>>Res;
 89     Solution s;
 90     v = { 2, 3, 6, 7 };
 91     Res = s.combinationSum(v, 7);
 92     for (auto &a : Res) {
 93         for (auto b : a)
 94             cout << b << "  ";
 95         cout << endl;
 96     }
 97     cout << endl<<"*********"<< endl;
 98     v = { 2, 3,5 };
 99     Res = s.combinationSum(v, 8);
100     for (auto &a : Res) {
101         for (auto b : a)
102             cout << b << "  ";
103         cout << endl;
104     }
105     cout << endl << "*********" << endl;
106 
107 
108 
109 }

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
Google 资深工程师苏勇:算法面试6大数据结构必考知识点!

在互联网行业的算法面试中经常会被考到数据结构的知识,它与算法相辅相成,没有扎实的数据结构基础,学好算法几乎不太可能。 这里精心整理了 Google 资深工程师的学习笔记和解题技巧,总结出...

北城码农Alex
2019/06/27
146
0
算法刷题笔记-stack-四则运算

题目描述: 给定一个含有数字和运算符的字符串,为表达式添加括号,改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。 示例 1: 输入:...

野生学霸
2019/06/23
0
0
算法刷题笔记-stack-四则运算

题目描述: 给定一个含有数字和运算符的字符串,为表达式添加括号,改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。 示例 1: 输入:...

osc_nnbkiac5
04/16
2
0
「算法」加一 & 二进制求和

00066 加一 题目描述 给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。 最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。 你可以假设除了整数 0 之外,这个...

小猿刷题
01/11
16
0
Java面试越来越难怎么办?80% 应聘者不知道的面试加分项

     “你懂算法吗?服务器这块咋样?项目经验有吗?软件开发这块呢?懂分布式吗……”   假如恰好你涉猎广泛,以上都懂。但也极有可能会在手写红黑树上掉坑。      [事件援引:H...

java进阶架构师
2019/09/28
0
0

没有更多内容

加载失败,请刷新页面

加载更多

科技人文丨玻璃心:承受阈值与表达

大家好,我是SKODE。 有趣的灵魂,聊科技人文。 本系列博客地址:传送门 本文转载自B站:安慰记传送门 玻璃心是网络用语,意思是: 对负面事件的接受度很低 还有对别人可能给出的负面评价非常...

osc_u9mt0sus
54分钟前
20
0
迅睿CMS 游客不允许上传附件

游客不允许上传附件 迅睿CMS系统:https://www.xunruicms.com/ 本文档原文地址:https://www.xunruicms.com/doc/752.html...

迅睿CMS-PHP开源CMS程序
54分钟前
12
0
代理,注解,接口和实现类的小测验

* retention : 保留* policy : 策略 ps : 简单测试了一下手写代理,jdk动态代理,和cglib动态代理,根据其不同的结果分析其原理 一:测试目的 主要想看一下不同的代理模式对于目标类中方法上注...

岁一
55分钟前
12
0
V-Ray 5 For 3ds Max 正式发布:超越渲染 - 知乎

15个新功能,V-Ray5助你时间更节省,渲染更出色! 作者:ChaosGroup VRay 5 For 3ds Max 已正式发布! 2分钟视频,抢先预览新功能↓ 知乎视频 www.zhihu.com V-Ray 5 for 3ds Max 新增功能 ...

osc_o9u1um45
55分钟前
0
0
毕业的笑容和悲伤永远是校园的回忆

校园的风轻轻的拂过我的脸庞,风儿显得更加凉爽, 开满火红的凤凰树,染遍了校园的每个角落, 晚上那枝头蝉儿的竞相鸣奏,唱满了令人不舍的毕业歌, 它们彷彿告诉了我们要毕业了。 毕业典礼那...

瑾123
55分钟前
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部