由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 求教一道DP的面试题,minimum adjustment cost
相关主题
这题怎么做?Given an array of N integers from range [0, N] and one is missing. Find the missing number.
请教一道算法题问道题,谁给个效率高点的解法
问一道面试题目a[i] + b[j] = c[k] 的题有靠谱的答案不?
Google电话面试题目菜鸟问个two sum的变型题
[合集] Google电话面试题目amazon 电面问题 求解答, 在线等
一道老题请教个面试题
careercup上这道题我竟然没看懂Minimum number of moves to make an integer array balance
算法题:两列找共同元素有O(n)的算法吗?问个最近面试里的题目
相关话题的讨论汇总
话题: int话题: cost话题: tempcost话题: currentmincost话题: v1
1 (共1页)
y*****e
发帖数: 712
1
我忘了是F家还是G家的了,当时没仔细看大家的讨论,这两天做lintcode,竟然和这题
重逢了,看了半天一点思路也没有,不知有没有大神愿意指点一下,动态方程应该怎么
写?
题目:
Given an integer array, adjust each integers so that the difference of every
adjcent integers are not greater than a given number target.
If the array before adjustment is A, the array after adjustment is B, you
should minimize the sum of |A[i]-B[i]|
例子
Given [1,4,2,3] and target=1, one of the solutions is [2,3,2,3], the
adjustment cost is 2 and it's minimal. Return 2.
我要是面试碰到这题,直接傻眼。。。。
l*******0
发帖数: 95
2
My solution should be correct. It prints the followings when you run the
code
min cost = 2
B = 1 2 2 3
public class MinAdjustment {
public int[] adjust(int[] A, int target) {
// state: cost[i][v] - the total cost of changing A[i] to v, where v
belongs to [0, max]
// init: cost[0][v] = |A[0] - v|;
// function: cost[i][v] = min(cost[i-1][v - target ... v + target])
+ |A[i] - v|
// where v, v - target and v + target all belong to [0,
max]
// result: min(cost[A.length - 1][v])
int[] B = new int[A.length];
int max = Integer.MIN_VALUE;
for(int i = 0; i < A.length; i ++)
if(A[i] > max) max = A[i];
int range = max + 1;
int[][] cost = new int[A.length][range];
for(int i = 0; i < range; i ++)
cost[0][i] = Math.abs(A[0] - i);
for(int i = 1; i < A.length; i ++) {
int currentMinCost = Integer.MAX_VALUE;
for(int v = 0; v < range; v ++) {
// calculate the min cost for changing A[i] to v
cost[i][v] = Integer.MAX_VALUE;
for(int diff = -1 * target; diff <= target; diff ++) {
int v1 = v + diff;
if(v1 < 0) continue;
if(v1 > max) break;
int tempCost = cost[i-1][v1] + Math.abs(A[i] - v);
if(tempCost < cost[i][v]) cost[i][v] = tempCost;
if(tempCost < currentMinCost) {
currentMinCost = tempCost;
B[i-1] = v1;
}
}
}
}
// resolve the value of B[A.length - 1], i.e. the last element of B
int lastMinCost = cost[A.length - 1] [0];
B[A.length - 1] = 0;
for(int v = 1; v < range; v ++) {
if(cost[A.length - 1][v] < lastMinCost) {
lastMinCost = cost[A.length - 1][v];
B[A.length - 1] = v;
}
}
System.out.println("min cost = " + lastMinCost);
return B;
}
public static void main(String[] args) {
MinAdjustment sol = new MinAdjustment();
int[] A = {1,4,2,3};
int[] B = sol.adjust(A, 1);
System.out.print("B = ");
for(int b : B) System.out.print(b + "\t");
}
}
l*******0
发帖数: 95
3
我上面的solution有个假设: A中元素的取值范围是非负的,也就是大于或者等于0. 如
果感兴趣,你可以试着自己改一下程序,让它能够handle包括负数的情况。
另外,这个题现场不会做也没啥,的确要花些时间想想。
y*****e
发帖数: 712
4
非常感谢啊!我凝视了快半个小时终于明白了,幸亏我没放弃。。。这答案写的真好!
我放去OJ,全部test case都通过了 :)

v
)

【在 l*******0 的大作中提到】
: My solution should be correct. It prints the followings when you run the
: code
: min cost = 2
: B = 1 2 2 3
: public class MinAdjustment {
: public int[] adjust(int[] A, int target) {
: // state: cost[i][v] - the total cost of changing A[i] to v, where v
: belongs to [0, max]
: // init: cost[0][v] = |A[0] - v|;
: // function: cost[i][v] = min(cost[i-1][v - target ... v + target])

l*******0
发帖数: 95
5
Cheers :-)
k*******a
发帖数: 433
6
You can assume each number in the array is a positive integer and not
greater than 100
用DP做,充分利用1-100这个条件
n***t
发帖数: 76
7
Hi Luckier, I have a question.
why range = max+1? should it be range = max+target?

v
v
)

【在 l*******0 的大作中提到】
: My solution should be correct. It prints the followings when you run the
: code
: min cost = 2
: B = 1 2 2 3
: public class MinAdjustment {
: public int[] adjust(int[] A, int target) {
: // state: cost[i][v] - the total cost of changing A[i] to v, where v
: belongs to [0, max]
: // init: cost[0][v] = |A[0] - v|;
: // function: cost[i][v] = min(cost[i-1][v - target ... v + target])

z*********e
发帖数: 10149
8
这个问题可不可以这么做?
先算出mean,然后adjusted array的取值范围是
[mean - target/2, mean + target/2]
然后对于每一个Array里面的元素a,对应的adjusted array的元素的取值为离最近的那
个值?
z*********e
发帖数: 10149
9
这个想法完全不对,晕

【在 z*********e 的大作中提到】
: 这个问题可不可以这么做?
: 先算出mean,然后adjusted array的取值范围是
: [mean - target/2, mean + target/2]
: 然后对于每一个Array里面的元素a,对应的adjusted array的元素的取值为离最近的那
: 个值?

M*********y
发帖数: 7
10
也觉得range = max+target?
相关主题
一道老题Given an array of N integers from range [0, N] and one is missing. Find the missing number.
careercup上这道题我竟然没看懂问道题,谁给个效率高点的解法
算法题:两列找共同元素有O(n)的算法吗?a[i] + b[j] = c[k] 的题有靠谱的答案不?
p****a
发帖数: 447
11
似乎是max+target合理

【在 M*********y 的大作中提到】
: 也觉得range = max+target?
N*D
发帖数: 3641
12
好,今天虐印就这道题了。
y*****e
发帖数: 712
13
给你点赞

【在 N*D 的大作中提到】
: 好,今天虐印就这道题了。
s********x
发帖数: 81
14
which oj 哈?
m*****k
发帖数: 731
15
can be simplified:

//NEW LINE
int currentMinCost = 0;
for(int i = 1; i < A.length; i ++) {
currentMinCost = Integer.MAX_VALUE;
for(int v = 0; v < range; v ++) {
// calculate the min cost for changing A[i] to v
cost[i][v] = Integer.MAX_VALUE;
for(int diff = -1 * target; diff <= target; diff ++) {
int v1 = v + diff;
if(v1 < 0) continue;
if(v1 > max) break;
int tempCost = cost[i-1][v1] + Math.abs(A[i] - v);
if(tempCost < cost[i][v]) cost[i][v] = tempCost;
if(tempCost < currentMinCost) {
currentMinCost = tempCost;
B[i-1] = v1;

//NEW LINE
B[i] = v;
}
}
}
}

System.out.println("min cost = " + currentMinCost);
return B;

v
)

【在 l*******0 的大作中提到】
: My solution should be correct. It prints the followings when you run the
: code
: min cost = 2
: B = 1 2 2 3
: public class MinAdjustment {
: public int[] adjust(int[] A, int target) {
: // state: cost[i][v] - the total cost of changing A[i] to v, where v
: belongs to [0, max]
: // init: cost[0][v] = |A[0] - v|;
: // function: cost[i][v] = min(cost[i-1][v - target ... v + target])

m*****k
发帖数: 731
16
v should be within [min,max] of the array 吧

【在 p****a 的大作中提到】
: 似乎是max+target合理
l*****n
发帖数: 246
17
给大牛点赞

v
)

【在 l*******0 的大作中提到】
: My solution should be correct. It prints the followings when you run the
: code
: min cost = 2
: B = 1 2 2 3
: public class MinAdjustment {
: public int[] adjust(int[] A, int target) {
: // state: cost[i][v] - the total cost of changing A[i] to v, where v
: belongs to [0, max]
: // init: cost[0][v] = |A[0] - v|;
: // function: cost[i][v] = min(cost[i-1][v - target ... v + target])

m*****n
发帖数: 2152
18
这个答案好像不够优化,遇到烙印有被搞死的危险。
比如,min_value和max_value相差极大,
[INT_MIN, INT_MAX, 0,0,0,0,0....0] 10^9个0,range = 2,这个方法内存就爆掉了。
如果先计算中位数medium,然后,把window 调成 (medium-range, medium+range),再
做DP。就会好很多了。

v
)

【在 l*******0 的大作中提到】
: My solution should be correct. It prints the followings when you run the
: code
: min cost = 2
: B = 1 2 2 3
: public class MinAdjustment {
: public int[] adjust(int[] A, int target) {
: // state: cost[i][v] - the total cost of changing A[i] to v, where v
: belongs to [0, max]
: // init: cost[0][v] = |A[0] - v|;
: // function: cost[i][v] = min(cost[i-1][v - target ... v + target])

p******e
发帖数: 14
19
mark
1 (共1页)
相关主题
问个最近面试里的题目[合集] Google电话面试题目
求这道题的O(N)解 (转载)一道老题
求助:2倍年龄问题的通项解析式问题careercup上这道题我竟然没看懂
再问一道题算法题:两列找共同元素有O(n)的算法吗?
这题怎么做?Given an array of N integers from range [0, N] and one is missing. Find the missing number.
请教一道算法题问道题,谁给个效率高点的解法
问一道面试题目a[i] + b[j] = c[k] 的题有靠谱的答案不?
Google电话面试题目菜鸟问个two sum的变型题
相关话题的讨论汇总
话题: int话题: cost话题: tempcost话题: currentmincost话题: v1