一道面试算法求解

假设m=7时,7=1 2 4,用集合1,2,4中元素进行组合能够组合为1到6 6=2 4 5=1 4 4=4 3=1 2 2=2 1=1 用的都是1,2,4集合中的元素,求能满足这种条件集合的元素个数最小时的集合是什么,比如m=7时集合为1,2,4元素个数为3最小所以输出1,2,4#字节跳动#
全部评论
加号怎么没了
点赞 回复 分享
发布于 2018-05-20 00:04
我有个解法 记下当前集合中最大的数字和不包括最大数字的所有其他集合内数字之和 然后下一个数字就是最大数字加上其他数字之和+1 比如当前最大是max 集合内为[],  集合内元素不包括最大元素和sum=0 那么下一个数字就是0 + 0 + 1 = 1 这时更新max=1, [1], sum=0 下一个数字就是1 + 0 + 1 = 2 这时更新max=2, [1, 2], sum=1 下一个数字就是1 + 2 + 1 = 4 这时更新max=4, [1, 2, 4], sum=3 下一个数字就是3 + 4 + 1 = 8 大于7 终止 返回集合即可
点赞 回复 分享
发布于 2018-05-20 00:17
二进制的思想,我也被问到这道题了
点赞 回复 分享
发布于 2018-05-20 00:24
应该有的数不满足这个条件吧
点赞 回复 分享
发布于 2018-05-20 00:35
1 2 4 8这样排列,和不超过给定的数,最后再补上一个余数,比如8:1,2,4,1 13:1,2,4,6 21:1,2,4,8,6
点赞 回复 分享
发布于 2018-05-20 00:55

相关推荐

莉莉丝游戏
|
校招
|
17个岗位
点赞 评论 收藏
分享
食其家 java开发 8K一个月
点赞 评论 收藏
分享
点赞 13 评论
分享
牛客网
牛客企业服务