V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
ajsonx
V2EX  ›  问与答

面试题,这题目咋做?

  •  
  •   ajsonx · 2020-03-09 17:04:08 +08:00 · 1269 次点击
    这是一个创建于 628 天前的主题,其中的信息可能已经有所发展或是发生改变。

    几个整数组合相加命中某个范围,输出所有的组合方案。int32

    Example1:

    比如输入 {1,2,3} 范围 [7,9]

    可以输出:

    (每个 a[i]的个数,最后一个是 sum )

    7 0 0 7

    8 0 0 8

    9 0 0 9

    0 4 0 8

    Example2:

    输入{1,2,3,4,5} 范围 [30,35]

    输出:

    30 0 0 0 0 30

    0 0 0 0 6 30

    最简单的做法:

    n = sum /a

    m = sum /b

    z = sum /c

    {

    枚举 1 to n

    枚举 1 to m

    枚举 1 to z

    求 sum

    }

    这个时间复杂度肯定不行的。各位大牛有好的解法吗?

    9 条回复    2020-03-10 01:56:15 +08:00
    cassyfar
        1
    cassyfar   2020-03-09 17:27:50 +08:00
    第一个例子没有 0 0 3 9 或者 6 0 1 等等吗?
    cassyfar
        2
    cassyfar   2020-03-09 17:32:54 +08:00
    你那个方法如果是 N 个数组合做不出来吧

    这个可以用 DFS 做 把范围内每个整数都搜索下组合
    ajsonx
        3
    ajsonx   2020-03-09 17:33:53 +08:00
    @cassyfar 有的,太多了没写出来。
    psychoo
        4
    psychoo   2020-03-09 17:38:55 +08:00
    第一反应是深搜,但咋看咋像背包呢
    ajsonx
        5
    ajsonx   2020-03-09 17:54:21 +08:00
    @cassyfar
    谢谢回答
    我那种做法 无法实现在哪一步? N 个数 N 层递归不可以吗?
    DFS 可以,但时间复杂度没有降低。
    ajsonx
        6
    ajsonx   2020-03-09 17:55:23 +08:00
    @psychoo 有道理!谢谢提醒
    不过这题求多个解,背包只有最优解。我尝试用 DP 试试
    BiteTheDust
        7
    BiteTheDust   2020-03-09 18:34:14 +08:00   ❤️ 1
    数据范围?
    这个题假如数字可以重复,假设只有 20 个 1,要求范围为[20,20],那也有整整 C(39,19)=68923264410 种方案数,这样要求输出方案就不实际了。
    zoowii
        8
    zoowii   2020-03-09 18:47:12 +08:00   ❤️ 1
    粗看只想到两个方法

    方法 1,sum 分是否包含某个元素 nums[k[, 变子问题(sum, k-1)和(sum-nums[k], k)。 用 dp 表避免重复计算
    方法 2,nums 中各元素构造最小堆,每次弹出一个元素后把弹出元素加上 nums 各元素后的 len(nums)个新元素推入堆中,不断弹出直到找到范围内所有值
    cassyfar
        9
    cassyfar   2020-03-10 01:56:15 +08:00   ❤️ 1
    @ajsonx DFS 时间复杂度是所有组合的数量 这是最小时间复杂度了吧 你还可以做优化 比如 memorization

    背包我觉得没差别 因为你最后还是要求出所有组合 而不是组合的数目

    你的方法我不是很理解 我以为你是写几个 for loop
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2278 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 12:00 · PVG 20:00 · LAX 04:00 · JFK 07:00
    ♥ Do have faith in what you're doing.