m******a
发帖数: 84 | 1 Give an integer array, adjust each integers so that the difference of every
adjacent 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 abs(A[i] - B[i])
You can assume each number in the array is a positive integer and not
greater than 100
Example:
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.
题目如上，请问大牛们有没有好的想法？谢谢！ | x********k
发帖数: 256 | | t*******y
发帖数: 3 | | m*****k
发帖数: 731 | 4 >>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.
结果为啥不是[1,2,2,3] ， adjust cost = 1 ? | b******g
发帖数: 3616 | 5 4>2所以adjust以后也得是这个关系？
mark，回头想想
【在 m*****k 的大作中提到】
: >>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.
: 结果为啥不是[1,2,2,3] ， adjust cost = 1 ?
| m******a
发帖数: 84 | 6 这个cost是2， 第二个元素由4变成了2了
【在 m*****k 的大作中提到】
: >>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.
: 结果为啥不是[1,2,2,3] ， adjust cost = 1 ?
| m******a
发帖数: 84 | 7 能详细点么？
【在 t*******y 的大作中提到】
: 动态规划
| m******a
发帖数: 84 | 8 这个没有规定adjust后还是原来的大小关系吧
【在 b******g 的大作中提到】
: 4>2所以adjust以后也得是这个关系？
: mark，回头想想
| r****7
发帖数: 2282 | 9 复杂度太高了
应该要用到正数和小于100的特点，不过目前还没想到啥好办法
【在 t*******y 的大作中提到】
: 动态规划
| i*****o
发帖数: 105 | | | | g***s
发帖数: 3811 | 11 复杂度也就100N，
100的特点就是target就算是无穷大也和100一样。
★ 发自iPhone App: ChineseWeb 8.6
【在 r****7 的大作中提到】
: 复杂度太高了
: 应该要用到正数和小于100的特点，不过目前还没想到啥好办法
| r****7
发帖数: 2282 | 12 恩，后来睡觉的时候想了想，100就是为了限制一个constant time的，否则是个NP
problem
【在 g***s 的大作中提到】
: 复杂度也就100N，
: 100的特点就是target就算是无穷大也和100一样。
:
: ★ 发自iPhone App: ChineseWeb 8.6
| m******a
发帖数: 84 | 13 动态规划是怎么做得呢？能详细一点么？
【在 r****7 的大作中提到】
: 恩，后来睡觉的时候想了想，100就是为了限制一个constant time的，否则是个NP
: problem
| s***c
发帖数: 639 | 14 dfs+pruning,你看成不成。数大小都在100以内，复杂度就能估计，可还是太狠
every
minimize
【在 m******a 的大作中提到】
: Give an integer array, adjust each integers so that the difference of every
: adjacent 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 abs(A[i] - B[i])
: You can assume each number in the array is a positive integer and not
: greater than 100
: Example:
: 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.
: 题目如上，请问大牛们有没有好的想法？谢谢！
| x*******9
发帖数: 138 | 15 略暴力，Lintcode上的题。（没看错，是Lintcode，不是Leetcode）
class Solution {
public:
/**
* @param A: An integer array.
* @param target: An integer.
*/
int MinAdjustmentCost(vector A, int target) {
if (A.empty()) {
return 0;
}
int n = A.size();
int ptr = 0;
memset(dp, 0, sizeof(dp));
for (int i = 0; i < n; i++) {
int cur = A[i];
int next = ptr ^ 1;
memset(dp[next], INF, sizeof(dp[next]));
for (int j = 1; j <= 100; j++) {
int diff = abs(cur - j);
int range_l = max(1, j - target);
int range_r = min(100, j + target);
for (int k = range_l; k <= range_r; k++) {
dp[next][j] = min(dp[next][j], dp[ptr][k] + diff);
}
}
ptr ^= 1;
}
int ans = INF;
for (int i = 1; i <= SIZE; i++) {
ans = min(ans, dp[ptr][i]);
}
return ans;
}
private:
static const int SIZE = 100;
static const int INF = 0x3f3f3f3f;
int dp[2][SIZE + 5];
}; | b********r
发帖数: 620 | 16 my 2 cents for DP, define min as cost of between i and j, inclusive.
min(i,j)=min(i,k)+min(k,j), i
i am guessing probably that's the reason why the array element has a range
limit.
by the way the solution is not unique, e.g, both 2,3,2,3 and 1,2,2,3 work | d*******8
发帖数: 23 | 17 Using Dynamic Programming.
The time complexity is O(maxDiff * N), where N is array size and maxDiff is
the maximum diff allowed between adjacent elements
My codes here:
http://ideone.com/btd3WU |
|
