b******y
发帖数: 660 | 1 前段时间看到一道Google Intern的题目，没想出来具体怎么做，所以上来请教一下各
位大侠，请不吝赐教。
意思大概是这样的：
一群人要清算相互之间的欠款，要写check给对方。问能不能找出一种还钱的方法，以
至于每个人只要写一张check.
譬如说
A欠B 10刀，
B欠C 10刀，
B欠D 10刀，
D欠C 20刀，
原本B要写两张check的，一张给C,一张给D，
跟好的方法是B只写一张20刀的check给C,而D写一张10刀的check给C
要设计一个算法判断是否存在有这种只写一张check的解。 |
h***o
发帖数: 1494 | 2 1. Create a matrix like below
A B C D
A 0 10 0 0
B 0 0 10 10
C 0 0 0 0
D 0 0 20 0
2. For each person, caculate the amount as per the matrix
A -10
B -10
C +30
D -10
3. Group negative numbers based on number of positive numbers
For example, there is only one positive, so need only 1 group.
If can't group, return false. (need recursion for grouping) |
d*********i
发帖数: 628 | 3 A B C D
A 0 10 0 0
B 0 0 10 10
C 0 0 0 0
D 0 0 20 0
2. For each person, caculate the amount as per the matrix
A -10
B -10
C +30
D -10 |
b******y
发帖数: 660 | 4 huduo, 能展开说说怎么group么？
例如：
A B C D E F
A 10 10
B 10 10
C 10 10
D
E 20 10
F
对于每个人
A： -20
B： 0
C： -10
D： 40
E： -20
F： 10
有两个正数，怎么group/group不起来? |
h***o
发帖数: 1494 | 5
Create an array, and pass each item
For example,
int amount[4];
for(int i=0;i<4;i++)
amount[i]=0;
A欠B 10刀，amount[0]-=10;amount[1]+=10;
B欠C 10刀，amount[1]-=10;amount[2]+=10;
B欠D 10刀，amount[1]-=10;amount[3]+=10;
D欠C 20刀，amount[3]-=20;amount[2]+=20;
amount[0]=-10;
amount[1]=-10;
amount[2]=30;
amount[4]=-10;
【在 d*********i 的大作中提到】
: A B C D
: A 0 10 0 0
: B 0 0 10 10
: C 0 0 0 0
: D 0 0 20 0
: 2. For each person, caculate the amount as per the matrix
: A -10
: B -10
: C +30
: D -10
|
h***o
发帖数: 1494 | 6
按正负数，先分成两组
group1: 20,10,20
group2: 40,10
问题就变成了，有一个arrary，几个sum，怎么把array里的整数分组，使得每一组的
sum等于
each sum？
if sizeof(group1)
return false;
Sort group1 and group2, so
group1: 10,20,20 (size:n)
group2: 10,40 (size:m)
if(group1[0]>group2[0] || group1[n]>group[m])
return false;
foreach(i in group1)
{
if(i in group2)
remove i from group1 and group2;
}
so,
group1: 20, 20 (size:n)
group2: 40 (size:m)
for(int i=1;i
{
sum group1[0]+group1[1]...
if(the sume == group2[0])
remove each items in the sum from group1
remove group2[0]
recursion/loop
}
【在 b******y 的大作中提到】
: huduo, 能展开说说怎么group么？
: 例如：
: A B C D E F
: A 10 10
: B 10 10
: C 10 10
: D
: E 20 10
: F
: 对于每个人
|
h**6
发帖数: 4160 | 7 使用链式传递付帐法，先在欠款人之间传递，每人加上自己的应付款交给下一个人。然
后在收款人之间传递，每人减去自己的应收款交给下一个人。 |
f****g
发帖数: 313 | 8 1) Model the question as a Directed Graph: A node represents a person; A
directed edge from node A to node B represents person A owns the money to
person B; the weight for each directed edge represents how much money it
owns.
2) Set the rules to combine/remove the the directed edges:
2.1) if the graph contains circles, then remove the edge with minimum
weight, and minus the minimum weight to other edges on the circle.
2.2) If node A has multiples paths to reach node B, always choose the
longest path. Then we could pass the weight to the next node on the path. |
d*********i
发帖数: 628 | |
z****n
发帖数: 1379 | 10 靠，我自己写过一个出去玩以后回来分账还钱的程序，核心问题就是这个，老美不都是
当场aa吗，居然google能问到这个。。。
就是算一下每个人总共欠别人多少刀就行（欠款为负就表示别人欠他），跟楼下给的算
法思路差不多
【在 b******y 的大作中提到】
: 前段时间看到一道Google Intern的题目，没想出来具体怎么做，所以上来请教一下各
: 位大侠，请不吝赐教。
: 意思大概是这样的：
: 一群人要清算相互之间的欠款，要写check给对方。问能不能找出一种还钱的方法，以
: 至于每个人只要写一张check.
: 譬如说
: A欠B 10刀，
: B欠C 10刀，
: B欠D 10刀，
: D欠C 20刀，
|
|
|
K******g
发帖数: 1870 | 11 你这个要先排一下序吧？
【在 h**6 的大作中提到】
: 使用链式传递付帐法，先在欠款人之间传递，每人加上自己的应付款交给下一个人。然
: 后在收款人之间传递，每人减去自己的应收款交给下一个人。
|
h**6
发帖数: 4160 | 12 不需要排序，遍历两次数组即可。第一次把沿负的传递一遍，第二次沿正的传递一遍。 |
h*t
发帖数: 505 | 13 这个算法是错的。
比如a须付20，bc各收10
安装这个算法是无解的，但是正确解法是a写20给b，b写10给c
另一个人说的链式算法是对的。
【在 h***o 的大作中提到】
:
: 按正负数，先分成两组
: group1: 20,10,20
: group2: 40,10
: 问题就变成了，有一个arrary，几个sum，怎么把array里的整数分组，使得每一组的
: sum等于
: each sum？
: if sizeof(group1): return false;
: Sort group1 and group2, so
|
g*******s
发帖数: 2963 | 14 这个算法如果是大家都用cash分可以。
但按题目说的是要用check怎么办呢，check无法传递，也就是说每人必须事先知到
check开给谁和开多少钱，而且只能一张check。
【在 h**6 的大作中提到】
: 不需要排序，遍历两次数组即可。第一次把沿负的传递一遍，第二次沿正的传递一遍。
|
k*****7
发帖数: 72 | 15 链式算法可以找出这样的一个解。
但是问题是，题目是要求判断有没有这样一个解，而不是解是什么，所以应该有更快速
的算法回答。或
者说，在什么样的情况下不存在这样一个解？
【在 b******y 的大作中提到】
: 前段时间看到一道Google Intern的题目，没想出来具体怎么做，所以上来请教一下各
: 位大侠，请不吝赐教。
: 意思大概是这样的：
: 一群人要清算相互之间的欠款，要写check给对方。问能不能找出一种还钱的方法，以
: 至于每个人只要写一张check.
: 譬如说
: A欠B 10刀，
: B欠C 10刀，
: B欠D 10刀，
: D欠C 20刀，
|
k*****7
发帖数: 72 | 16 这样看来，任何情况下都能够找到这样一个每人只写一张check的解了？那题目要判断
有没有这样一个
解是什么意义？
【在 h**6 的大作中提到】
: 使用链式传递付帐法，先在欠款人之间传递，每人加上自己的应付款交给下一个人。然
: 后在收款人之间传递，每人减去自己的应收款交给下一个人。
|
y******5
发帖数: 43 | 17 假如B再欠E钱，而其他人都和E没关系，那么就无解。
我觉得这个可能得对每个人判断能否找到一个有向路径覆盖他的所有债主。对于一个返
回True/False
的函数来说总感觉时间复杂度比较高。
【在 k*****7 的大作中提到】
: 这样看来，任何情况下都能够找到这样一个每人只写一张check的解了？那题目要判断
: 有没有这样一个
: 解是什么意义？
|
k*****7
发帖数: 72 | 18 这种情况也是可以的吧，按链式算，每个人算欠别人多少，别人欠自己多少，确定要支
出或收益的净
值。然后支出人把钱逐一链式传递到一个支出人那里，然后那个人把总数（加上自己的
）付给一个收益
人，然后这个收益人留下自己的部分，再把剩下的钱在收益人组传递下去。
比如 A欠B20，B欠C20， B欠D10，这样A净值-20，B净值-10，C净值20，D净值10，于是
A -> B 20
B -> C 30
C -> D 10
我于是死活也想不出来什么情况下无解。。。
【在 y******5 的大作中提到】
: 假如B再欠E钱，而其他人都和E没关系，那么就无解。
: 我觉得这个可能得对每个人判断能否找到一个有向路径覆盖他的所有债主。对于一个返
: 回True/False
: 的函数来说总感觉时间复杂度比较高。
|
f*********i
发帖数: 197 | 19 我觉得其实有一种最简单的O(n)算法。
按照上面的方法，算出每个人究竟是付钱多还是收钱多，
假设人员a,b,c,d都是付的钱比收的钱多，无论要多付多少
人员e,f,g,h都是收的钱比付的多
解法如下：
a，b,c,d把钱全部给e
e把收到的钱减去应得的钱，然后pass给f
f把收到的钱减去应得的钱，然后pass给g
g把收到的钱减去应得的钱，然后pass给h
完毕
guaranteed everyone signs only one check |
h*t
发帖数: 505 | 20 有解的，b写多余他欠e的钱给e,e写多出的钱给另一个人
【在 y******5 的大作中提到】
: 假如B再欠E钱，而其他人都和E没关系，那么就无解。
: 我觉得这个可能得对每个人判断能否找到一个有向路径覆盖他的所有债主。对于一个返
: 回True/False
: 的函数来说总感觉时间复杂度比较高。
|
y******5
发帖数: 43 | 21 看来我对题意理解有误。我以为一个人只能给他的债主写check，也就是说，在有向图
中我们只能减少
某个点的已有出度边。
如果e可以代替b向"b的而非e的"的债主还钱，感觉总是有解啊，这题目还要我们判断什
么？能说说你的
理解么？
【在 h*t 的大作中提到】
: 有解的，b写多余他欠e的钱给e,e写多出的钱给另一个人
|
