avatar
问一道面试题目# JobHunting - 待字闺中
l*2
1
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]|
You can assume each number in the array is a positive integer and not
greater than 100
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.
avatar
r*7
2
这个不就动态规划么,O(n)的复杂度

every

【在 l******2 的大作中提到】
: 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]|
: You can assume each number in the array is a positive integer and not
: greater than 100
: 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.

avatar
i*e
3
element value需要在合理范围内,否则没法dp。
楼主应该漏了这点。
avatar
m*l
4
"You can assume each number in the array is a positive integer and not
greater than 100 "
所以可以DP.
另一个方法是. 表明这个问题可以写成min-cost flow. 然后这个图很特别, 是series-
parallel graph.
然后表明用Booth&Tarjan的算法O(n log n)的时间即可.
avatar
t*5
5
能具体说说算法么,谢谢

【在 r****7 的大作中提到】
: 这个不就动态规划么,O(n)的复杂度
:
: every

avatar
b*e
6
int f[n][100]
第一维是数组里的数,第二维是那个数的取值,f[i][j]是第i个数取j(0的cost
转移方程很恶心如果k很大的话
如果k==1的话
f[i][j]=min(f[i-1][j-1],f[i-1][j],f[i-1][j+1])+ |A[i]-j|
最后输出f[N-1][]里最小的元素即可

【在 t******5 的大作中提到】
: 能具体说说算法么,谢谢
avatar
b*e
7
直接求max(A)和min(A)就好了吧

【在 i*********e 的大作中提到】
: element value需要在合理范围内,否则没法dp。
: 楼主应该漏了这点。

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。