o*********g
发帖数: 10 | 1 G:
一个队列，每个元素自身有一个数值，并且有一个计数，存储着排在这个元素前面有几
个比他的数值大的元素，比如[(3,2),(2,2),(4,1),(6,0)], 如果现在这个队列突然被
随机打乱作为输入，比如[(2,2),(6,0),(4,1),(3,2)],请据此恢复输出原来队列。
F:
给一个数组，其中相邻元素不能同时选，返回求和的最大值。 | f*****e
发帖数: 2992 | 2 第一题排序，然后从小到大确定位置。
第二题DP。
【在 o*********g 的大作中提到】
: G:
: 一个队列，每个元素自身有一个数值，并且有一个计数，存储着排在这个元素前面有几
: 个比他的数值大的元素，比如[(3,2),(2,2),(4,1),(6,0)], 如果现在这个队列突然被
: 随机打乱作为输入，比如[(2,2),(6,0),(4,1),(3,2)],请据此恢复输出原来队列。
: F:
: 给一个数组，其中相邻元素不能同时选，返回求和的最大值。
| s**x
发帖数: 7506 | 3 应该是从大到小吧？
【在 f*****e 的大作中提到】
: 第一题排序，然后从小到大确定位置。
: 第二题DP。
| c*********a
发帖数: 8 | 4 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 的大作中提到】
: G:
: 一个队列，每个元素自身有一个数值，并且有一个计数，存储着排在这个元素前面有几
: 个比他的数值大的元素，比如[(3,2),(2,2),(4,1),(6,0)], 如果现在这个队列突然被
: 随机打乱作为输入，比如[(2,2),(6,0),(4,1),(3,2)],请据此恢复输出原来队列。
: F:
: 给一个数组，其中相邻元素不能同时选，返回求和的最大值。
| c*********a
发帖数: 8 | 5 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 的大作中提到】
: G:
: 一个队列，每个元素自身有一个数值，并且有一个计数，存储着排在这个元素前面有几
: 个比他的数值大的元素，比如[(3,2),(2,2),(4,1),(6,0)], 如果现在这个队列突然被
: 随机打乱作为输入，比如[(2,2),(6,0),(4,1),(3,2)],请据此恢复输出原来队列。
: F:
: 给一个数组，其中相邻元素不能同时选，返回求和的最大值。
| A*********c
发帖数: 430 | 6 赞。
【在 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*****c
发帖数: 1103 | | P**********0
发帖数: 412 | 8 第一题没看懂，能解释一下“并且有一个计数，存储着排在这个元素前面有几个比他的
数值大的元素，”
为什么是（3，2）和（2，2） ？ | r*c
发帖数: 167 | 9 第二题为什么一定要用DP？求出最大的和第三大的然后相加，不就出来了吗？假设存在
任何其它的解，都可以用反证法证明不会比最大项和第三大项之和更大。
【在 f*****e 的大作中提到】
: 第一题排序，然后从小到大确定位置。
: 第二题DP。
| d*****1
发帖数: 263 | 10
不止2个元素相加。
【在 r*c 的大作中提到】
: 第二题为什么一定要用DP？求出最大的和第三大的然后相加，不就出来了吗？假设存在
: 任何其它的解，都可以用反证法证明不会比最大项和第三大项之和更大。
| A*********c
发帖数: 430 | 11 反着看。(6,0)是第一个。
【在 P**********0 的大作中提到】
: 第一题没看懂，能解释一下“并且有一个计数，存储着排在这个元素前面有几个比他的
: 数值大的元素，”
: 为什么是（3，2）和（2，2） ？
| d*****1
发帖数: 263 | 12
思路讲讲？
没想出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****m
发帖数: 177 | 13 好像有问题，试试 (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 的大作中提到】
: 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
|
|
