首页 > 其他 > 详细

【leetcode】1144. Decrease Elements To Make Array Zigzag

时间:2019-08-20 16:14:01      阅读:174      评论:0      收藏:0      [点我收藏+]

题目如下:

Given an array nums of integers, a move consists of choosing any element and decreasing it by 1.

An array A is a zigzag array if either:

  • Every even-indexed element is greater than adjacent elements, ie. A[0] > A[1] < A[2] > A[3] < A[4] > ...
  • OR, every odd-indexed element is greater than adjacent elements, ie. A[0] < A[1] > A[2] < A[3] > A[4] < ...

Return the minimum number of moves to transform the given array nums into a zigzag array.

 

Example 1:

Input: nums = [1,2,3]
Output: 2
Explanation: We can decrease 2 to 0 or 3 to 1.

Example 2:

Input: nums = [9,6,1,6,2]
Output: 4

 

Constraints:

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 1000

解题思路:本题无外乎两种情况,一种是nums[0] > nums[1],另一种是nums[0] < nums[1],把这两种情况计算一遍求较小值即可。在计算过程中,如果要求nums[i] > nums[i-1],那么把nums[i-1] 减到nums[i] - 1;如果要求nums[i] < nums[i-1],则把nums[i]减少到nums[i-1] - 1。

代码如下:

class Solution(object):
    def movesToMakeZigzag(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # flag -  0: decrease; 1:increase
        def process(flag,nums):
            count = 0
            for i in range(1, len(nums)):
                if flag == 0 and nums[i] >= nums[i - 1]:
                    count += (nums[i] - nums[i - 1] + 1)
                    nums[i] = nums[i - 1] - 1
                elif flag == 1 and nums[i] <= nums[i - 1]:
                    count += (nums[i - 1] - nums[i] + 1)
                    nums[i - 1] = nums[i] - 1
                flag = not flag
            return count


        #nums[0] > nums[1]
        res = process(0,nums[::])
        # nums[1] > nums[0]
        res = min(res,process(1,nums))
        return res

 

【leetcode】1144. Decrease Elements To Make Array Zigzag

原文:https://www.cnblogs.com/seyjs/p/11383437.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!