弱问一道G题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

弱问一道G题

弱问一道G题# JobHunting - 待字闺中

c*t2012-10-12 07:10

1 楼

Write a program to determine whether n/2 distintinctve pairs can be formed
from given n integers where n is even and each pair's sum is divisible by
given k. Numbers cannot be repeated in the pairs, that means only you can
form total n/2 pairs.
我想到的方法
find num%k for each number in the array and sum them. If it is divisible by
K then we have n/2 pairs
被鄙视了。为什么？

h*92012-10-12 07:10

2 楼

by
充分和必要条件的区别。试试 { 3, 4, 7, 10 } & k = 3.

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

: Write a program to determine whether n/2 distintinctve pairs can be formed
: from given n integers where n is even and each pair's sum is divisible by
: given k. Numbers cannot be repeated in the pairs, that means only you can
: form total n/2 pairs.
: 我想到的方法
: find num%k for each number in the array and sum them. If it is divisible by
: K then we have n/2 pairs
: 被鄙视了。为什么？

h*92012-10-12 07:10

3 楼

public class Divisible {
public static void main(String args[]) {
int a1[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int a2[] = { 1, 2, 3, 4, 7, 10 };
System.out.println(isDivisible(a1, 5));
System.out.println(isDivisible(a2, 3));
}

public static boolean isDivisible(int a[], int k) {
assert (a != null && a.length % 2 == 0);
assert (k != 0);

int count[] = new int[k];
for(int i = 0; i < a.length; i++) {
count[a[i] % k]++;
}
if(count[0] % 2 != 0) {
return false;
}
int i = 1;
int j = k - 1;
while(i < j) {
if(count[i++] != count[j--]) {
return false;
}
}
if(i == j && count[i] % 2 != 0) {
return false;
}
return true;
}
}

g*y2012-10-12 07:10

4 楼

可以再写短一点：(更正版）
public boolean isDivisible(int[] a, int k) {
if (a==null || a.length%2==1) return false;
int[] count = new int[k];
for (int i : a) count[i%k]++;
for (int i=1; iif (count[i] != count[k-i]) return false;
}
return count[0]%2==0;
}
其他判断已经被限制，就不用测了。

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

: public class Divisible {
: public static void main(String args[]) {
: int a1[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
: int a2[] = { 1, 2, 3, 4, 7, 10 };
: System.out.println(isDivisible(a1, 5));
: System.out.println(isDivisible(a2, 3));
: }
:
: public static boolean isDivisible(int a[], int k) {
: assert (a != null && a.length % 2 == 0);

C*U2012-10-12 07:10

5 楼

我的想法是把这些数根据%k归类
然后从互余类里面取出数来

by

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

h*92012-10-12 07:10

6 楼

赞简洁，再看了一下，可以把 "return k%2==1 || count[k/2]%2==0;" 改成 "return
count[0]%2==0;"。

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

: 可以再写短一点：(更正版）
: public boolean isDivisible(int[] a, int k) {
: if (a==null || a.length%2==1) return false;
: int[] count = new int[k];
: for (int i : a) count[i%k]++;
: for (int i=1; i: if (count[i] != count[k-i]) return false;
: }
: return count[0]%2==0;
: }

g*y2012-10-12 07:10

7 楼

赞，这个更简单

★ 发自iPhone App: ChineseWeb 7.5

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

:
: 赞简洁，再看了一下，可以把 "return k%2==1 || count[k/2]%2==0;" 改成 "return
: count[0]%2==0;"。

c*t2012-10-12 07:10

8 楼

赞你们，不过好像最后的判断有个bug
我感觉应该是
return（k%2==1 && count[k/2] == count[k/2+1]) || (k%2==0 && count[0]%2==0);
不知能不能再简化。

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

: 赞，这个更简单
:
: ★ 发自iPhone App: ChineseWeb 7.5

c*t2012-10-12 07:10

9 楼

试试{ 1, 2, 2, 4}，5 ，出错

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

: 赞，这个更简单
:
: ★ 发自iPhone App: ChineseWeb 7.5

c*t2012-10-12 07:10

10 楼

明白了循环判断中间改成 i<=k/2, 最后一行用 return count[0]%2==0即可

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

: 赞你们，不过好像最后的判断有个bug
: 我感觉应该是
: return（k%2==1 && count[k/2] == count[k/2+1]) || (k%2==0 && count[0]%2==0);
: 不知能不能再简化。

g*y2012-10-12 07:10

11 楼

不需要那么多判断，不信你写unit test试试

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

: 赞你们，不过好像最后的判断有个bug
: 我感觉应该是
: return（k%2==1 && count[k/2] == count[k/2+1]) || (k%2==0 && count[0]%2==0);
: 不知能不能再简化。

e*e2012-10-12 07:10

12 楼

public static boolean isDivisible(ArrayList a, int K) {

if ( a.size() == 0 )
return true;

for ( int i = 0; i < a.size(); i++ ) {
for ( int j = i + 1; j < a.size(); j++ ) {
if ( ( a.get( i ) + a.get( j ) ) % K == 0 ) {
ArrayList c = (ArrayList)a.clone();
c.remove(a.get(i));
c.remove(a.get(j));
return isDivisible(c, K) ;
}
}
}
return false;
}

r*c2012-10-12 07:10

13 楼

this is n^2?

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

: public static boolean isDivisible(ArrayList a, int K) {
:
: if ( a.size() == 0 )
: return true;
:
: for ( int i = 0; i < a.size(); i++ ) {
: for ( int j = i + 1; j < a.size(); j++ ) {
: if ( ( a.get( i ) + a.get( j ) ) % K == 0 ) {
: ArrayList c = (ArrayList)a.clone();
: c.remove(a.get(i));

e*e2012-10-12 07:10

14 楼

not sure. maybe n!.

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

: this is n^2?

g*y2012-10-12 07:10

15 楼

你是对的，我把边界写错了。但是不能这样改，应该是 i < (k+1)/2

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

: 明白了循环判断中间改成 i<=k/2, 最后一行用 return count[0]%2==0即可

h*n2012-10-12 07:10

16 楼

the difference betwen i<=k/2, and i < (k+1)/2 is ?

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

: 你是对的，我把边界写错了。但是不能这样改，应该是 i < (k+1)/2

g*y2012-10-12 07:10

17 楼

6

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

: the difference betwen i<=k/2, and i < (k+1)/2 is ?

c*t2012-10-12 07:10

18 楼

虽说我的也没有错，因为哪怕改成 i你这个很明确。

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

: 你是对的，我把边界写错了。但是不能这样改，应该是 i < (k+1)/2

I*g2012-10-12 07:10

19 楼

二分图最大匹配吧

g*y2012-10-12 07:10

20 楼

是我想错了，按里面的循环，多计算一次没关系

★ 发自iPhone App: ChineseWeb 7.5

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

: 虽说我的也没有错，因为哪怕改成 i: 你这个很明确。

h*n2012-10-12 07:10

21 楼

...
brain short circuit of mine..

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

: 6

i*e2012-10-12 07:10

22 楼

如果可以用O(K)空间的话，counting算法的应用，可能会使逻辑看起来比较简单
int rm_k[k] = {0,...,0}
for each n in the sequence
rm_k[n%k] += 1
如果余数为0的数的个数为奇数，则至少有一个不能配对成功
if rm_k[0] % 2 == 1: return false
如果k为偶数，且余数为k/2的数的个数为奇数，，则至少有一个不能配对成功
if k % 2 == 0 && rm_k[k/2] % 2 == 1: return false
余数为i的数，必须与余数为k-i的数配对
for i from 1 to k/2
if rm_k[i] != rm_k[k-i]: return false
return true