问答

当前位置

Google 面试题 | 最优账户结余

  • Ta: 马克助教

题目描述

一群朋友去度假,有时互相借钱。
例如,爱丽丝为比尔的午餐支付了 10 美元。后来克里斯给爱丽丝 5 美元搭出租车。我们可以假设每笔交易为一个三元组(X,Y,Z),这意味着第 X 个人借给第 Y 个人 Z 美元。假设 Alice,Bill 和 Chris 是第0,1,2 个人(0,1,2是他们的ID),他们之间的交易可以表示为[ [ 0,1,10 ],[ 2,0,5 ] ]。给定一组人之间的交易清单,返回结算所需的最低交易数量。

样例 1

输入 [[0,1,10], [2,0,5]]
输出 2
样例解释
第 0 个人借给第 1 个人10美元
第 2 个人借给第 0 个人 5美元
需要2笔交易,其中一种方式是第1个人还给第0个人和第2个人各5美元。

样例 2

输入 [[0,1,10], [1,0,1], [1,2,5], [2,0,5]]
输出 1
样例解释
第0个人借给第1个人10美元
第1个人借给第0个人1美元
第1个人借给第2个人5美元
第2个人借给第0个人5美元
只需要1笔交易,第1个人还给第0个人4美元债务就还清了。

解题思路

1. 读完题我们会发现每个人都有一个借钱的数量和一个还钱的数量(有可能是0),如果这个人的这两个值的和为0,那么他就不需要还钱或者借钱给别人了。

证明:假设此人在借还之和为0的情况下收到 X 的钱,那么为了收支平衡,必定要把这些钱给另外一个人 Y,那么这样不会比X把钱直接给 Y 得到的答案更优。

比如,设三个人的收支情况为[-2,0,2],那么第3个人把2转移到第2个人,再由第2个人转移到第1个人,需要2次交易,但是第3个人直接转移给第1个人那么只需要1次。

2. 接下来我们只需要处理所有收支不为0的那些人。我们发现,(在数据合法的情况下)所有人的收支情况的和也是0,那么我们就来分析一下如何让答案最小。

对于预处理完收支情况的一个数组[ 2 , 3 , -2 , -3 ] (用正数表示收入,负数表示支出),显而易见答案是2 (2 → -2 , 3 → -3 ),但是还有一种不是最优的答案3(3 → -2 , 1 → -3 , 2 → -2)。那么我们就能发现,最优答案是2个子问题([2,-2],[3,-3])的最优解的和。

我们可以用集合枚举所有的子集,找到每个子集的最优解从而解得总问题的最优解。在这里我们可以把一个集合的子集定义为一个只有 0,1 的向量,

比如一个有3个元素的集合,他们的子集分别是000(空集),001,010,100,011,110,101,111(全集),'1'代表这个子集里有这个元素,'0'代表这个子集里没有这个元素。

再利用一个1~n循环来判断这个子集里有哪些元素,如101代表这个子集里有第1个和第3个元素。

3. 接下来我们分析这种解法的时间复杂度,假设去除所有收支平衡以后的人数为n,枚举子集的时间复杂度为O(2^n),对每个子集进行最优解分析也需要枚举它的所有子集(这些子集的最优解已经计算完成),需要的时间复杂度也为O(2^n),最终的时间复杂度为O(4^n)。空间复杂度为O(2^n)。

参考代码

面试官角度分析

本题难度较大,可能会有多种解法,比如深度优先搜索(需要枚举所有可能的交易情况)等,效率较低。

假如运用这种预处理+动态规划或更高效的方法,那么有 strong hire 的水平,如果能用其他解法(如搜索)解出,则有 hire 的水平。

九章答案链接

Optimal Account Balancing 参考代码

LintCode 相关题目

k 数和
打劫房屋

0 个回复

我来回答

您没有权限

为提高问答质量,问答版块发言权限只向九章学员开放

登录 注册

© Jiu Zhang 2013-. All rights reserved. 京ICP备16004690号-1