Amazon男女/儿童服饰鞋包手表配饰7折优惠码CYBERWK14 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Fashion - 美丽时尚

Amazon男女/儿童服饰鞋包手表配饰7折优惠码CYBERWK14

Amazon男女/儿童服饰鞋包手表配饰7折优惠码CYBERWK14# Fashion - 美丽时尚

C*Y2014-11-29 08:11

1 楼

一帮朋友去旅行. 给定一个数组, 表示每人的花费. 旅行结束后相互交易平摊费用. 求
最少需要多少次交易?
例子:
Input: [0, 1, 2, 3, 5, 7]
Output: 3
解释: 6人总花费0+1+2+3+5+7=18刀, 平均每人3刀. 最简方案是第二人给第五人2刀,
第一人给第六人3刀, 第三人给第六人1刀. 所以一共3次交易
Input: [1, 3, 5, 8, 13]
Output: 4

K*92014-11-29 08:11

2 楼

刚刚在USCIS网站上换了地址，不知道他们更新地址要多少时间？我10月的RD，怕出差
错啊

g*o2014-11-29 08:11

3 楼

d*j2014-11-29 08:11

4 楼

median吧
感觉基本上是greedy，欠钱的和收钱分别放入heap里，最顶端的分别是欠钱最多的和付
钱最多的，这两者之间交易一次，总会有一个变成0，或者两个都变成0，然后剩下的
balance重新入heap，nlog(n)可解。

c*x2014-11-29 08:11

5 楼

不在同一个城市，不知道地址暂时不换行么？我还没有换，这个EAD卡早就应该到了，
结果网上CHECK几天前就一直OUT FOR DELIVERY，直到现在也找到到底去了哪里，急人
不？USPS真的不靠谱，据说递送包裹的还是一个小公司承包的！邮局根本不管。没有说
理的地方！
希望你地址更换顺利！

【在 K***9 的大作中提到】

: 刚刚在USCIS网站上换了地址，不知道他们更新地址要多少时间？我10月的RD，怕出差
: 错啊

g*o2014-11-29 08:11

6 楼

在这里
http://www.amazon.com/b/?_encoding=UTF8&camp=1789&creative=3909

w*g2014-11-29 08:11

7 楼

难。如果刨掉平均值后是+7 +5 -3 -4 -4 -1怎么知道-1要给5？多项式时间算法存在
性都是问题。

：一帮朋友去旅行. 给定一个数组, 表示每人的花费. 旅行结束后相互交易平摊费用.
求最少需要多少次交易?
：

x*n2014-11-29 08:11

8 楼

应该是NP hard 吧，比knapsack 问题还要复杂。

f*e2014-11-29 08:11

9 楼

LC原题，答案出题人自己都搞错了。

【在 x*********n 的大作中提到】

: 应该是NP hard 吧，比knapsack 问题还要复杂。

a*a2014-11-29 08:11

10 楼

确实np hard，这个题目的一个特例都是np-hard，比如假设有两个人是多出了钱，然后
其他人都是少出了钱，还钱的时候看会不会需要有个人同时给这两个人钱，是subset
sum问题，subset sum是np hard的

n*g2014-11-29 08:11

11 楼

撑死了easy
不带这么侮辱np-hard的
人家没问你怎么交易，只是问多少次

【在 C*Y 的大作中提到】

: 一帮朋友去旅行. 给定一个数组, 表示每人的花费. 旅行结束后相互交易平摊费用. 求
: 最少需要多少次交易?
: 例子:
: Input: [0, 1, 2, 3, 5, 7]
: Output: 3
: 解释: 6人总花费0+1+2+3+5+7=18刀, 平均每人3刀. 最简方案是第二人给第五人2刀,
: 第一人给第六人3刀, 第三人给第六人1刀. 所以一共3次交易
: Input: [1, 3, 5, 8, 13]
: Output: 4

h*c2014-11-29 08:11

12 楼

我不信面试官自己能写对

r*s2014-11-29 08:11

13 楼

最小费用流
最优解不好写
但是土鳖解法还是可以的

G*g2014-11-29 08:11

14 楼

用greedy没错，感觉不需要heap吧，排序就够了。

: median吧

: 感觉基本上是greedy，欠钱的和收钱分别放入heap里，最顶端的分别是欠钱最多
的和付

: 钱最多的，这两者之间交易一次，总会有一个变成0，或者两个都变成0，然后剩
下的

: balance重新入heap，nlog(n)可解。

【在 d***j 的大作中提到】

: median吧
: 感觉基本上是greedy，欠钱的和收钱分别放入heap里，最顶端的分别是欠钱最多的和付
: 钱最多的，这两者之间交易一次，总会有一个变成0，或者两个都变成0，然后剩下的
: balance重新入heap，nlog(n)可解。

g*y2014-11-29 08:11

15 楼

np hard问题，比如1 6 -7 -2 19 -17，这个例子就不是gready能解决的。

【在 G*******g 的大作中提到】

: 用greedy没错，感觉不需要heap吧，排序就够了。
:
:
: median吧
:
: 感觉基本上是greedy，欠钱的和收钱分别放入heap里，最顶端的分别是欠钱最多
: 的和付
:
: 钱最多的，这两者之间交易一次，总会有一个变成0，或者两个都变成0，然后剩
: 下的
:
: balance重新入heap，nlog(n)可解。
:

r*s2014-11-29 08:11

16 楼

每个人一个节点，源点到节点若有边，权表示负债
节点到终点有边，权表示债权
所有节点连通，边容量无限
跑一个dinic算法，复杂度是多项式的吧？

: np hard问题，比如1 6 -7 -2 19 -17，这个例子就不是gready能解决的。

【在 g****y 的大作中提到】

: np hard问题，比如1 6 -7 -2 19 -17，这个例子就不是gready能解决的。

d*g2014-11-29 08:11

17 楼

1. sort the array
2. deduct a number from the max , add to the min. to make the min into avg.
3. remove the avg
4. go to #1
i.e.
1 6 -7 -2 19 -17 avg = 0
1. sort : 19 6 1 -2 -7 -17
2. deduct 17 from 19: 2 6 1 -2 -7 0
3. remove 0
1. sort: 6 2 1 -2 -7
2. deduct 6 from 6 to -7
3. remove 0
1. sort: 2 1 -1 -2
2. deduct 2 from 2 to -2:
3. remove 0 and 0
1. sort 1 -1
2. deduct 1 to -1
3. remove 0 and 0
all 4 times.

【在 g****y 的大作中提到】

: np hard问题，比如1 6 -7 -2 19 -17，这个例子就不是gready能解决的。

f*n2014-11-29 08:11

18 楼

反例：
-100, -51, -50, 48, 52, 101
按你的方法，一共需要5步
1. [0, -51, -50, 48, 52, 1] => [-51, -50, 1, 48, 52]
2. [0, -50, 1, 48, 1] => [-50, 1, 1, 48]
3. [-2, 1, 1, 0] => [-2, 1, 1]
4. [-1, 1, 0] => [-1, 1]
5. [0, 0]
正解是需要4步：
[-100, 48, 52] 和 [-51, -50, 101]各需要2次
具体错误的原因是：你这个算法第2步的贪心规则缺少理论证明，构造反例只需要一个
最优解中min和max不在一个集合里就可以
这个求transaction(S)的题关键点在于找到集合S的一个partition，使得
transaction(S) = transaction(S1) + transaction(S2)
把集合内每个数减去平均值之后，这个关键点就变成：
在S中找到一个子集S1，使得sum(S1) == 0
因为这个S1一定可以满足transaction(S) = transaction(S1) + transaction(S2)
不幸的是subset sum是个np-hard
幸运的是面试遇到np-hard问题其实很好解，基本上无脑dfs就可以了
接下去聊理想聊人生

【在 d*******g 的大作中提到】

: 1. sort the array
: 2. deduct a number from the max , add to the min. to make the min into avg.
: 3. remove the avg
: 4. go to #1
: i.e.
: 1 6 -7 -2 19 -17 avg = 0
: 1. sort : 19 6 1 -2 -7 -17
: 2. deduct 17 from 19: 2 6 1 -2 -7 0
: 3. remove 0
: 1. sort: 6 2 1 -2 -7

y*g2014-11-29 08:11

19 楼

最小费用最大流中的费用是指“单位费用”，而这题构造的流图要求单边费用固定为1
-- 费用目标函数连续性的缺失导致这个问题就是NP-hard，并无多项式时间算法

: 每个人一个节点，源点到节点若有边，权表示负债

: 节点到终点有边，权表示债权

: 所有节点连通，边容量无限

: 跑一个dinic算法，复杂度是多项式的吧？

【在 r*****s 的大作中提到】

: 每个人一个节点，源点到节点若有边，权表示负债
: 节点到终点有边，权表示债权
: 所有节点连通，边容量无限
: 跑一个dinic算法，复杂度是多项式的吧？
:
:
: np hard问题，比如1 6 -7 -2 19 -17，这个例子就不是gready能解决的。
:

M*n2014-11-29 08:11

20 楼

startup跟风面这种题就是跟自己过不去
那些有很多项目经验的，谁有这个时间刷这种题
那些有时间刷这么多题的，说明工作肯定都不忙，实际项目肯定做的不多，去了
startup很难马上上手
我觉得刷题只是对大公司，找fresh graduate，才比较make sense，找个基本功好的过
来慢慢培养

q*62014-11-29 08:11

21 楼

第一步就是做了一个sorting啊，算一次交易吗？

【在 f*******n 的大作中提到】

: 反例：
: -100, -51, -50, 48, 52, 101
: 按你的方法，一共需要5步
: 1. [0, -51, -50, 48, 52, 1] => [-51, -50, 1, 48, 52]
: 2. [0, -50, 1, 48, 1] => [-50, 1, 1, 48]
: 3. [-2, 1, 1, 0] => [-2, 1, 1]
: 4. [-1, 1, 0] => [-1, 1]
: 5. [0, 0]
: 正解是需要4步：
: [-100, 48, 52] 和 [-51, -50, 101]各需要2次

d*g2014-11-29 08:11

22 楼

你这个例子就按我那个我算来算去也只有四步
1sort
2deduct
3remove
以上重复了4次

【在 f*******n 的大作中提到】

y*g2014-11-29 08:11

23 楼

这个过程确实是5步:
第一步：101 - 100 = 1
第二步：52 - 51 = 1
第三步：48 - 50 = -2
第四步：1 - 2 = -1
第五步：1 - 1 = 0
前面层主列的12345其实省略了真正的第一步

: 你这个例子就按我那个我算来算去也只有四步

: 1sort

: 2deduct

: 3remove

: 以上重复了4次

【在 d*******g 的大作中提到】

: 你这个例子就按我那个我算来算去也只有四步
: 1sort
: 2deduct
: 3remove
: 以上重复了4次

i*w2014-11-29 08:11

24 楼

利口斯留吴，归类为hard.不过只能用dfs解，所以解法本身是median,但是意识到这个
问题是np complete,需要用dfs这个过程属于hard吧。

f*n2014-11-29 08:11

25 楼

我自认为已经写的够清楚了。。。
我的例子就是sort好了的，然后每一步是deduct了一次的结果
没想到还是有人看不懂。。。
我一直觉得面试最重要的就是找能够低成本沟通高效率产出可以一起工作的同事
一个算法思路不懂没关系，一个实现细节不懂也没关系，缺少一些不是那么重要的背景
知识也没关系，谁都是从不会到会的
但是反反复复解释了半天还是不能明白，每天让我怀疑我自己的沟通能力是不是有问题
，我还是不要这样的人做同事的好。。。

【在 d*******g 的大作中提到】

: 你这个例子就按我那个我算来算去也只有四步
: 1sort
: 2deduct
: 3remove
: 以上重复了4次

C*Y2014-11-29 08:11

26 楼

你想多了. 某些startup找的就是不需刷题也能做对这种题的人

【在 M*******n 的大作中提到】

: startup跟风面这种题就是跟自己过不去
: 那些有很多项目经验的，谁有这个时间刷这种题
: 那些有时间刷这么多题的，说明工作肯定都不忙，实际项目肯定做的不多，去了
: startup很难马上上手
: 我觉得刷题只是对大公司，找fresh graduate，才比较make sense，找个基本功好的过
: 来慢慢培养

C*Y2014-11-29 08:11

27 楼

哪道? 刚把LC所有题目标题看了一遍没发现相关的

【在 f*****e 的大作中提到】

: LC原题，答案出题人自己都搞错了。

e*22014-11-29 08:11

28 楼

https://leetcode.com/problems/optimal-account-balancing/description/

【在 C*Y 的大作中提到】

: 哪道? 刚把LC所有题目标题看了一遍没发现相关的

C*Y2014-11-29 08:11

29 楼

谢谢! 难怪我没看到原来是没给LC交钱

【在 e********2 的大作中提到】

: https://leetcode.com/problems/optimal-account-balancing/description/

d*g2014-11-29 08:11

30 楼

我刚看了下，我也没交钱。哈哈。楼上说leetcde也是错的?
早上仔细想了一下，我楼上的贪婪策略错了。下面重新整一个
以这个数列为例子
104 101 57 45 1 -43 -58 -102 -105
最优解应该是5步，
其中关键要点是104和1可以与-105“抵消”；
57和45 可以与-102抵消。
-43 -58抵消101
背后原理如下：
一个N长度的数列，最坏情况（最劣解）需要交换N-1次。这道理很容易想通：10个朋友
，从大到小，挨个把自己多余的钱拿出来，最多交换9次，肯定能完成。
如果在交换过程中能完成一次“抵消”的动作，则可以少交换一次，那么最优解就是N-
1-(抵消的次数），如上述9个数，抵消了3次，则是9-1-3=5为最优解
有一个问题需要研究，就是如果一个数，可以同时参与两个不同的抵消策略，那么哪一
个抵消策略更容易影响最优解呢?比如这个数列
101 56 47 21 2 1 -6 -41 -78 -103
其中56，既可以参与56+47抵消-103，也可以参与56+21+1抵消-78
后者还多一个数参与，那么哪种抵消策略更好？经过计算都一样。具体就不详细说，反
正大概来说就是把N分成A和B两组数的话，如果A和B内没有更优的解法，那么A和B的各
自的最优解一定就是A-1，B-1。则N的解为A+B-2，也就是N-1-1.（多减的这个1正好就
是抵消一次）。所以最优解答与抵消策略无关。
有了上述策略，那么算法就很简单（就是有点占内存）
1.把N以正负分为AB两组。
2.找出A的所有组合之和，以及B的所有组合之和。分别把A的组合存在一个hashmap的
KEY值里面，B的存在一个hashset里。
3.遍历B，找到一个在A里面的“抵消值”，则在A的map的相应VALUE里记1. 同时B的所
有相关节点的组合和可以全部从SET里剔除。（这步就是在找抵消策略），剔除的目的
就是让B已经参与抵消的节点不再参与另一次抵消。
4.循环2-3，直到B遍历完毕或者剔除完毕。WHICHEVER COMES FIRST。
5. 遍历A的MAP，计算有多少value被设为1，即为抵消count
6，结论，最优解次数为 N-1-抵消COUNT
等会上解释和代码

【在 C*Y 的大作中提到】

: 谢谢! 难怪我没看到原来是没给LC交钱

d*g2014-11-29 08:11

31 楼

104 101 57 45 1 -43 -58 -102 -105
1.分成正负两组
104 101 57 45 1 以及 -43 -58 -102 -105
2.
A的组合和为
104, 101, 57, 45, 1,
205(from 104+101), 161(from 104+57), 149(from 104+45), 105(from 104+1),
262(104+101+57), 250(104+101+45)........etc
A中包含的元素为C(5，1)+C（5,2）+C(5，3)+C(5，4)+C(5，5,)=31个组合
B为
-43，-58，-102，-105， -101（-43+-58），etc...
初始化A的map即是(104,0),(101,0),(57,0), (45,0), (205,0), (161, 0), (149,0),
(105,0)...etc
B的Hashset即是上述B的set{-43,-58,-102,-105,-101....etc}
为了让B便于做删除处理，则B的HashSet元素不能简单为一个数字，而是一个对象：
BClass{
int numbersSum;
int[] array = new int[]{参与这个sum的所有number}
}
比如上述的-101，则为
BClass{
int numbersSum = -101;
int[] array = new int[]{-43，-58}
}
那么一旦这个-101参与了抵消动作，则将-101从B中删除，同时将-43和-58参与的所有
sum都从B中删除。
重复以上步骤直到B遍历完毕或者B删除得没有了即可。
然后在A的MAP里找到抵消的有几个。3个，则是9-1-3 = 5

d*g2014-11-29 08:11

32 楼

补充下
1.A里面的VALUE不能超过1，若超过，SKIP继续比较。
2.最后一步无需遍历A，当时即可计数。
3.时间复杂度即为寻找A组合+寻找B组合的时间复杂度+B删除策略的时间复杂度。