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 | |
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 | |
|
|
p****a
发帖数: 447 | 11 似乎是max+target合理
【在 M*********y 的大作中提到】
: 也觉得range = max+target?
|
N*D
发帖数: 3641 | |
y*****e
发帖数: 712 | 13 给你点赞
【在 N*D 的大作中提到】
: 好，今天虐印就这道题了。
|
s********x
发帖数: 81 | |
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 | |
