1
coderluan 2020-10-27 15:26:45 +08:00 9
楼主你被误导了, 这题并不是单纯的递归, 单纯的递归一般现学是能搞定的, 这个实际是动态规划问题, 一般解决动态规划问题会用到递归, 但是绝对不是你会递归就能解决动态规划问题.
然后, 我是面试官肯定不给你过了, 不是你不会动态规划和递归, 而是你连循环都不会写, 按你写的, 5 个数你写 5 个变量判断 5 次 15 行代码, 万一工作中要处理 1 万个数, 不得累死你...... |
3
kop1989 2020-10-27 15:32:43 +08:00 1
这……lz 你没有 get 到这个题目的关键点。
这个题目的关键不是真的让你筛选出 5 个数中相加得 13 的。 我帮你翻译翻译:怎么能从 x 个数中“最快”的找到相加为 y 的组合? |
4
kkbblzq 2020-10-27 15:33:36 +08:00
问题是你这循环写的也不怎么样啊,5 重循环亏你写得出来,而且也不对,比如有一个数字是 1,按这题的意思可以选 13 次 1
|
5
hikarikun1991 2020-10-27 15:34:09 +08:00
这是动态规划吧
|
8
gdw1986 OP @hikarikun1991 头一次听说这词
|
9
oahebky 2020-10-27 15:37:20 +08:00 via Android 2
这不是 two sum 吗?
(知道 two sum 的朋友,我有没有理解错题意?) 如果中大厂考我 two sum 我会偷笑... 如果大几十人、100 人刚出头的公司考 two sum 就比较无感,最多觉得公司“身体素质”不错。 |
12
wxsm 2020-10-27 15:41:41 +08:00
DP 头一次听说?哥们你有点水。
|
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) |
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 |
16
oahebky 2020-10-27 15:52:07 +08:00 via Android
哦...
就是有某一个值可以重复取一直加到 13 就可以... 还还是很难的,一时半会我个人想不出高效的思路。 那应该是面的大厂的样子。 |
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,存在递归之外地方 } |
21
devfeng 2020-10-27 15:59:03 +08:00 via Android
什么公司,测试要会动归
|
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); } } ``` |
24
jmc891205 2020-10-27 16:05:45 +08:00 via iPhone
组合的意思就是 5 个数里选 n 个,每个数只能用一次吧
|
25
oahebky 2020-10-27 16:08:04 +08:00
|
26
cnoder 2020-10-27 16:09:46 +08:00
感觉是 dfs 求所有解 剪剪枝
|
28
boring3b 2020-10-27 16:16:42 +08:00
是所有 不是最优 就该暴力来吧
|
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) ``` |
30
lambdafate 2020-10-27 16:20:21 +08:00
@lambdafate 好家伙,直接乱格式
|
31
8Cangtou 2020-10-27 16:21:08 +08:00
回溯+剪枝
|
32
ArthurUp 2020-10-27 16:23:08 +08:00
回溯加剪枝吧
|
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) |
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 就有解的方面入手优化一下 大概思路是这样 |
35
yaphets666 2020-10-27 16:40:25 +08:00
你是测试啊? 我以为你开发呢 测试怎么考算法...
|
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) ``` |
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/ |
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 的实现 |
39
gdw1986 OP @yaphets666 说实话,听到这题,开始没觉得怎么样,越想越不对,这 TM 就是算法题吧
|
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) |
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] 不行的话把结果存下来,再配合个剪枝,应该就行了 |
45
MinQ 2020-10-27 18:13:28 +08:00
格式丢了,这就尴尬了
|
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) |
50
lambdafate 2020-10-27 18:39:38 +08:00
@user8341 是的,都是一类题
|
51
bwt 2020-10-27 18:50:48 +08:00 via Android
Leetcode 零钱兑换 和这个类似
|
52
smallpython 2020-10-27 18:56:09 +08:00
不知道递归的意义是什么, 用循环又容易理解, 效率也更高
|
53
aneureka 2020-10-27 18:57:13 +08:00 via iPhone
这个是完全背包问题🤣
|
54
user8341 2020-10-27 19:20:13 +08:00
|
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 |
56
wulin 2020-10-27 22:24:39 +08:00
背包吧,刷动态规划
|
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); } } } 回溯法吧 |
59
Taikyo 2020-10-28 00:09:30 +08:00
滑动窗口算法应该可以解这道题吧
|
60
binux 2020-10-28 00:21:19 +08:00 via Android
这题有更好的解法,但是暴力的解法你也没做对啊。
|
61
Mrun 2020-10-28 00:40:11 +08:00
老铁,这个是 leetcode 的原题
可以参考一下这个答案 https://leetcode-cn.com/problems/combination-sum/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-2/ |
63
kuangwinnie 2020-10-28 03:29:02 +08:00
@oahebky 不是 2sums
|
64
ericgui 2020-10-28 03:36:50 +08:00
这是 dfs
你要刷 dfs |
65
xrr2016 2020-10-28 09:01:56 +08:00
第一眼看上去要用回溯法
|
66
SuperXRay 2020-10-28 09:16:07 +08:00
dfs + 剪枝 也是递归的一种嘛,猎头没骗你
找测试的话,如果非写代码自动化测试的那种,面这个真的过分了 就说技术岗,我觉得现场写不出来的也有很多 如果并不要求写出正确答案,只从你的解答来看观察专业水平的话,倒也合理 |
67
dany813 2020-10-28 09:17:30 +08:00
面试前还是先刷下算法吧
|
68
simonlu9 2020-10-28 09:25:17 +08:00
感觉和爬楼梯有多少种爬法一个解法
|
69
meathill 2020-10-28 09:36:01 +08:00
楼主让我想起了最近被我开掉的那个哥们儿。说的话听起来好像都懂,表现不好可能是因为临场没发挥出来。结果往细里一看差的不是一点半点。
|
70
ymyqwe 2020-10-28 09:44:45 +08:00
dfs 啊,套路都差不多的,怎么剪枝优化才是重点
|
71
salamanderMH 2020-10-28 09:51:47 +08:00
回溯法可以做这道题。
|
72
fcoolish 2020-10-28 09:52:18 +08:00
这两天刚做了这题,回溯 + 剪枝,题目类型还分数字能不能重复使用。
|
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)) |
74
jtwor 2020-10-28 10:08:39 +08:00
回溯把。。
|
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]]。 |
76
b1ackjack 2020-10-28 10:11:37 +08:00
dfs 可解,leetcode 有原题
|
77
allforone 2020-10-28 10:11:50 +08:00
楼上正解
|
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 } |
79
GroupF 2020-10-28 10:24:58 +08:00
我就留个眼睛吧
|
80
tankren 2020-10-28 10:36:05 +08:00
还需努力 加油吧 虽然我不会写代码。。
|
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% 的用户 |
82
xuxuzhaozhao 2020-10-28 11:02:33 +08:00
这也太严格了,测试都要考算法了吗
|
83
balaWgc 2020-10-28 11:24:37 +08:00
竟然是面试测试,啥厂啊
|
84
ppcoin 2020-10-28 11:32:46 +08:00
动态规划不能做让你列出所有结果的问题
|
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; } } ``` |
86
kanemochi 2020-10-28 11:49:05 +08:00
递归+减枝可以解决
|
87
maplelin 2020-10-28 11:51:25 +08:00
回溯算法,经典的可以重复取值和不能重复取值,算法的核心在于怎么剪枝掉暴力枚举会出现的重复计算,或者多余计算。如果从最小的值开始依次取,一旦和大于 13 之后在枚举就没有意义了,就需要剪枝。
|
88
maplelin 2020-10-28 11:53:03 +08:00
楼主这是直接用的暴力法,估计是不合格了,因为核心考点就是剪枝,不剪枝基本在刷题网站都是直接判超时不给通过的
|
89
user8341 2020-10-28 12:01:13 +08:00
暴力解也得写对呀。不是胡乱瞎写就叫做暴力解。
|
90
zmxnv123 2020-10-28 12:18:52 +08:00 via iPhone
看看 sicp 看完后只会递归了,循环是什么?
|
91
aijam 2020-10-28 12:52:38 +08:00 1
|
92
GoLand 2020-10-28 13:27:20 +08:00
这其实就是遍历二叉树,广度遍历,每个节点的子节点都是数组里的所有数,和大于 13 的节点就剪枝。最后生成的树就是你要的答案。其实还是暴力递归。
|
94
gmywq0392 2020-10-28 13:41:28 +08:00
回溯标准题, 具体表现是递归+剪枝.
|
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) |
98
Hieast 2020-10-28 14:01:26 +08:00
这是面的啥级别,P6 ?
|
99
gaigechunfeng 2020-10-28 14:28:44 +08:00
还是继续努力吧。没办法,既然要吃这碗饭,出去面试都考这个。别人学,你也得学。
|