莱芜市网站建设公司,代理网址上境外网,网站安全建设的重要性,留学网站建设多少钱目录链接#xff1a;
力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目#xff1a;
https://github.com/September26/java-algorithms 原题链接#xff1a;力扣 描述#xff1a;
给你一个整数数组 nums#xff0c;每次 操作 会从中选择一个元素并 将该元素的…目录链接
力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目
https://github.com/September26/java-algorithms 原题链接力扣 描述
给你一个整数数组 nums每次 操作 会从中选择一个元素并 将该元素的值减少 1。
如果符合下列情况之一则数组 A 就是 锯齿数组
每个偶数索引对应的元素都大于相邻的元素即 A[0] A[1] A[2] A[3] A[4] ...或者每个奇数索引对应的元素都大于相邻的元素即 A[0] A[1] A[2] A[3] A[4] ...
返回将数组 nums 转换为锯齿数组所需的最小操作次数。 示例 1
输入nums [1,2,3]
输出2
解释我们可以把 2 递减到 0或把 3 递减到 1。示例 2
输入nums [9,6,1,6,2]
输出4提示
1 nums.length 10001 nums[i] 1000解题思路
* 解题思路
* 分别尝试两种可能即A[0]A[1]的可能以及A[0]A[1]的可能最后返回两者较小值。
* 接下来我们讲遍历的过程使用到了最优解的策略。
* 比如[2,2,2,2]A[0]A[1]的情况读到i1时发现A[1]A[0]则只能减少A[1]的值count1。A[1]减少只会让A[2]更可能大于A[1]。
* 同样[2,2,2,2]A[0]A[1]的情况读到i1时发现A[1]A[0]则只能减少A[0]的值,count1。A[0]减少不会影响A[2]和A[1]之间的比较。
代码
public class Solution1144 {public int movesToMakeZigzag(int[] nums) {return Math.min(countSum(Arrays.copyOf(nums, nums.length), true), countSum(nums, false));}public int countSum(int[] nums, boolean firstBig) {boolean isBig firstBig;int count 0;for (int i 1; i nums.length; i) {if (isBig) {if (nums[i - 1] nums[i]) {count (nums[i] - nums[i - 1] 1);nums[i] nums[i - 1] - 1;}isBig false;continue;}if (nums[i - 1] nums[i]) {count (nums[i - 1] - nums[i] 1);nums[i - 1] nums[i] - 1;}isBig true;}return count;}
}
