狗狗惨烈电面

自我介绍后就问了一个问题
给一批人， 这些人每人都花了一笔钱，

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

个加面就好了。。。。
好蛋碎，，，

public void calculate(int[] nums) {
                int sum = 0;
                for (int i : nums) {
                        sum += i;
                }
                double avg = sum * 1.0 / nums.length;
                double[] temp = new double[nums.length];
                for (int i = 0; i < nums.length; i++) {
                        temp[i] = avg - nums[i];
                }
                int cur1 = 0; //pos
                int cur2 = 0; //neg
                while (cur1 < nums.length) {
                        while (cur1 < nums.length && temp[cur1] <= 0) {
                                cur1++;
                        }
                        while (cur2 < nums.length && temp[cur2] >= 0) {
                                cur2++;
                        }
                        if (cur1 < nums.length && cur2 < nums.length) {
                                double min = Math.min(temp[cur1], -temp[cur2]);
                                System.out.println("" + cur2 + " gives " + (min) + " to " + cur1);
                                temp[cur1] -= min;
                                temp[cur2] += min;
                        }
                }
        }


求帮忙看看

这题是个数学问题，最后你发现是一个公式，假设ABCDE 5个人，分别花了nums = {1, 2, 3, 4, 5}，假设从A的角度出发，分别计算A要给BCDE多少钱，如果是负数就反过来给A，最后结果是，A要给第i个人：
gives = (n * nums - sum) / n;
其中n是总人数，sum是所有人花的钱总和，nums是第i个人花的钱。代码如下：

1. void giveMoney(vector<int> &nums) {
   
2.   int n = nums.size();
   
3.   int sum = 0;
   
4.   for (int i : nums)
   
5.     sum += i;
   
6.   for (int i = 1; i < n; ++ i) {
   
7.     int cur = (n * nums[i] - sum) * 1.0 / n;
   
8.     cout << "gives " << i << " $" << cur << endl;
   
9.   }
   
10. }

复制代码

e.g. n = 5, nums = {1,2,3,4,5}:
$ ./a.out
gives 1 $-1
gives 2 $0
gives 3 $1
gives 4 $2

补充内容 (2016-9-8 03:32):
少写了[i], 公式是:
gives = (n * nums[i] - sum) / n;
其中n是总人数，sum是所有人花的钱总和，nums[i]是第i个人花的钱。

补充内容 (2016-9-8 03:33):
额方括号打不出来么...

This problem can be done by general way:
go through the array starting at index 1, for each element larger than the average, give the superfluous money to the first guy
go through the array starting at index 1, for each element smaller than the average, the first guy give its money to make him to average.

才面完就想到更好的解法了。。写出那么复杂的我也是醉了。。。

对的，就是这个意思

没有要求least transactions什么的？

fatalme 发表于 2016-9-8 03:06
没有要求least transactions什么的？

没有， 估计来不及问了吧， 我写完也没多少时间了， 估计是跪了

ivanml 发表于 2016-9-8 03:31
这题是个数学问题，最后你发现是一个公式，假设ABCDE 5个人，分别花了nums = {1, 2, 3, 4, 5}，假设从A的角 ...

按照楼主的意思，是应该要求出来，特定的谁给谁多少钱，不是一个人拿多少或者给多少

Xochitl 发表于 2016-9-8 03:52
按照楼主的意思，是应该要求出来，特定的谁给谁多少钱，不是一个人拿多少或者给多少

你看我的输出里第一项是“gives 1 $-1”，意思就是1号要给0号$1。
当然你说不特定以某个人的角度当然可以，但是我觉得会更复杂，只要能得到一个合法解，应该就可以了吧。

ivanml 发表于 2016-9-8 04:02
你看我的输出里第一项是“gives 1 $-1”，意思就是1号要给0号$1。
当然你说不特定以某个人的角度当然可 ...

纯讨论啊，感觉2楼的two pointer比较合适，这种输出“gives 1 $-1”==1号要给0号$1，感觉还是直接输出1 gives 0 $1比较make sense一些