V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
gdw1986
V2EX  ›  Python

估计面试没通过,唉

  •  
  •   gdw1986 · 2020-10-27 15:13:32 +08:00 · 16618 次点击
    这是一个创建于 1248 天前的主题,其中的信息可能已经有所发展或是发生改变。
    面试前猎头提示我会考递归,妈的,现学真的搞不定啊,题目是 li = [2,3,5,7,9],输出任意组合,可以重复选,输出所有和是 13 的组合,递归现学现用失败,还是老老实实拿循环写的:
    li = [2,3,5,7,9]

    def sum13(li):
    for i in li:
    if i == 13:
    print(i)
    for j in li:
    if i + j == 13:
    print(i,j)
    for k in li:
    if i + j + k== 13:
    print(i,j,k)
    for l in li:
    if i + j + k + l== 13:
    print(i,j,k,l)
    for o in li:
    if i + j + k + l + o == 13:
    print(i,j,k,l,o)

    我这是面不过了吧?
    125 条回复    2020-11-26 06:20:16 +08:00
    1  2  
    coderluan
        1
    coderluan  
       2020-10-27 15:26:45 +08:00   ❤️ 9
    楼主你被误导了, 这题并不是单纯的递归, 单纯的递归一般现学是能搞定的, 这个实际是动态规划问题, 一般解决动态规划问题会用到递归, 但是绝对不是你会递归就能解决动态规划问题.

    然后, 我是面试官肯定不给你过了, 不是你不会动态规划和递归, 而是你连循环都不会写, 按你写的, 5 个数你写 5 个变量判断 5 次 15 行代码, 万一工作中要处理 1 万个数, 不得累死你......
    gdw1986
        2
    gdw1986  
    OP
       2020-10-27 15:32:00 +08:00
    @coderluan 是的,我觉得也是,哈哈,但是短时间内我实在想不出啥好办法,就硬着头皮写了,总比交白卷强吧
    kop1989
        3
    kop1989  
       2020-10-27 15:32:43 +08:00   ❤️ 1
    这……lz 你没有 get 到这个题目的关键点。
    这个题目的关键不是真的让你筛选出 5 个数中相加得 13 的。

    我帮你翻译翻译:怎么能从 x 个数中“最快”的找到相加为 y 的组合?
    kkbblzq
        4
    kkbblzq  
       2020-10-27 15:33:36 +08:00
    问题是你这循环写的也不怎么样啊,5 重循环亏你写得出来,而且也不对,比如有一个数字是 1,按这题的意思可以选 13 次 1
    hikarikun1991
        5
    hikarikun1991  
       2020-10-27 15:34:09 +08:00
    这是动态规划吧
    gdw1986
        6
    gdw1986  
    OP
       2020-10-27 15:34:16 +08:00
    @kop1989 但是还有重复的情况,脑壳疼,我只是面个测试要不要要求这么高
    gdw1986
        7
    gdw1986  
    OP
       2020-10-27 15:34:58 +08:00
    @kkbblzq 好吧,你是对的
    gdw1986
        8
    gdw1986  
    OP
       2020-10-27 15:36:32 +08:00
    @hikarikun1991 头一次听说这词
    oahebky
        9
    oahebky  
       2020-10-27 15:37:20 +08:00 via Android   ❤️ 2
    这不是 two sum 吗?

    (知道 two sum 的朋友,我有没有理解错题意?)

    如果中大厂考我 two sum 我会偷笑...


    如果大几十人、100 人刚出头的公司考 two sum 就比较无感,最多觉得公司“身体素质”不错。
    gdw1986
        10
    gdw1986  
    OP
       2020-10-27 15:38:13 +08:00
    @oahebky 还可能 one sum 或者 three sum
    wangyzj
        11
    wangyzj  
       2020-10-27 15:41:07 +08:00
    @gdw1986 #6 哈哈哈,面试前刷刷题找找感觉,这玩意一段时间不搞就生疏
    不管你搞啥的,先来个算法恶心一下你
    wxsm
        12
    wxsm  
       2020-10-27 15:41:41 +08:00
    DP 头一次听说?哥们你有点水。
    vipppppp
        13
    vipppppp  
       2020-10-27 15:42:08 +08:00
    感觉可以多看看生成器,最近工作需要,发现这个东西在动态生成数据很有用。

    ii = [2, 3, 5, 7, 9, 1]
    target = 13


    def solution(score=0):
    for i in ii:
    if score + i == target:
    yield [i]
    elif score + i < target:
    for rs in solution(score + i):
    yield [i] + rs


    for s in solution():
    print(s)
    yhxx
        14
    yhxx  
       2020-10-27 15:46:33 +08:00
    @oahebky 这是 N sum 吧
    比 two sum 还是高了一阶的
    MoYi123
        15
    MoYi123  
       2020-10-27 15:49:56 +08:00
    随便写了一个答案,应该是正解

    def solution():
    ____a = [2, 3, 5, 7, 9]
    ____ret = []
    ____memo = set()

    ____def dp(index, acc):
    ________if (index, tuple(acc)) in memo:
    ____________return
    ________else:
    ____________memo.add((index, tuple(acc)))
    ________if index == 5:
    ____________return
    ________if sum(acc) == 13:
    ____________ret.append(tuple(acc))
    ________if sum(acc) >= 13:
    ____________return
    ________dp(index + 1, acc[:])
    ________dp(index, acc[:] + [a[index]])

    ____dp(0, [])
    ____return ret
    oahebky
        16
    oahebky  
       2020-10-27 15:52:07 +08:00 via Android
    哦...

    就是有某一个值可以重复取一直加到 13 就可以...

    还还是很难的,一时半会我个人想不出高效的思路。

    那应该是面的大厂的样子。
    finab
        17
    finab  
       2020-10-27 15:53:44 +08:00
    li 固定为这个数组嘛? 需要考虑 li 不是 5 个数的情况吧?

    递归也可以的,不过性能会比较慢,你这样想


    可以先假定有一个函数 叫 comb,可以将数组的数进行组合, 例如输入 [2,3] 就会返回 [[2],[3],[2,3]]
    问题就变成了 数组中第一个元素与 comb(数组中其他的元素) 组合

    func comb( nums:[Int] ) -> [[Int]] {
    if nums.count <= 1 {
    //数组中就一个元素,直接原样返回
    }
    //数组中第一个元素,与 comb(剩下的元素) 返回值 组合起来
    for( item in comb(去掉第一个,剩下的元素) ) {
    item.insert(nums[0], item.startIndex)
    }

    //计算最终组合的值,是否等于 13,存在递归之外地方

    }
    finab
        18
    finab  
       2020-10-27 15:56:01 +08:00
    @finab 刚写完发现能重复选,那上面的写法是错的 囧~
    georgetso
        19
    georgetso  
       2020-10-27 15:57:21 +08:00
    @oahebky 这不是 two sum, [可以重复选]
    gdw1986
        20
    gdw1986  
    OP
       2020-10-27 15:58:35 +08:00
    @wxsm 哥们只是个测试,确实很水
    devfeng
        21
    devfeng  
       2020-10-27 15:59:03 +08:00 via Android
    什么公司,测试要会动归
    gdw1986
        22
    gdw1986  
    OP
       2020-10-27 16:01:20 +08:00
    @devfeng 哈哈哈,一个做大数据的美企
    hello2060
        23
    hello2060  
       2020-10-27 16:04:29 +08:00   ❤️ 2
    不是 dp 啦,我不知道这叫什么,模式是很常见的

    ```
    void getall(int[] ar, int cur, List<Integer> current, List<List<Inetger>> rslt, int target) {
    if (cur == ar.length) return;

    if (sum(current) == target) {
    rslt.add(current);
    }

    for (int i = cur; i < ar.length; i++) {
    current.add(ar[i]);
    getall(ar, i + 1, current, rslt, target); // 如果每个数只能用一次,不然就从 i 开始
    current.remove(curreent.size() - 1);
    }
    }
    ```
    jmc891205
        24
    jmc891205  
       2020-10-27 16:05:45 +08:00 via iPhone
    组合的意思就是 5 个数里选 n 个,每个数只能用一次吧
    oahebky
        25
    oahebky  
       2020-10-27 16:08:04 +08:00
    @georgetso
    @yhxx
    @gdw1986

    👌 确实不是 two sum 。
    这种 “不一定多少个 [加数] ” & “数组内的某一个数可以重复选” 的题目我个人还没刷到过,换我我也不会做,哈哈哈哈...

    可能暴力解想想会想出来;


    leetcode 只刷了一百多 medium,算法菜鸟一个;
    最近找到工作入职了就暂停练算法了,所以知道自己菜,一看到算法题就问问有没有理解错题意!
    cnoder
        26
    cnoder  
       2020-10-27 16:09:46 +08:00
    感觉是 dfs 求所有解 剪剪枝
    gdw1986
        27
    gdw1986  
    OP
       2020-10-27 16:14:50 +08:00
    @cnoder 停停,现在内卷这么严重了吗,测试都要会算法了
    boring3b
        28
    boring3b  
       2020-10-27 16:16:42 +08:00
    是所有 不是最优 就该暴力来吧
    lambdafate
        29
    lambdafate  
       2020-10-27 16:17:45 +08:00   ❤️ 1
    leetcode 39. 组合总和问题。
    可使用 dfs

    ```
    class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
    ret = []
    candidates.sort()
    self.dfs(candidates, 0, target, [], ret)
    return ret

    def dfs(self, candidates, index, target, path, ret):
    if target == 0:
    ret.append(path)
    return None
    for i in range(index, len(candidates)):
    if candidates[i] > target:
    break
    self.dfs(candidates, i, target-candidates[i], path+[candidates[i]], ret)
    ```
    lambdafate
        30
    lambdafate  
       2020-10-27 16:20:21 +08:00
    @lambdafate 好家伙,直接乱格式
    8Cangtou
        31
    8Cangtou  
       2020-10-27 16:21:08 +08:00
    回溯+剪枝
    ArthurUp
        32
    ArthurUp  
       2020-10-27 16:23:08 +08:00
    回溯加剪枝吧
    finab
        33
    finab  
       2020-10-27 16:36:21 +08:00
    还是用递归,时间复杂度十分感人

    var result: [[Int]] = []

    func comb(nums:[Int], len:Int) -> [[Int]] {
    if len == 0 {
    return []
    }
    if len == 1 {
    return nums.map { [$0] }
    }

    var arr:[[Int]] = []
    for num in nums {
    for var item in comb(nums: nums, len: len - 1) {
    item.append(num)
    arr.append(item)
    }
    }
    arr.forEach { (item) in
    if item.reduce(0, +) == 13 {
    result.append(item)
    }
    }
    return arr
    }

    var nums = [2,3,5]
    comb(nums: nums, len: nums.count)
    print(result)
    easonHHH
        34
    easonHHH  
       2020-10-27 16:39:14 +08:00
    动态规划吧,定义类似一个二维数组。
    先把数组排序,然后>13 的全部舍弃,方便早日跳出循环
    假设数组长度为 1 [2],那可以组合的小于 13 结果就是:[ 2:[[2]],4:[[2,2]],6:[[2,2,2]],8:[[2,2,2,2]],10:[[2,2,2,2,2]],12:[[2,2,2,2,2,2]] ],到 14>13 结束循环
    假设数组长度为 1 [2,3],把 2 的组合+3*N 递归出来,>13 就跳过,直到 3*N>13,结果就是:[ 2:[[2]],[3],4:[[2,2]],5:[[2,3]],6:[[2,2,2],[3,3]],7:[[2,2,3]],8:[[2,2,2,2],[2,3,3]],9:[[3,3,3]],10:[[2,2,2,2,2],[2,2,3,3]],11:[[2,2,2,2,3]],12:[[2,2,2,2,2,2],[2,2,2,3,3],[3,3,3,3]],13:[[2,2,2,2,2,3],[[2,2,3,3,3]] ]
    手写的可能会有纰漏,然后继续,最后把二维数组[13]拉出来就行,而且好像有优化空间,你把[2,4,6,8,10,12].map(n=>{(13-n)%3==0})然后如果余数为 0 就有解的方面入手优化一下
    大概思路是这样
    yaphets666
        35
    yaphets666  
       2020-10-27 16:40:25 +08:00
    你是测试啊? 我以为你开发呢 测试怎么考算法...
    nightcatsama
        36
    nightcatsama  
       2020-10-27 16:50:34 +08:00
    看到输出所有组合,第一时间想到的是递归加回溯。
    ```js
    function NSum(arr, target) {
    let res = []
    function dfs(start, list, total) {
    if (total >= target) {
    if (total === target) res.push([...list])
    return
    }
    for (let i = start; i < arr.length; i++) {
    list.push(arr[i])
    dfs(i, list, total + arr[i])
    list.pop()
    }
    }
    dfs(0, [], 0)
    return res
    }

    NSum([2,3,5,7,9], 13)
    ```
    user8341
        37
    user8341  
       2020-10-27 16:59:25 +08:00
    @lambdafate 确实是这道题 Combination Sum,还有 Coin Change 2 其实也是类似的吧?

    leetcode.com/problems/combination-sum/

    leetcode.com/problems/coin-change-2/
    zjlletian
        38
    zjlletian  
       2020-10-27 17:07:14 +08:00
    ```
    package main

    import (
    "fmt"
    )

    var items = []int{2, 3, 5, 7, 9}
    var target int = 13

    func main() {
    findSum([]int{}, 0)
    }

    func findSum(list []int, sum int) {
    for _, i := range items {
    if sum+i > target {
    return
    }
    newList := append(list, i)
    if sum+i == target {
    fmt.Println(newList)
    return
    }
    findSum(newList, sum+i)
    }
    return
    }
    ```

    go 的实现
    gdw1986
        39
    gdw1986  
    OP
       2020-10-27 17:24:51 +08:00
    @yaphets666 说实话,听到这题,开始没觉得怎么样,越想越不对,这 TM 就是算法题吧
    Kvip
        40
    Kvip  
       2020-10-27 17:49:50 +08:00
    不知道能否用第三方库完成,特意去找了下答案

    ```
    from itertools import combinations_with_replacement
    li = [2, 3, 5, 7, 9]
    for item in combinations_with_replacement(li, 3):
    if sum(item) == 13:
    print(item)
    ```
    输出结果:
    (2, 2, 9)
    (3, 3, 7)
    (3, 5, 5)
    kera0a
        41
    kera0a  
       2020-10-27 17:57:04 +08:00 via iPhone
    @Kvip 取的数个数不固定,
    还需再套一层循环,个数 3 改成 1 到 n 每个都算一次
    kera0a
        42
    kera0a  
       2020-10-27 17:59:21 +08:00 via iPhone
    @Kvip 并且 n 并不是 nums.count,仔细想想还挺难的
    user8341
        43
    user8341  
       2020-10-27 18:10:07 +08:00
    @gdw1986
    leetcode 题目还有一个限定条件:保证组合不超过 150 种。
    所以只要递归法就够了吧。
    MinQ
        44
    MinQ  
       2020-10-27 18:13:05 +08:00
    num = [2,3,5,7,9]
    result = []

    def calc(result):
    for i in range(0,5):
    result.append(num[i])
    if sum(result) == 13:
    print(result)
    result.pop()
    return
    elif sum(result) < 13:
    calc(result)
    result.pop()
    return

    calc(result)

    python 的,这样会有重复选择的情况,比如
    [2, 2, 2, 2, 2, 3]
    [2, 2, 2, 2, 3, 2]
    不行的话把结果存下来,再配合个剪枝,应该就行了
    MinQ
        45
    MinQ  
       2020-10-27 18:13:28 +08:00
    格式丢了,这就尴尬了
    MinQ
        46
    MinQ  
       2020-10-27 18:20:49 +08:00   ❤️ 1
    num = [2,3,5,7,9]
    result = []


    def calc(result):
    ____for i in range(0,5):
    ________result.append(num[i])
    ________if sum(result) == 13:
    ____________print(result)
    ____________result.pop()
    ____________return
    ________elif sum(result) < 13:
    ____________calc(result)
    ________result.pop()
    ____return


    calc(result)
    gdw1986
        47
    gdw1986  
    OP
       2020-10-27 18:21:42 +08:00
    @MinQ 感觉你这个靠谱,因为猎头提示了递归,但是我没搞出你这个的结果,格式不对
    MinQ
        48
    MinQ  
       2020-10-27 18:22:19 +08:00
    @gdw1986 格式的问题,下面那一版已经修正了
    gdw1986
        49
    gdw1986  
    OP
       2020-10-27 18:27:59 +08:00
    @MinQ 试了,厉害,应该就是这个答案
    lambdafate
        50
    lambdafate  
       2020-10-27 18:39:38 +08:00
    @user8341 是的,都是一类题
    bwt
        51
    bwt  
       2020-10-27 18:50:48 +08:00 via Android
    Leetcode 零钱兑换 和这个类似
    smallpython
        52
    smallpython  
       2020-10-27 18:56:09 +08:00
    不知道递归的意义是什么, 用循环又容易理解, 效率也更高
    aneureka
        53
    aneureka  
       2020-10-27 18:57:13 +08:00 via iPhone
    这个是完全背包问题🤣
    user8341
        54
    user8341  
       2020-10-27 19:20:13 +08:00
    @lambdafate

    题目条件完全一样,只是要求的计算结果不同:一题要求列出所有组合,一题要求计算组合总数。

    列出所有组合的这题是不是没办法用动态规划呀?
    shen132465
        55
    shen132465  
       2020-10-27 22:20:05 +08:00
    @cnoder 就是这样
    ```
    public class NSum {
    static int res = 13;
    static int idx = 0;
    public static void main(String[] args) {
    int[] arr = {2, 3, 5, 7, 9};
    Stack<Integer> resStack = new Stack();
    traceback(arr, 0, 0,resStack);
    }

    public static void traceback(int[] arr, int s,int sum,Stack<Integer> resStack){
    for (int i = s; i < arr.length; i++) {
    int cs = sum + arr[i];
    if(cs > res){
    break;
    }
    resStack.push(arr[i]);
    if(cs == res){
    System.out.println(idx++ + " - " + resStack + " - " + i + " - " + cs);
    resStack.pop();
    break;
    }
    traceback(arr,i,cs,resStack);
    resStack.pop();
    }
    }
    }
    ```
    ```
    0 - [2, 2, 2, 2, 2, 3] - 1 - 13
    1 - [2, 2, 2, 2, 5] - 2 - 13
    2 - [2, 2, 2, 7] - 3 - 13
    3 - [2, 2, 3, 3, 3] - 1 - 13
    4 - [2, 2, 9] - 4 - 13
    5 - [2, 3, 3, 5] - 2 - 13
    6 - [3, 3, 7] - 3 - 13
    7 - [3, 5, 5] - 2 - 13
    wulin
        56
    wulin  
       2020-10-27 22:24:39 +08:00
    背包吧,刷动态规划
    gdw1986
        57
    gdw1986  
    OP
       2020-10-27 22:32:54 +08:00 via Android
    @wulin #56 背包是什么意思?
    lu5je0
        58
    lu5je0  
       2020-10-27 22:32:57 +08:00   ❤️ 1
    public static List<List<Integer>> cal(int[] arr, int target) {
    List<List<Integer>> results = new ArrayList<>();
    func(results, new ArrayList<>(), arr, target, 0);
    return results;
    }

    public static void func(List<List<Integer>> results, List<Integer> curList, int[] arr, int target, int start) {
    int num = curList.stream().mapToInt(value -> value).sum();
    if (num > target) {
    return;
    }

    if (num == target) {
    results.add(new ArrayList<>(curList));
    } else {
    for (int i = start; i < arr.length; i++) {
    curList.add(arr[i]);
    func(results, curList, arr, target, i);
    curList.remove(curList.size() - 1);
    }
    }
    }
    回溯法吧
    Taikyo
        59
    Taikyo  
       2020-10-28 00:09:30 +08:00
    滑动窗口算法应该可以解这道题吧
    binux
        60
    binux  
       2020-10-28 00:21:19 +08:00 via Android
    这题有更好的解法,但是暴力的解法你也没做对啊。
    Mrun
        61
    Mrun  
       2020-10-28 00:40:11 +08:00
    Mrun
        62
    Mrun  
       2020-10-28 00:43:55 +08:00
    @oahebky #25 leetcode 39 和 40,这个是面试的经典题型
    kuangwinnie
        63
    kuangwinnie  
       2020-10-28 03:29:02 +08:00
    @oahebky 不是 2sums
    ericgui
        64
    ericgui  
       2020-10-28 03:36:50 +08:00
    这是 dfs

    你要刷 dfs
    xrr2016
        65
    xrr2016  
       2020-10-28 09:01:56 +08:00
    第一眼看上去要用回溯法
    SuperXRay
        66
    SuperXRay  
       2020-10-28 09:16:07 +08:00
    dfs + 剪枝 也是递归的一种嘛,猎头没骗你
    找测试的话,如果非写代码自动化测试的那种,面这个真的过分了
    就说技术岗,我觉得现场写不出来的也有很多

    如果并不要求写出正确答案,只从你的解答来看观察专业水平的话,倒也合理
    dany813
        67
    dany813  
       2020-10-28 09:17:30 +08:00
    面试前还是先刷下算法吧
    simonlu9
        68
    simonlu9  
       2020-10-28 09:25:17 +08:00
    感觉和爬楼梯有多少种爬法一个解法
    meathill
        69
    meathill  
       2020-10-28 09:36:01 +08:00
    楼主让我想起了最近被我开掉的那个哥们儿。说的话听起来好像都懂,表现不好可能是因为临场没发挥出来。结果往细里一看差的不是一点半点。
    ymyqwe
        70
    ymyqwe  
       2020-10-28 09:44:45 +08:00
    dfs 啊,套路都差不多的,怎么剪枝优化才是重点
    salamanderMH
        71
    salamanderMH  
       2020-10-28 09:51:47 +08:00
    回溯法可以做这道题。
    fcoolish
        72
    fcoolish  
       2020-10-28 09:52:18 +08:00
    这两天刚做了这题,回溯 + 剪枝,题目类型还分数字能不能重复使用。
    18870715400
        73
    18870715400  
       2020-10-28 09:52:43 +08:00
    这个应该是回溯吧
    def f(lst, target):
    ans = []
    def dfs(val_index, index):
    if sum([lst[i] for i in val_index]) == target:
    ans.append([lst[i] for i in val_index])
    return
    if sum([lst[i] for i in val_index]) > target:
    return
    for i in range(index, len(lst)):
    if i in val_index:
    continue
    dfs(val_index+[i], i+1)
    dfs([], 0)
    return ans

    print(f([1, 2, 3, 4, 5, 6, 7], 8))
    jtwor
        74
    jtwor  
       2020-10-28 10:08:39 +08:00
    回溯把。。
    tianhualefei
        75
    tianhualefei  
       2020-10-28 10:09:47 +08:00 via Android
    这是 leetcode 上面第 518 题,的零钱兑换问题 II,给定不同面额的硬币个一个总金额,写出函数计算可以凑成总金额额额硬币组合数。假设每种面额的硬币无限个。

    状态表示 dp[i][j],表示数组前 i 个数[0.....i-1]组成金额为 j 的硬币组合数。
    第 i 种货币可以不拿,可以拿 1…n 次。
    递推方程 dp[i][j]=dp[i-1][j]+dp[i-1][j-coni[i]]+dp[i-1][j-k*coin[i]],简化为
    dp[i][j]=dp[i-1][j]+dp[i][j-coin[i]]或一维的 dp[j]=dp[j]+dp[j-coin[i]]。
    b1ackjack
        76
    b1ackjack  
       2020-10-28 10:11:37 +08:00
    dfs 可解,leetcode 有原题
    allforone
        77
    allforone  
       2020-10-28 10:11:50 +08:00
    楼上正解
    caoyouming
        78
    caoyouming  
       2020-10-28 10:23:59 +08:00
    func combinationSum(candidates []int, target int) [][]int {
    return findSum(candidates, target)
    }

    func findSum(candidates []int, target int) [][]int {
    var result [][]int
    var list []int
    var sum int
    for _,val :=range candidates{
    if sum + val > target{
    return result
    }else{
    newList := append(list,val)
    if sum + val == target{
    result = append(result, newList)
    }else{
    findSum(newList, sum + val)
    }
    }
    }
    return result
    }
    GroupF
        79
    GroupF  
       2020-10-28 10:24:58 +08:00
    我就留个眼睛吧
    tankren
        80
    tankren  
       2020-10-28 10:36:05 +08:00
    还需努力 加油吧 虽然我不会写代码。。
    cyrbuzz
        81
    cyrbuzz  
       2020-10-28 10:37:07 +08:00
    dp 走一波。

    ```
    /**
    * @param {number[]} candidates
    * @param {number} target
    * @return {number[][]}
    */
    var combinationSum = function(candidates, target) {
    // 思路就是 dp
    // 比如 target 2 的解是子问题 1 的解+子问题 1 的解,和 2 自己
    // target 3 的解可以是子问题 1 的解+子问题 1 的解+子问题 1 的解 / 子问题 1 的解+子问题 2 的解和 3 自己
    // target 4 的解就是 3 的解+1+自己。
    // 变一下这个思路,7 的解应该是自己(如果有) + 6 - 1 中的组合。
    // 还可继续优化。

    candidates = candidates.sort((a, b) => {
    return a - b
    })

    let _find = {}

    candidates.map((item) => {
    _find[item] = 1
    })

    let dp = [
    ]

    if (candidates[0] === 1) {
    dp.push({
    num: 1,
    sub: [[1]]
    })
    } else {
    dp.push({
    num: 1,
    sub: []
    })
    }

    for (let i=2; i <= target; i++) {
    let sub = []
    let old = {}
    for (let j = i-1; j > 0; j--) {
    if (dp[j-1].sub.lenght !== 0 && _find[i-j]) {
    for (let c of dp[j-1].sub) {
    let temp = [...c, i-j].sort((a, b) => {
    return a - b
    })
    if (!old[temp.join('')]) {
    sub.push(temp)
    old[temp.join('')] = 1
    continue
    }

    }
    }
    }

    if (_find[i]) {
    sub.push([i])
    }

    dp.push({
    num: i,
    sub: sub
    })
    }

    // console.log(dp[dp.length - 1].sub)
    return dp[dp.length - 1].sub
    };
    ```

    https://leetcode-cn.com/problems/combination-sum/

    执行用时:
    156 ms
    , 在所有 JavaScript 提交中击败了
    11.81%
    的用户
    内存消耗:
    46.9 MB
    , 在所有 JavaScript 提交中击败了
    5.04%
    的用户
    xuxuzhaozhao
        82
    xuxuzhaozhao  
       2020-10-28 11:02:33 +08:00
    这也太严格了,测试都要考算法了吗
    balaWgc
        83
    balaWgc  
       2020-10-28 11:24:37 +08:00
    竟然是面试测试,啥厂啊
    ppcoin
        84
    ppcoin  
       2020-10-28 11:32:46 +08:00
    动态规划不能做让你列出所有结果的问题
    blackshow
        85
    blackshow  
       2020-10-28 11:44:45 +08:00
    如果是白板题,可能很大概率写不出来.
    ```
    public class SumTest {

    public static void main(String[] args) {
    Integer[] li = new Integer[]{2, 3, 5, 7, 9};
    int target = 13;
    List<Integer[]> sum = sum(li, target);
    for (Integer[] i : sum) {
    System.out.print(Arrays.toString(i));
    }
    }

    private static List<Integer[]> sum(Integer[] args, int target) {
    List<Integer> nums = Arrays.asList(args);
    List<Integer[]> result = new ArrayList<>();
    for (int i = 0; i < (args.length % 2 == 0 ? args.length / 2 : args.length / 2 + 1); i++) {
    int num = args[i];
    int sum = num;
    int count = 1;
    while (target - sum > 0) {
    List<Integer> temp = new ArrayList<>();
    for (int j = 0; j < count; j++) {
    temp.add(num);
    }
    if (nums.contains(target - sum)) {
    temp.add(target - sum);
    result.add(temp.toArray(new Integer[0]));
    }
    sum = sum + args[i];
    count++;
    }
    }
    return result;
    }
    }

    ```
    kanemochi
        86
    kanemochi  
       2020-10-28 11:49:05 +08:00
    递归+减枝可以解决
    maplelin
        87
    maplelin  
       2020-10-28 11:51:25 +08:00
    回溯算法,经典的可以重复取值和不能重复取值,算法的核心在于怎么剪枝掉暴力枚举会出现的重复计算,或者多余计算。如果从最小的值开始依次取,一旦和大于 13 之后在枚举就没有意义了,就需要剪枝。
    maplelin
        88
    maplelin  
       2020-10-28 11:53:03 +08:00
    楼主这是直接用的暴力法,估计是不合格了,因为核心考点就是剪枝,不剪枝基本在刷题网站都是直接判超时不给通过的
    user8341
        89
    user8341  
       2020-10-28 12:01:13 +08:00
    暴力解也得写对呀。不是胡乱瞎写就叫做暴力解。
    zmxnv123
        90
    zmxnv123  
       2020-10-28 12:18:52 +08:00 via iPhone
    看看 sicp 看完后只会递归了,循环是什么?
    aijam
        91
    aijam  
       2020-10-28 12:52:38 +08:00   ❤️ 1
    GoLand
        92
    GoLand  
       2020-10-28 13:27:20 +08:00
    这其实就是遍历二叉树,广度遍历,每个节点的子节点都是数组里的所有数,和大于 13 的节点就剪枝。最后生成的树就是你要的答案。其实还是暴力递归。
    no1xsyzy
        93
    no1xsyzy  
       2020-10-28 13:34:17 +08:00
    @zmxnv123 你这显然只看了一半,sicp 不是明确指出递归可以方便地转写成迭代了吗?
    gmywq0392
        94
    gmywq0392  
       2020-10-28 13:41:28 +08:00
    回溯标准题, 具体表现是递归+剪枝.
    no1xsyzy
        95
    no1xsyzy  
       2020-10-28 13:49:23 +08:00
    不确定选取个数啊,那确实是剪枝完事

    @easonHHH @cyrbuzz 这是 BFS 吧(
    fsworld
        96
    fsworld  
       2020-10-28 13:54:55 +08:00   ❤️ 2
    JavaScript 版本的:

    var li = [2, 3, 5, 7, 9]

    function getCombination(target, arr = []) {
    li.forEach(value => {
    if (target - value < 0) {
    return
    }
    if (target - value === 0) {
    console.log(arr.concat(value))
    return
    }
    getCombination(target - value, arr.concat(value))
    })
    }

    getCombination(13)
    easonHHH
        97
    easonHHH  
       2020-10-28 13:56:38 +08:00
    @no1xsyzy #95
    这属于动态规划的完全背包问题也不矛盾吧,算法题多种思路解也很常见
    Hieast
        98
    Hieast  
       2020-10-28 14:01:26 +08:00
    这是面的啥级别,P6 ?
    gaigechunfeng
        99
    gaigechunfeng  
       2020-10-28 14:28:44 +08:00
    还是继续努力吧。没办法,既然要吃这碗饭,出去面试都考这个。别人学,你也得学。
    no1xsyzy
        100
    no1xsyzy  
       2020-10-28 14:39:37 +08:00
    @easonHHH 我是说你们俩写出来的都是 BFS……
    1  2  
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3118 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 34ms · UTC 14:30 · PVG 22:30 · LAX 07:30 · JFK 10:30
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.