一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 336|回复: 5
收起左侧

[算法题] 给一个只有(正负)2的幂的数列找到一个子序列的和为t

[复制链接] |试试Instant~ |关注本帖
mgccl 发表于 2015-11-29 21:18:12 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
遇到有趣的题分享一下, 大家以后也能拿去做面试题用.

Warmup:
Input: power of 2: 比如 8,2,4,4,4
以及一个target number t.
是否存在一个subsequence, 加起来等于t.

followup 1:
如果input可以有负的power of 2呢? 比如 8,-2,-4,-4,4
(hint: 有个很巧妙的解)

followup 2:
假如给你k个target number t_1,...,t_k. 然后你要找到k个disjoint subsequence, 使得它们的和各为t_1,...,t_k呢?
stellari 发表于 2015-11-29 21:51:17 | 显示全部楼层
感谢分享。subsequence指的是“(连续的)subarray”还是“(可以不连续的)subsequence”?比如[8, 4]算不算第一个input例子的subsequence呢?抱歉我必须确认这一点,因为好像大家总是把这两个词混着用。
回复 支持 反对

使用道具 举报

 楼主| mgccl 发表于 2015-11-29 21:54:59 | 显示全部楼层
stellari 发表于 2015-11-29 21:51
感谢分享。subsequence指的是“(连续的)subarray”还是“(可以不连续的)subsequence”?比如[8, 4]算不 ...

可以不连续的.
回复 支持 反对

使用道具 举报

sdudxf 发表于 2015-11-29 22:31:30 | 显示全部楼层
楼主说一说大体思路呗
回复 支持 反对

使用道具 举报

stellari 发表于 2015-11-30 00:27:20 | 显示全部楼层
warmup倒是好说,我想只要先将input中每个元素的个数数出来(因为每个数都是2^k次方,所以这个统计表可以用一个数组来记录),然后用greedy的方式,从t中不断减去“统计表中最大的小于t”的数字m即可,每减一次同时也将m从统计表中除去。如果最后t能减到0,则说明存在一个subsequence,否则不存在。建立统计表需要O(N)时间(N是数组长度),循环相减最多进行N次,所以总时间复杂度就是O(N)。

至于followup 1“很巧妙的解法”,容在下再想想。
回复 支持 反对

使用道具 举报

 楼主| mgccl 发表于 2015-12-1 04:26:09 | 显示全部楼层
“很巧妙的解法” 在这里. http://mathb.in/47550
巧妙解法没法用在 followup 2上就是了...
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-7 06:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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