leetcode1144-递减元素使数组呈锯齿状

原题

给你一个整数数组 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 <= 1000
  • 1 <= nums[i] <= 1000

解法

思想

分成奇、偶两种情况进行遍历,找到满足条件的最小值

代码

class Solution {
    public int movesToMakeZigzag(int[] nums) {
        int count1 = 0;
        for(int i = 0;i<nums.length;i+=2){
            int cur = nums[i];
            int diff = cur - Math.min(i==0?1001:nums[i-1],i == nums.length-1?1001:nums[i+1]) + 1;
            if(diff > 0) count1+=diff;
        }
        int count2 = 0;
        for(int i = 1;i<nums.length;i+=2){
            int cur = nums[i];
            int diff = cur - Math.min(nums[i-1],i == nums.length-1?1001:nums[i+1]) + 1;
            if(diff > 0) count2+=diff;
        }
        return Math.min(count1,count2);
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode1144-%e9%80%92%e5%87%8f%e5%85%83%e7%b4%a0%e4%bd%bf%e6%95%b0%e7%bb%84%e5%91%88%e9%94%af%e9%bd%bf%e7%8a%b6/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年6月4日
下一篇 2020年6月6日

相关推荐

  • leetcode206-反转链表

    原题 反转一个单链表。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 进阶: 你可以迭代或递归地反转链表。你能否用两种方法…

    2019年12月16日
    0160
  • leetcode454-四数相加II

    原题 给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ,使得 A[i] + B[j] + C[k] + D[l] = 0。 为…

    算法 2019年12月27日
    070
  • leetcode118-杨辉三角

    原题 给定一个非负整数 numRows,生成杨辉三角的前 numRows 行。在杨辉三角中,每个数是它左上方和右上方的数的和。 示例: 输入: 5 输出: [ [1], [1,1]…

    2019年11月15日
    0100
  • leetcode234-回文链表

    原题 请判断一个链表是否为回文链表。 示例1: 输入: 1->2 输出: false 示例2: 输入: 1->2->2->1 输出: true 进阶: 你能否用 O(n) 时间复杂…

    2019年12月16日
    0110
  • leetcode435-无重叠区间

    原题 给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。 注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”,但没…

    算法 2020年2月18日
    02420
  • leetcode221-最大正方形

    原题 在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。 示例: 输入: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 …

    算法 2020年5月8日
    0110
  • 用一个栈实现另一个栈的排序

    原题(来源牛客网) 一个栈中元素的类型为整型,现在想将该栈从顶到底按从大到小的顺序排序,只许申请一个栈。除此之外,可以申请新的变量,但不能申请额外的数据结构。如何完成排序? 解法 …

    算法 2020年4月20日
    02090
  • leetcode341-扁平化嵌套列表迭代器

    原题 给定一个嵌套的整型列表。设计一个迭代器,使其能够遍历这个整型列表中的所有整数。 列表中的项或者为一个整数,或者是另一个列表。 示例1: 输入: [[1,1],2,[1,1]]…

    算法 2020年1月27日
    050
  • leetcode41-缺失的第一个正数

    原题 给你一个未排序的整数数组,请你找出其中没有出现的最小的正整数。 示例 1: 输入: [1,2,0] 输出: 3 示例 2: 输入: [3,4,-1,1] 输出: 2 示例 3…

    算法 2020年5月11日
    0130
  • leetcode914-卡牌分组

    原题 给定一副牌,每张牌上都写着一个整数。 此时,你需要选定一个数字 X,使我们可以将整副牌按下述规则分成 1 组或更多组: 每组都有 X 张牌。 组内所有的牌上都写着相同的整数。…

    算法 2020年3月27日
    090

发表回复

登录后才能评论