查看: 2949|回复: 12
收起左侧

Microsoft(4) 求正数数组内和为指定数字的合并总数

|只看干货
头像被屏蔽
wwwyhx | 显示全部楼层 |阅读模式
提示: 作者被禁止或删除 内容自动屏蔽

上一篇:感叹:提高算法真不是一天两天的事
下一篇:Microsoft(5) : 字符串最大回文子串
Imbalism 2011-4-22 16:23:24 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (42)
 
 
0% (0)    👎
请问10是什么意思?
回复

使用道具 举报

头像被屏蔽
 楼主| wwwyhx 2011-4-22 16:52:07 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

头像被屏蔽
 楼主| wwwyhx 2011-4-23 12:04:13 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

ljfljf2006 2011-4-23 14:24:54 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (36)
 
 
0% (0)    👎
本帖最后由 ljfljf2006 于 2011-4-23 14:25 编辑

简单DP,我说下大概思路。

假设有数组num[N],需要凑出和M。DP[x][y]表示用数组前x个数组凑合和y的可能方法数。

除了DP[0][0]=1,初始化DP[][]=0。
则有DP[N][M]=DP[N-1][M]+DP[N-1][M-num[N-1]]。其中注意判断M-num[N-1]的正负。

时间复杂度O(M*N)。

评分

参与人数 1大米 +56 收起 理由
wwwyhx + 56

查看全部评分

回复

使用道具 举报

头像被屏蔽
 楼主| wwwyhx 2011-4-23 14:39:38 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

头像被屏蔽
 楼主| wwwyhx 2011-4-24 12:43:08 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

Imbalism 2011-4-24 13:14:49 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (42)
 
 
0% (0)    👎
本帖最后由 Imbalism 于 2011-4-24 13:17 编辑

用map优化了一下, 把中间永远为0的数省去了,同时也利用了map内部已经排好序的性质
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <map>
  5. using namespace std;


  6. int main(int argc, char *argv[])
  7. {
  8.      vector<int> v = {5, 5, 10, 2, 3};
  9.      sort(v.begin(), v.end());
  10.      map<int, int> m;
  11.      for(int i = 0; i < v.size(); ++i)
  12.      {
  13.           map<int, int>::reverse_iterator iter;
  14.           for(iter = m.rbegin(); iter != m.rend(); ++iter)
  15.           {
  16.                if(iter->first + v > 15)
  17.                     continue;
  18.                if(m.count(iter->first + v) == 0)
  19.                {
  20.                     m[iter->first + v] = 0;
  21.                     ++iter;
  22.                }
  23.                m[iter->first + v] += iter->second;
  24.           }
  25.           if(m.find(v) == m.end())
  26.                m[v] = 0;
  27.           m[v]++;
  28.      }
  29.      map<int, int>::iterator iter;     
  30.      for (iter = m.begin() ; iter != m.end(); ++iter)
  31.      {
  32.           cout << iter->first <<' '<<iter->second << endl;
  33.      }
  34.      return 0;
  35. }
复制代码
回复

使用道具 举报

头像被屏蔽
 楼主| wwwyhx 2011-4-24 13:22:00 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

benny 2011-4-25 10:41:16 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   91% (21)
 
 
8% (2)    👎
有个想法,不知道对不对

迭代的做。。

F(index, sum)返回的是位置为index时,从index往后的数字(包括index)组成sum的可能的个数

如果sum小于等于0就返回0
如果sum等于本身就返回1+F(index+1, sum)
如果是最后一个元素且Sum不等于自己,返回0

Initial:
F(0,15)=F(1,15)+F(1,15-Num[0])


我在想一个问题
如果这道题认为 (5,10), (5,10)是一样的组合怎么办?

评分

参与人数 1大米 +23 收起 理由
wwwyhx + 23

查看全部评分

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表