d****r 发帖数: 80 | 1 一道面试题:
给定一个整数数组。怎样能将其分为三组(不要求个数相等),使每组值的总和相等。
不能分的时候返回空值。能分的时候给出一个解就行。
我只能想到三进制,有没有更优化的方法? | c********t 发帖数: 5706 | 2 是整数吧?要求每组的整数个数相等吗?
【在 d****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 一道面试题: : 给定一个整数数组。怎样能将其分为三组(不要求个数相等),使每组值的总和相等。 : 不能分的时候返回空值。能分的时候给出一个解就行。 : 我只能想到三进制,有没有更优化的方法?
| d****r 发帖数: 80 | 3 对,整数。有何高见?
【在 c********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 是整数吧?要求每组的整数个数相等吗?
| j*****y 发帖数: 1071 | 4 用三进制 brute force ?
【在 d****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 对,整数。有何高见?
| d****r 发帖数: 80 | 5 我是那么想的。三进制达不到要求。要求优化解。
【在 j*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 用三进制 brute force ?
| d****r 发帖数: 80 | 6 不要求个数相等。
【在 c********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 是整数吧?要求每组的整数个数相等吗?
| j*****y 发帖数: 1071 | 7 二等分数组是可以用 dp的,
三等分的话,可不可以证明:
如果可以三等分的话,如果拿出一个子集的和是 1/3的和,那么剩下的一定可以二等分?
这个可以证明是正确的话,那么就是两次 dp 了
【在 d****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 一道面试题: : 给定一个整数数组。怎样能将其分为三组(不要求个数相等),使每组值的总和相等。 : 不能分的时候返回空值。能分的时候给出一个解就行。 : 我只能想到三进制,有没有更优化的方法?
| j*****y 发帖数: 1071 | 8 这个可以证明是正确的,那么就是两次 dp
第一次 dp 找出和是 1/3 的总和的子集
第二次dp 等分剩下的集合
分?
【在 j*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 二等分数组是可以用 dp的, : 三等分的话,可不可以证明: : 如果可以三等分的话,如果拿出一个子集的和是 1/3的和,那么剩下的一定可以二等分? : 这个可以证明是正确的话,那么就是两次 dp 了
| z*******8 发帖数: 30 | 9 我觉得这个思路挺好,有点递归的意思,不过条件有点强吧。
比如
1,2,3,
0,0,5,
0,0,7
这个数组就是不能三分的。
分?
【在 j*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 二等分数组是可以用 dp的, : 三等分的话,可不可以证明: : 如果可以三等分的话,如果拿出一个子集的和是 1/3的和,那么剩下的一定可以二等分? : 这个可以证明是正确的话,那么就是两次 dp 了
| j*****y 发帖数: 1071 | 10 不能三分的话两次 dp 也能 detect 出来
【在 z*******8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我觉得这个思路挺好,有点递归的意思,不过条件有点强吧。 : 比如 : 1,2,3, : 0,0,5, : 0,0,7 : 这个数组就是不能三分的。 : : 分?
| | | c********t 发帖数: 5706 | 11 应该不是正确的。1,1,3,4,6
dp 两次也不一定可以 1,1,2,3,4,4 如果第一次拿走 1,1,3,以后将无解啊
【在 j*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个可以证明是正确的,那么就是两次 dp : 第一次 dp 找出和是 1/3 的总和的子集 : 第二次dp 等分剩下的集合 : : 分?
| j*****y 发帖数: 1071 | 12 哈哈,我刚才大脑过了一遍,感觉是对的,看来是错的 :)
【在 c********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 应该不是正确的。1,1,3,4,6 : dp 两次也不一定可以 1,1,2,3,4,4 如果第一次拿走 1,1,3,以后将无解啊
| c********t 发帖数: 5706 | 13 用dp找出=1/3*sum 的所有解,然后对每一组都取剩下的,试试能不能用dp 2等分?
是不是太复杂了?
【在 j*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 哈哈,我刚才大脑过了一遍,感觉是对的,看来是错的 :)
| j*****y 发帖数: 1071 | 14 这个所有解,感觉太复杂了:)
【在 c********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 用dp找出=1/3*sum 的所有解,然后对每一组都取剩下的,试试能不能用dp 2等分? : 是不是太复杂了?
| f*****e 发帖数: 2992 | 15 一个DP就行,然后就看所有解中是否有两个不相交就行。
【在 c********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 用dp找出=1/3*sum 的所有解,然后对每一组都取剩下的,试试能不能用dp 2等分? : 是不是太复杂了?
| c********t 发帖数: 5706 | 16 嗯,同意
【在 f*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 一个DP就行,然后就看所有解中是否有两个不相交就行。
| d**********n 发帖数: 132 | 17 不可以,有反例
分?
【在 j*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 二等分数组是可以用 dp的, : 三等分的话,可不可以证明: : 如果可以三等分的话,如果拿出一个子集的和是 1/3的和,那么剩下的一定可以二等分? : 这个可以证明是正确的话,那么就是两次 dp 了
| d**********n 发帖数: 132 | 18 请大牛明示,这道题的dp是找一个解吧?用一个二维数组来储存当前element可能生成
的和
【在 f*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 一个DP就行,然后就看所有解中是否有两个不相交就行。
| s********i 发帖数: 145 | 19 这道题不是经典的NP-COMPLETE的problem之一么...还解个啥? | t****a 发帖数: 1212 | 20 我把它当二维DP做了,clojure程序和结果如下
(def divide-3-sub
(memoize
(fn [s1 s2 [x & xs]]
(cond (and (zero? s1) (zero? s2)) ['() '() (cons x xs)]
(or (< s1 0) (< s2 0) (empty? xs)) nil
:else (if-let [d1 (divide-3-sub (- s1 x) s2 xs)]
(assoc d1 0 (cons x (first d1)))
(if-let [d2 (divide-3-sub s1 (- s2 x) xs)]
(assoc d2 1 (cons x (second d2)))
(if-let [d3 (divide-3-sub s1 s2 xs)]
(assoc d3 2 (cons x (last d3)))
nil)))))))
(defn divide-3 [x]
(let [s (apply + x)
s3 (int (/ s 3))]
(if (= s (* s3 3))
(divide-3-sub s3 s3 x)
nil)))
(divide-3 (take 12 (repeat 1))) ; [(1 1 1 1) (1 1 1 1) (1 1 1 1)]
(divide-3 (range 6)) ; [(0 1 4) (2 3) (5)]
(divide-3 (range 12)) ; [(0 1 2 3 7 9) (4 8 10) (5 6 11)]
(divide-3 (take 100 (repeatedly #(rand-int 20)))) ; [(19 19 5 19 3 3 7 4 2 4
18 5 16 9 4 16 7 3 12 9 3 19 2 6 13 5 0 3 0 9 3 7 12 8 17 1 7 9 17 1 0 0 0)
(17 18 17 12 19 4 9 18 5 17 3 14 19 16 7 7 1 8 3 14 4 10 19 15 4 15 17 13 1
) (16 15 10 19 6 17 11 15 18 18 14 8 17 11 17 9 19 6 5 2 2 11 7 11 19 15 5 3
)]
这个程序的计算复杂度为O(s*s*n),其中s为数组的总和,n为数组长度。 | | | j*****y 发帖数: 1071 | 21 能把那个 optimal structure 写一下吗?
thanks.
【在 t****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我把它当二维DP做了,clojure程序和结果如下 : (def divide-3-sub : (memoize : (fn [s1 s2 [x & xs]] : (cond (and (zero? s1) (zero? s2)) ['() '() (cons x xs)] : (or (< s1 0) (< s2 0) (empty? xs)) nil : :else (if-let [d1 (divide-3-sub (- s1 x) s2 xs)] : (assoc d1 0 (cons x (first d1))) : (if-let [d2 (divide-3-sub s1 (- s2 x) xs)] : (assoc d2 1 (cons x (second d2)))
| t****a 发帖数: 1212 | 22 f(s1, s2, (x & xs)) = f(s1-x, s2, xs) or f(s1, s2-x, xs) or f(s1, s2, xs)
f(0, 0, (x & xs)) 时候成功
话说楼主的3进制是什么意思啊? | j*****y 发帖数: 1071 | 23 s1 是第一个 subset, s2 是第二个 subset ?
x 和 xs 是什么呢?
【在 t****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : f(s1, s2, (x & xs)) = f(s1-x, s2, xs) or f(s1, s2-x, xs) or f(s1, s2, xs) : f(0, 0, (x & xs)) 时候成功 : 话说楼主的3进制是什么意思啊?
| t****a 发帖数: 1212 | 24 (x & xs)整体表示输入的数字序列。s1是该数字序列中需要分出来第一组的和和第二组
的和。本题s1=s2=1/3 * sum(x & xs)
【在 j*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : s1 是第一个 subset, s2 是第二个 subset ? : x 和 xs 是什么呢?
| w**********o 发帖数: 140 | 25 小弟抛块砖,希望大牛们点评下。
首先sort, 从大到小排列。
L: 100, 98, 97, 76, 50, 30, ...., 10, 9, 2,1
分3组, a, b, c. 挨个拿。
First time
a: 100
b: 98
c: 97
sum(a) = 100
sum(b) = 98
sum(c) = 97 最小, 把L里面最大的分给他
Second time
a: 100,
b: 98,
c: 97, 76
sum(a) =100
sum(b) = 98 最小, 把L里面最大的分给他
sum(c) =173
3rd
a: 100,
b: 98, 50,
c: 97, 76,
sum(a) =100 最小, 把L里面最大的分给他
sum(b) = 148
sum(c) = 173
3rd
a: 100, 30
b: 98, 50,
c: 97, 76,
以此类推, 全部分完。
这样3组的difference比较小,size基本一样的情况下。
算法:个人理解就和国内分蛋糕一样。
每人都拿一块, c拿最小的要说话了, 再给我一份。
c变最大, b说他也要,一次不行,两次,拿到他是最大的(最小的变最大的)。
接着a也不服气,直到大家找到平衡点(找到组合), 要么掀桌
子(return null)。
可用structure,: 2个heap, one min heap for 3(a,b,c), one max heap for list(
same thing as sorted list)。
====
回复楼上,估计不是测试DP问题,interviewer没那个闲工夫测试30mins吧。 | t****a 发帖数: 1212 | 26 这个会挂掉的。因为解的个数在最糟糕情况下是个组合数。
【在 f*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 一个DP就行,然后就看所有解中是否有两个不相交就行。
| t****a 发帖数: 1212 | 27 这样的方法好像是贪婪,不知道能不能保证找到结果啊。我数学不好,有哪位朋友来证
明一下贪婪对不对么?
【在 w**********o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 小弟抛块砖,希望大牛们点评下。 : 首先sort, 从大到小排列。 : L: 100, 98, 97, 76, 50, 30, ...., 10, 9, 2,1 : 分3组, a, b, c. 挨个拿。 : First time : a: 100 : b: 98 : c: 97 : sum(a) = 100 : sum(b) = 98
| w**********o 发帖数: 140 | 28 题目本身是NP, 所以应该没问题吧。
希望PeK能点评下。
【在 t****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这样的方法好像是贪婪,不知道能不能保证找到结果啊。我数学不好,有哪位朋友来证 : 明一下贪婪对不对么?
| d**********x 发帖数: 4083 | 29 http://poj.org/problem?id=1011
一个区别不大的问题,poj的这个只是组数不确定
如果没记错的话,没有多项式解法,只是暴力搜索,加上各种神奇的剪支。
【在 d****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 一道面试题: : 给定一个整数数组。怎样能将其分为三组(不要求个数相等),使每组值的总和相等。 : 不能分的时候返回空值。能分的时候给出一个解就行。 : 我只能想到三进制,有没有更优化的方法?
| s********i 发帖数: 145 | 30
我都说了是NP-COMPLETE了,为什么大家都无视我呢... T_T
【在 d**********x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : http://poj.org/problem?id=1011 : 一个区别不大的问题,poj的这个只是组数不确定 : 如果没记错的话,没有多项式解法,只是暴力搜索,加上各种神奇的剪支。
| | | d**********x 发帖数: 4083 | 31 真没看见你那篇。。
【在 s********i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 我都说了是NP-COMPLETE了,为什么大家都无视我呢... T_T
| f*****e 发帖数: 2992 | 32 对NP-complete,你能搞个pseudopolynoimal算法,也很nb的。
【在 s********i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 我都说了是NP-COMPLETE了,为什么大家都无视我呢... T_T
| v*******e 发帖数: 326 | 33 既然是np complete 为啥还要考楼主算法和优化解?
【在 s********i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 我都说了是NP-COMPLETE了,为什么大家都无视我呢... T_T
| s****r 发帖数: 28 | 34 这个不就是相当于leetcode上的combination sum么?
target = total_sum/3
如果能找两个不相交的组合就可以了
【在 d****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 一道面试题: : 给定一个整数数组。怎样能将其分为三组(不要求个数相等),使每组值的总和相等。 : 不能分的时候返回空值。能分的时候给出一个解就行。 : 我只能想到三进制,有没有更优化的方法?
| d**********x 发帖数: 4083 | 35 Once I was interviewed by fb and the interviewer told me the problem IS an
NP, but he still wanted to see how optimized algorithm I could give
【在 v*******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 既然是np complete 为啥还要考楼主算法和优化解?
| d****r 发帖数: 80 | 36
穷举。N个数的话,用N位的三进制。从0扫到最大值。0,1,2对应三个组。我这个方法实
际上没什么用。
【在 t****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : f(s1, s2, (x & xs)) = f(s1-x, s2, xs) or f(s1, s2-x, xs) or f(s1, s2, xs) : f(0, 0, (x & xs)) 时候成功 : 话说楼主的3进制是什么意思啊?
| b*******e 发帖数: 217 | 37 my solution: 4d np.
recursive function.
Exist(i, a1, a2, a3) = { Exist(i-1, a1-xi, a2, a3) ||
Exist(i-1, a1, a2-xi, a3) ||
Exist(i-1, a1, a2, a3-xi) }
where xi is the ith integer.
a1, a2, a3 are the sum of three subsets in the set.
start from i = 1, a1, a2, a3 = 1
stop at i = n, a1 = a2 = a3 = sum/3.
complexity n * (sum/3)^3.
Any problem with the above DP?
【在 d****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 穷举。N个数的话,用N位的三进制。从0扫到最大值。0,1,2对应三个组。我这个方法实 : 际上没什么用。
| c********t 发帖数: 5706 | 38 两个问题
1.如何保证同一个元素没有被a1,a2,a3重用
2.a3需要吗?如果能求出a1,a2就不用a3了吧。n * (sum/3)^2.
【在 b*******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : my solution: 4d np. : recursive function. : Exist(i, a1, a2, a3) = { Exist(i-1, a1-xi, a2, a3) || : Exist(i-1, a1, a2-xi, a3) || : Exist(i-1, a1, a2, a3-xi) } : where xi is the ith integer. : a1, a2, a3 are the sum of three subsets in the set. : start from i = 1, a1, a2, a3 = 1 : stop at i = n, a1 = a2 = a3 = sum/3. : complexity n * (sum/3)^3.
| f****s 发帖数: 74 | 39 背包问题也是npc啊,
【在 s********i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 我都说了是NP-COMPLETE了,为什么大家都无视我呢... T_T
| c********t 发帖数: 5706 | 40 肯定是不行的
试试用你的做法把 1 3 4 5 6 7分成两组
【在 w**********o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 小弟抛块砖,希望大牛们点评下。 : 首先sort, 从大到小排列。 : L: 100, 98, 97, 76, 50, 30, ...., 10, 9, 2,1 : 分3组, a, b, c. 挨个拿。 : First time : a: 100 : b: 98 : c: 97 : sum(a) = 100 : sum(b) = 98
| | | b*******e 发帖数: 217 | 41 for (2): you are right.
recursive fucntion:
exist(i, a1, a2) = { exist(i-1, a1-xi, a2) ||
exist(i-1, a1, a2-xi)}
starting form i = 1 a1 = 1, a2 =1
end at i = n and a1 = a2 = sum/3.
complexity: n * (sum/3)^2.
don't quite understand (1). any example?
when start froming i = 1 to i = n, the recursive structure ... should be
able to gurantee that xi will only be used for once?
my solution: 3d np. | c********t 发帖数: 5706 | 42 for 1) example 4,6.....
exist(1,10,10)= exist(0,4,10)|| exist(0,10,4);
did ur program put 4 in a1, a2 or both? how about 6?
for 1,3,4,6,1,9, how can you prevent the result to be 1,9| 1,3,6 | 4,6 (use
6 twice)
【在 b*******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : for (2): you are right. : recursive fucntion: : exist(i, a1, a2) = { exist(i-1, a1-xi, a2) || : exist(i-1, a1, a2-xi)} : starting form i = 1 a1 = 1, a2 =1 : end at i = n and a1 = a2 = sum/3. : complexity: n * (sum/3)^2. : don't quite understand (1). any example? : when start froming i = 1 to i = n, the recursive structure ... should be : able to gurantee that xi will only be used for once?
| b*******e 发帖数: 217 | 43 for i == 0, only exist(0, 4, 0) and exist(0, 0, 4) = true. all other
comibinations for i == 0 including exist(0, 4, 10) = false and exist(0, 10,
4) = false, so exist(1, 10, 10) = false.
for i == 1, exist(1, 10, 0) = exist(0, 4, 0 ) || exist(0, 10, -6) = true ||
false. and exist(1, 0, 10) = exist(0, -6, 10) || exist(0, 0, 4) = false ||
true and exist(1, 4, 6) = exist(0, 4, 0) || exist(0, -2, 0) = true || false
and
exist (1, 6, 4) = exist(0, 0, 4) || exist(0, 6, -2) = true || false will be
true. All other combinations will be false.
for 1, 3, 4, 5, 1, 9, "6" participate in the selection only when i == 3. and
it will either stay with 3 and 1, or with 4 for exist(3, 10, 10).
exist(3, 10, 10) = exist(2, 4, 10) || exist(2, 10, 4) = exist(1, 0, 10) ||
exist(1, 4, 6) || exist(1, 6, .... = false.
use
【在 c********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : for 1) example 4,6..... : exist(1,10,10)= exist(0,4,10)|| exist(0,10,4); : did ur program put 4 in a1, a2 or both? how about 6? : for 1,3,4,6,1,9, how can you prevent the result to be 1,9| 1,3,6 | 4,6 (use : 6 twice)
| c********t 发帖数: 5706 | 44 I think it will cause the problem,if continuing, later 4 might be used in
both a1 and a2.
let me simplify my second example to 6,1,3,4,10. By running ur program to
get exist(3,10,10), won't 6 be used in both a1 and a2? exist(3,[6,1,3], [6,
4])?
,
|
|
【在 b*******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : for i == 0, only exist(0, 4, 0) and exist(0, 0, 4) = true. all other : comibinations for i == 0 including exist(0, 4, 10) = false and exist(0, 10, : 4) = false, so exist(1, 10, 10) = false. : for i == 1, exist(1, 10, 0) = exist(0, 4, 0 ) || exist(0, 10, -6) = true || : false. and exist(1, 0, 10) = exist(0, -6, 10) || exist(0, 0, 4) = false || : true and exist(1, 4, 6) = exist(0, 4, 0) || exist(0, -2, 0) = true || false : and : exist (1, 6, 4) = exist(0, 0, 4) || exist(0, 6, -2) = true || false will be : true. All other combinations will be false. : for 1, 3, 4, 5, 1, 9, "6" participate in the selection only when i == 3. and
| b*******e 发帖数: 217 | 45 exist(3, 10, 10)
= exist(2, 10-4, 10) || exist(2, 10, 10-4)
= exist(2, 6, 10) || exist(2, 10, 6) = false || false = false already.
let us continue from i == 2 to i== 1
= exist(1, 3, 10) || exist(1, 6, 7) || exist(1, 7, 6) || exist(1, 6, 7)
= false || false || false || false.
we can continue from i == 1 to 0.
also we can find it is false.
So exist(3, 10, 10) = false. That indicates 6 are not used for multiple
times.
Otherwise exist(3, 10, 10) should be true.
to
6,
【在 c********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : I think it will cause the problem,if continuing, later 4 might be used in : both a1 and a2. : let me simplify my second example to 6,1,3,4,10. By running ur program to : get exist(3,10,10), won't 6 be used in both a1 and a2? exist(3,[6,1,3], [6, : 4])? : : , : | : |
| c********t 发帖数: 5706 | 46 好像你是对的。我有空做做看。多谢!
【在 b*******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : exist(3, 10, 10) : = exist(2, 10-4, 10) || exist(2, 10, 10-4) : = exist(2, 6, 10) || exist(2, 10, 6) = false || false = false already. : let us continue from i == 2 to i== 1 : = exist(1, 3, 10) || exist(1, 6, 7) || exist(1, 7, 6) || exist(1, 6, 7) : = false || false || false || false. : we can continue from i == 1 to 0. : also we can find it is false. : So exist(3, 10, 10) = false. That indicates 6 are not used for multiple : times.
| b*******e 发帖数: 217 | 47 This is a problem in DP chapter of "Algorithms" by a berkeley professor. It
asked for a polynomail complexity solution whether dividing evenly by 3
exists or not.
【在 d****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 一道面试题: : 给定一个整数数组。怎样能将其分为三组(不要求个数相等),使每组值的总和相等。 : 不能分的时候返回空值。能分的时候给出一个解就行。 : 我只能想到三进制,有没有更优化的方法?
|
|