我在思考一个问题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Stock

我在思考一个问题

我在思考一个问题# Stock

h*n2010-12-12 08:12

1 楼

题1
Given an array with non negative numbers, divide the array into two parts
such that the average of both the parts is equal.
Return both parts (If exist).
If there is no solution. return an empty list.
Example:
Input:
[1 7 15 29 11 9]
Output:
[9 15] [1 7 11 29]
The average of part is (15+9)/2 = 12,
average of second part elements is (1 + 7 + 11 + 29) / 4 = 12
题2：
Given an array A of integers, find the index of values that satisfy A + B =
C + D, where A,B,C & D are integers values in the array
Note:
1) Return the indices `A1 B1 C1 D1`, so that
A[A1] + A[B1] = A[C1] + A[D1]
A1 < B1, C1 < D1
A1 < C1, B1 != D1, B1 != C1
2) If there are more than one solutions,
then return the tuple of values which are lexicographical smallest.
Assume we have two solutions
S1 : A1 B1 C1 D1 ( these are values of indices int the array )
S2 : A2 B2 C2 D2
S1 is lexicographically smaller than S2 iff
A1 < A2 OR
A1 = A2 AND B1 < B2 OR
A1 = A2 AND B1 = B2 AND C1 < C2 OR
A1 = A2 AND B1 = B2 AND C1 = C2 AND D1 < D2

j*72010-12-12 08:12

2 楼

为什么现在国内发生的那些被老百姓痛恨的事情在历史上一朝一朝的反复发生（具体可
以参看吳思写的血酬中的例子）．难道是经济上的需要吗？

b*t2010-12-12 08:12

3 楼

第一个题 O(n) 求出average 数字是多少
题目就变成在集合中找任意个数（找到一个另外剩下的必然是等于 average
dfs暴力搜一下(求有更好的办法吗？)

w*u2010-12-12 08:12

4 楼

第一题是不是可以这样：
先sort 一下原来的序列，O(nlogn)
求得 average 数字O(n),
binary search average，如果直接能在序列中找到这个数，那序列就能直接分成一边
是一个，另外一边就是剩下的数
如果找不到，找到average可以插入的idx，这样把序列分成两半，一边小于average，
另外一边大于average。
大家都减去average，这样一边就是正数，一边是负数，
问题就变成在两个半边中，找想加等于0的组合。
对于每个半边，纪录sum和idx的对应关系。
这样只要两个sum互为正负对，就能找到partition了

w*u2010-12-12 08:12

5 楼

第二题如何解？

j*a2010-12-12 08:12

6 楼

多个sum为0怎么办？

：第一题是不是可以这样：
：先sort 一下原来的序列，O(nlogn)
：求得 average 数字O(n),
：binary search average，如果直接能在序列中找到这个数，那序列就能直接分成一
边是一个，另外一边就是剩下的数
：如果找不到，找到average可以插入的idx，这样把序列分成两半，一边小于average，
：另外一边大于average。
：大家都减去average，这样一边就是正数，一边是负数，
：问题就变成在两个半边中，找想加等于0的组合。
：对于每个半边，纪录sum和idx的对应关系。
：这样只要两个sum互为正负对，就能找到partition了

【在 w***u 的大作中提到】

: 第二题如何解？

j*a2010-12-12 08:12

7 楼

: 第二题如何解？

w*u2010-12-12 08:12

8 楼

那就换成map，
map>,
左边的part 比如说有 5种sum的可能，右边的part 有10种可能
遍历左边的part sum，看能不能在右边找到对应的负值，找到了就算是一个正确的划分
，遍历一下里面是不是能找到多个负值。都记录下来就行了。

w*u2010-12-12 08:12

9 楼

至于求 sum 和 vector 的对应，我觉得就是求array的
permutation

m*n2010-12-12 08:12

10 楼

第一题是不是能当成0-1背包问题用DP做，如果数组Sum不太大的话

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

: 题1
: Given an array with non negative numbers, divide the array into two parts
: such that the average of both the parts is equal.
: Return both parts (If exist).
: If there is no solution. return an empty list.
: Example:
: Input:
: [1 7 15 29 11 9]
: Output:
: [9 15] [1 7 11 29]

g*v2010-12-12 08:12

11 楼

出这个题的人是诚心不想让你过。可以直接开骂。

i*e2010-12-12 08:12

12 楼

第一题，因为都是正整数，感觉像dp，背包问题。

r*g2010-12-12 08:12

13 楼

第一题，貌似很难。
第二题，对sum存hashtable，key为sum，value为不同的两个数。

h*n2010-12-12 08:12

14 楼

先算平均值此题是12
然后除以平均值，根据余数进行分组，如果A1代表余数1的话, A2代表余数2的话......
.:
A1=[1]
A7=[7]
A3=[15]
A5=[29]
A11=[11]
A9= [9]
几个组余数加起来是平均值话,如果这些组不是空的,给其配对就找到了. 比如A1和A11
加起来是12, [1,11] 是一组解, A3和A9, 加起来也是12, [15,9]是一组解,A7和A5加起
来是12, [7,29]是一组解
最后就变成把余数组成的新array[A1,A7,A3,A5,A11,A9]中找余数加起来等于平均值的
组合存不存在。

c*w2010-12-12 08:12

15 楼

错的一塌糊涂
原数组的平均值必然是整数？非整数的话你求什么余数？

..

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

: 先算平均值此题是12
: 然后除以平均值，根据余数进行分组，如果A1代表余数1的话, A2代表余数2的话......
: .:
: A1=[1]
: A7=[7]
: A3=[15]
: A5=[29]
: A11=[11]
: A9= [9]
: 几个组余数加起来是平均值话,如果这些组不是空的,给其配对就找到了. 比如A1和A11

T*u2010-12-12 08:12

16 楼

不一定是余数，但是他的思路是对的。

【在 c******w 的大作中提到】

: 错的一塌糊涂
: 原数组的平均值必然是整数？非整数的话你求什么余数？
:
: ..

s*92010-12-12 08:12

17 楼

第一题，先求平均数，每个元素减去平均数得到新数列，然后在其中找元素之和等于0
的子序列。

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

h*n2010-12-12 08:12

18 楼

题目要求找最短的，另外有多个最短的，找字典序最靠前的

0

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

: 第一题，先求平均数，每个元素减去平均数得到新数列，然后在其中找元素之和等于0
: 的子序列。

s*92010-12-12 08:12

19 楼

减去均值后的数组排序，然后求 1 sum, 2 sum, ..., k sum，其中 k = (数组 size
+ 1) / 2，时间复杂度也太高了，似乎不可行。

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

: 题目要求找最短的，另外有多个最短的，找字典序最靠前的
:
: 0

r*g2010-12-12 08:12

20 楼

第一题其实是写一个函数
possible(int index, int sum, int sz)
从index开始，是否存在sz的subset，和为sum。由于sz只可能是从1到N，对每个sz，用
上面函数计算对应的sum是否存在。
假设总和为N
(SUM-sum)/(N-sz)=sum/sz，所以如果sz一定，那么sum也就一定。
btw: 下面程序是抄的
bool possible(int index, int sum, int sz) {
if (sz == 0) return (sum == 0);
if (index >= total_size) return false;
if (dp[index][sum][sz] == false) return false;
if (sum >= original[index]) {
res.push_back(original[index]);
if (possible(index + 1, sum - original[index], sz - 1))
return true;
res.pop_back();
}

if (possible(index + 1, sum, sz))
return true;
return dp[index][sum][sz] = false;
}

g*v2010-12-12 08:12

21 楼

第一题挺难的。
suppose the array has n elements with an average "avg". then we divide the
array into two subarrays.
Suppose the first subarray has n1 elements with average "avg1" and 2nd
subarray has n2 elements with average "avg2".
we can have equations:
n1*avg1 + n2 * avg2 = n*avg
n1+n2=n
since we are looking for two subarrays with same average, we have :
avg1 = avg2
so we finally have :
(n1+n2)*avg1 = n*avg => n*avg1 = n*avg => avg1 = avg
结论：　数组的平均数就是要找的ｓｕｂａｒｒａｙ的平均数
所以现在的问题就变成了怎么找到subset whose average is the original array's
average.
有２个解决办法：
１：　类似ｃｏｍｂｉｎａｔｉｏｎ　ｓｕｍ，　递归解
２：　可以ＤＰ，类似ｃｏｉｎ　ｃｈａｎｇｅ，但这个解法直接给出了存在不存在，
没有打印出ｓｕｂｓｅｔ，所以这个解法的难点在于怎么找到ｓｕｂｓｅｔ，自己上网
找找吧。

A*g2010-12-12 08:12

22 楼

大家在忙着解题，有没有想到，如果是面试时，只给半个小时，从完全没见过这个题，
到给出起码可以通过的较佳答案（先退一步不要最佳答案），这有多少人可以通过？

h*n2010-12-12 08:12

23 楼

我觉得leetcode做熟的人应该不难，前面有人提到combination sum我看了一下确实是
combination sum的变形。但像我们这样没做过leetcode的,确实很难。奇怪的是
leetcode上combination sum标的难度竟是medium。

c*n2010-12-12 08:12

24 楼

0
我觉得你这方法不错啊
减去平均数后，找出新序列的subset sum = 0
有现成的DP算法求subset sum，可以找出所有的subsets来
然后计算每个subset的长度，找出最短的来就行了

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

: 第一题，先求平均数，每个元素减去平均数得到新数列，然后在其中找元素之和等于0
: 的子序列。

t*d2010-12-12 08:12

25 楼

第一题是np问题吧？

g*d2010-12-12 08:12

26 楼

第一题有点意思!
前面也分析了, 先排序, 然后我们要找的subset sum S1 = S*L1/L, 而如果S/L总平均
数可能不是整数, 那么需要检查一下S*L1%L是否为0, 是的话才能继续做, 进化版的
CombinationSum3 (L1, S*L1/L)
可以限制L1<=L/2. 如果到L/2还没找到就算失败.
由于已经排过序了, 那么找到的第一个组合就是长度最短,且topological最前的答案.
(所以也不用费神排除重复答案了)
原题链接: https://leetcode.com/problems/combination-sum-iii/
DFS+backtracking
感觉可以加进Leetcode成CombinationSum4, 难度的话算Hard里的中档题
PS: 刚开始找工作, 求各位前辈内推...CS fresh grad, 目标SDE, 会点ML

g*d2010-12-12 08:12

27 楼

第二题由于没排序, 那就用个unordered_map> map
map存的是值->idx的映射, 由于一个可能值对应多个idx, 所以用个set
然后就开始DFS+backtracking. 由于题目确定了lexicographically的顺序
所以先确定A, B, C, (然后删掉对应的idx, 不删也行) 再进map查询D=A-C+B (注意
overflow), 有的话就检查D的idx是否符合条件
总的O(n^3)时间, O(n)空间
应该有更好的解法, 望指教

S*t2010-12-12 08:12

28 楼

我贴一个第一题能通过的代码吧：
vector bestA;
int bestLen;
void search(int idx, int sum, int len, vector>>& f,
vector& ret, vector& A) {
//cout << idx << " " << sum << " " << len << endl;
if (idx == 0) {
int lenA = bestA.size();
vector v = ret;
/*
for (int i = 0; i < v.size(); i++)
cout << v[i] << " ";
cout << endl;
*/
if (v.size() < lenA || lenA == 0) {
bestA = v;
return;
}
bool flag = false;
for (int i = 0; i < v.size(); i++) {
if (v[i] < bestA[i]) {
flag = true;
break;
}
if (v[i] > bestA[i]) {
flag = false;
break;
}
}
if (flag) {
bestA = v;
return;
}
}
else {
if (sum >= A[idx - 1] && len - 1 >= 0 && f[idx - 1][sum - A[idx - 1]
][len - 1]
&& (bestA.size() == 0 || A[idx - 1] <= bestA[ret.size()])) {
ret.push_back(A[idx - 1]);
search(idx - 1, sum - A[idx - 1], len - 1, f, ret, A);
ret.pop_back();
}
if (f[idx - 1][sum][len]) {
search(idx - 1, sum, len, f, ret, A);
}
}
}
vector > Solution::avgset(vector &A) {
sort(A.begin(), A.end(), greater());
bestA.clear();
int n = A.size(), sum = 0;
for (int i = 0; i < n; i++)
sum += A[i];
vector>> f(n + 1, vector>(sum + 1,
vector(n + 1)));
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= sum; j++) {
for (int k = 0; k <= n; k++)
f[i][j][k] = false;
}
}
f[0][0][0] = true;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= sum; j++) {
for (int k = 0; k <= i; k++) {
if (f[i][j][k]) {
f[i + 1][j][k] = true;
f[i + 1][j + A[i]][k + 1] = true;
}
}
}
}
bestLen = INT_MAX;
for (int lenA = 1; lenA < n; lenA++) {
for (int sumA = 0; sumA <= sum; sumA++) {
if (f[n][sumA][lenA]) {
int avg1 = sumA / lenA;
int avg2 = (sum - sumA) / (n - lenA);
long long tmp1 = (long long)sumA * (n - lenA);
long long tmp2 = (long long)(sum - sumA) * lenA;
if (tmp1 == tmp2 && lenA < bestLen) {
//cout << sumA << " " << lenA << endl;
bestLen = lenA;
vector ret;
search(n, sumA, lenA, f, ret, A);
}
}
}
}
vector> ret;
if (bestLen == INT_MAX)
return ret;
ret.push_back(bestA);
vector bestB;
int pA = 0;
sort(A.begin(), A.end());
for (int i = 0; i < n; i++) {
if (A[i] != bestA[pA]) bestB.push_back(A[i]);
else pA++;
}
sort(bestB.begin(), bestB.end());
ret.push_back(bestB);
return ret;
}

a*d2010-12-12 08:12

29 楼

第一题的java答案抄了一个，运行通过的。
https://github.com/nagajyothi/InterviewBit/blob/master/DynamicProgramming/
AvgSet.java
各路大神看看还有没有更优解。
// Sum_of_Set1 / size_of_set1 = total_sum / total_size, and so, Sum_of_Set1
= size_of_set1 * total_sum / total_size.
// Now we can just iterate on size_of_set1, and we would know the required
Sum_of_Set1.
static List res = new ArrayList();
static boolean[][][] dp;
public static List> partitionAverage(int[] num) {
List> result = new ArrayList>();
if(num == null || num.length == 0)
return result;
int totalSize = num.length;
int totalSum = 0;
for(int i = 0; i < totalSize; i++)
totalSum += num[i];
dp = new boolean[totalSize][totalSum + 1][totalSize];
for(int i =0; i < totalSize; i++)
for(int j = 0; j < totalSum + 1; j++)
for(int k =0; k < totalSize; k++)
dp[i][j][k] = true;
// To minimize size_of_set1, search for the first possible size_of_
set1.
for(int i = 1; i < totalSize; i++){
if((totalSum * i) % totalSize != 0) continue;
int sumOfSet1 = i * totalSum / totalSize;
if(isPossible(num, 0, sumOfSet1, i)){
int ptr1 = 0;
int ptr2 = 0;
List res1 = new ArrayList(res);
List res2 = new ArrayList();
while(ptr1 < totalSize || ptr2 < res.size()){
if(ptr2 < res.size() && res.get(ptr2) == num[ptr1]){
ptr1++;
ptr2++;
continue;
}
res2.add(num[ptr1]);
ptr1++;
}
result.add(res1);
result.add(res2);
return result;
}
}
return result;
}

public static boolean isPossible(int[] num, int index, int sum, int sz){
if(sz == 0) return sum == 0;
if(index >= num.length || !dp[index][sum][sz]) return false;
if(num[index]<=sum){
res.add(num[index]);
if(isPossible(num, index + 1, sum - num[index], sz - 1))
return true;
res.remove(res.size() - 1);
}
if(isPossible(num, index + 1, sum, sz)) return true;
return false;
}