【算法题】minimum-adjustment-cost 梦里梦外; 2022-06-04 06:48 109阅读 0赞 题目描述: Given 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 `|A[i]-B[i]|` ##### Notice ##### You can assume each number in the array is a positive integer and not greater than `100`. Have you met this question in a real interview? Yes 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`. 题目连接: http://www.lintcode.com/en/problem/minimum-adjustment-cost/ 中文描述:给一个整数数组,调整每个数的大小,使得相邻的两个数的差不大于一个给定的整数target,调整每个数的代价为调整前后的差的绝对值,求调整代价之和最小是多少。 思路: 这个是动态规划背包问题。 state: dp\[i\]\[j\] 到A\[i\]为止A\[i\]变为j的时候的min cost initalization:dp\[0\]\[j\] = abs(A\[0\] - j) function:dp\[i\]\[j\] = min(dp\[i\]\[j\], dp\[i - 1\]\[j\] + A\[i\] - j) result:min(dp\[A.size - 1\]\[j\]) 这个其实需要三层循环,第三层循环的时候用到target这个值,根据j和target确定这次的j的范围。并且取最小的那个情况。 这个题目的标准思路和状态及方程是上面这样,我的优化思路: j的取值范围是从A中的最小值到最大值的 ,所以没必要从0到100循环。也就是他提示的假设条件是不需要的。 此时状态方程需要稍稍调整,直接贴出我的代码。 class Solution { public: /* * @param A: An integer array * @param target: An integer * @return: An integer */ int MinAdjustmentCost(vector<int> &A, int target) { int max_a = *(max_element(A.begin(), A.end())); int min_a = *(min_element(A.begin(), A.end())); vector<vector<int>> dp(A.size(), vector<int>(101, INT_MAX)); for (int i = 0; i <= max_a - min_a; i++) { dp[0][i] = abs(A[0] - (i + min_a)); } for (int i = 1; i < A.size(); i++) { for (int j = 0; j <= max_a - min_a; j++) { for (int k = max(min_a, j + min_a - target); k <= min(max_a, j + min_a + target); k++) { dp[i][j] = min(dp[i][j], dp[i - 1][k - min_a] + abs(A[i] - (j + min_a))); } } } return *(min_element(dp[A.size() - 1].begin(), dp[A.size() - 1].end())); } };
相关 算法题刷题笔记 在线题库 > [牛客华为机试题库【题号 HJ开头】(重点看)][HJ] > [牛客在线编程算法篇【题号NC开头】][NC] > [剑指offer【题号 JZ开头】 深藏阁楼爱情的钟/ 2024年03月27日 11:33/ 0 赞/ 33 阅读
相关 算法数组题 1.用最少的代码求出三个数那个数最大 <?php $a=10;$b=4;$c=22; $max=($a>$b?$a:$b)>$c?($a>$b?$a: 分手后的思念是犯贱/ 2022年08月22日 12:30/ 0 赞/ 107 阅读
相关 算法题总结 二、数据结构和算法 1.使对象可以像数组一样进行foreach循环,要求属性必须是私有。(Iterator模式的PHP5实现,写一类实现Iterator接口)( 我就是我/ 2022年06月11日 07:28/ 0 赞/ 123 阅读
相关 算法题 上学时学过的算法,青山遮不住,毕竟东流去,都忘得差不多了。。。。 题目1:使用一个数组实现一个循环队列 分析:简单来讲就是用一个数组,实现个队列的功能,可以用两个脚标来控制 我就是我/ 2022年06月10日 07:19/ 0 赞/ 122 阅读
相关 算法题分析 【题目描述】 在主城站街很久之后,小萌决定不能就这样的浪费时间虚度青春,他打算去打副本。 这次的副本只有一个BOSS,而且BOSS是不需要击杀的,只需要和它比智力……. ╰半橙微兮°/ 2022年06月05日 03:20/ 0 赞/ 126 阅读
相关 算法题1 假设有这样一个国家,其法律规定当公民月收入为x时,若x> 1.则每月应当缴纳的税金为x的因数中除了x之外的最大值:同时该国法律允许公民将月收入分成若干部分(每部分均为整数),要 野性酷女/ 2022年05月08日 18:24/ 0 赞/ 118 阅读
相关 算法逻辑题 目录 统计一个txt文本文件中字母和数字的数量 获取数值数组中第二大的数的索引值,例如:数值数组为 \{2,5,8,8,3,7,9,4,1,6,9\}, 结果为 2 两 古城微笑少年丶/ 2022年02月23日 04:20/ 0 赞/ 144 阅读
相关 算法题 <table> <tbody> <tr> <td>N.RSA加密算法</td> </tr> <tr> <td> <table> 桃扇骨/ 2022年01月10日 10:23/ 0 赞/ 161 阅读
相关 其他算法题 绳子可以覆盖的最多点数 数轴上从左到右有n各点a\[0\], a\[1\], ……,a\[n -1\],给定一根长度为L的绳子,求绳子最多能覆盖其中的几个点 题解:对于 末蓝、/ 2021年09月18日 12:54/ 0 赞/ 277 阅读
还没有评论,来说两句吧...