两道题，祝大家新年快乐！ - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

两道题，祝大家新年快乐！

两道题，祝大家新年快乐！# JobHunting - 待字闺中

s*n2013-12-31 08:12

1 楼

我觉得有点逻辑问题
那几条守则只有在彼此配合的情况下才有用，能给婚姻加分；如果彼此不配合的话做到
也没啥帮助啊~
实在没教会咱们怎么把婚姻留住啊。
能做到那几条准则又婚姻破裂的也有。我就见过妻子贤良淑德，男方也没有“严重人品
问题，比如嗜嫖嗜
赌，虐待老人孩子，或有精神病倾向，比如狂摔东西，要挟杀人”，最后就是走不到一
起，那咋办咧？

o*g2013-12-31 08:12

2 楼

G:
一个队列，每个元素自身有一个数值，并且有一个计数，存储着排在这个元素前面有几
个比他的数值大的元素，比如[(3,2),(2,2),(4,1),(6,0)], 如果现在这个队列突然被
随机打乱作为输入，比如[(2,2),(6,0),(4,1),(3,2)],请据此恢复输出原来队列。
F:
给一个数组，其中相邻元素不能同时选，返回求和的最大值。

f*e2013-12-31 08:12

3 楼

第一题排序，然后从小到大确定位置。
第二题DP。

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

: G:
: 一个队列，每个元素自身有一个数值，并且有一个计数，存储着排在这个元素前面有几
: 个比他的数值大的元素，比如[(3,2),(2,2),(4,1),(6,0)], 如果现在这个队列突然被
: 随机打乱作为输入，比如[(2,2),(6,0),(4,1),(3,2)],请据此恢复输出原来队列。
: F:
: 给一个数组，其中相邻元素不能同时选，返回求和的最大值。

s*x2013-12-31 08:12

4 楼

应该是从大到小吧？

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

: 第一题排序，然后从小到大确定位置。
: 第二题DP。

c*a2013-12-31 08:12

5 楼

Code for the F question:
public int getMaxSum(int[] A) {
if ( A == null || A.length == 0 ) { return 0;}
if ( A.length == 1 ) { return A[0];}
if ( A.length == 2 ) { return Math.max(A[0], A[1]);}

int[] S = new int[A.length];
S[0] = A[0];
S[1] = Math.max(A[0], A[1]);

for ( int i = 2; i < A.length; i++) {
int t = Math.max(A[i], S[i-2] + A[i]);
S[i] = Math.max(t, S[i-1]);
}

return S[S.length - 1];
}

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

c*a2013-12-31 08:12

6 楼

Code for G question:
public class Solution {
public static class Pair implements Comparable{
int val;
int count;
public Pair(int val, int count) {
this.val = val;
this.count = count;
}
@Override
public int hashCode() {
return val + count * 3;
}
@Override
public boolean equals(Object obj) {
if ( obj == null ) { return false;}
if ( obj.getClass() != this.getClass()) { return false;}
if ( obj == this ) { return true;}
Pair other = (Pair) obj;
return this.val == other.val && this.count == other.count;
}
@Override
public int compareTo(Pair other) {
if ( other == null ) { return 1;}
if ( other == this ) { return 0;}
if ( this.val < other.val ) { return -1;}
if ( this.val > other.val ) { return 1;}
if ( this.count < other.count ) { return -1;}
if ( this.count > other.count ) { return 1;}
return 0;
}
}
/*
* 一个队列，每个元素自身有一个数值，并且有一个计数，存储着排在这个元素
前面有几
个比他的数值大的元素，比如[(3,2),(2,2),(4,1),(6,0)], 如果现在这个队列突然被
随机打乱作为输入，比如[(2,2),(6,0),(4,1),(3,2)],请据此恢复输出原来队列
*/
public Pair[] sortPair(Pair[] A) {
if ( A == null || A.length < 2 ) { return A;}

Arrays.sort(A);

Pair[] result = new Pair[A.length];
boolean[] existed = new boolean[A.length];
for (int i = 0; i < A.length; i++) {
existed[i] = false;
}

int prevIndex = A[0].count;
result[prevIndex] = A[0];
existed[prevIndex] = true;

for (int i = 1; i < A.length; i++) {
Pair prev = result[prevIndex];
int pos = 0;
if ( A[i].count >= prev.count ) {
pos = assignIncrease(existed, prevIndex + A[i].count - prev.
count + 1);
} else {
pos = assignDecrease(existed, prevIndex - ( prev.count - A[i
].count));
}
result[pos] = A[i];
existed[pos] = true;
prevIndex = pos;
}

return result;
}

private int assignIncrease(boolean[] existed, int start ) {
while ( existed[start] ) {
start++;
}
return start;
}

private int assignDecrease(boolean[] existed, int start ) {
while ( existed[start] ) {
start--;
}
return start;
}
}

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

A*c2013-12-31 08:12

7 楼

赞。

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

: Code for the F question:
: public int getMaxSum(int[] A) {
: if ( A == null || A.length == 0 ) { return 0;}
: if ( A.length == 1 ) { return A[0];}
: if ( A.length == 2 ) { return Math.max(A[0], A[1]);}
:
: int[] S = new int[A.length];
: S[0] = A[0];
: S[1] = Math.max(A[0], A[1]);
:

b*c2013-12-31 08:12

8 楼

第一题不会。。。

P*02013-12-31 08:12

9 楼

第一题没看懂，能解释一下“并且有一个计数，存储着排在这个元素前面有几个比他的
数值大的元素，”
为什么是（3，2）和（2，2）？

r*c2013-12-31 08:12

10 楼

第二题为什么一定要用DP？求出最大的和第三大的然后相加，不就出来了吗？假设存在
任何其它的解，都可以用反证法证明不会比最大项和第三大项之和更大。

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

: 第一题排序，然后从小到大确定位置。
: 第二题DP。

d*12013-12-31 08:12

11 楼

不止2个元素相加。

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

: 第二题为什么一定要用DP？求出最大的和第三大的然后相加，不就出来了吗？假设存在
: 任何其它的解，都可以用反证法证明不会比最大项和第三大项之和更大。

A*c2013-12-31 08:12

12 楼

反着看。(6,0)是第一个。

【在 P**********0 的大作中提到】

: 第一题没看懂，能解释一下“并且有一个计数，存储着排在这个元素前面有几个比他的
: 数值大的元素，”
: 为什么是（3，2）和（2，2）？

d*12013-12-31 08:12

13 楼

思路讲讲？
没想出O(n)的解法来啊？（n是输入的pair数目）因为总要对相同的count的pair进行
排序的呀？？？？

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

: Code for G question:
: public class Solution {
: public static class Pair implements Comparable{
: int val;
: int count;
: public Pair(int val, int count) {
: this.val = val;
: this.count = count;
: }
: @Override

q*m2013-12-31 08:12

14 楼

好像有问题，试试 (2,0),(1,1),(4,0),(3,1)
,排序以后是 (1,1), (2,0), (3,1), (4,0),按照这个方法会先得到 (2,0),(1,1),(3,1
)然后放(4,0)的时候只能放在-1的位置上

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