iT邦幫忙

0

【leetcode練功坊】665. Non-decreasing Array,答對率最低的一道Easy題

題目: 665. Non-decreasing Array
題意: 給你一個整數陣列,只有一次修改數字的機會,問你有沒有辦法把陣列變成遞增數列?

乍看之下好像也不是很難,
leetcode的分類也是Easy,
但是leetcode統計本題的答對率大概只有19.5%,
可能是最難的一道Easy題了

本題要想清楚確實不容易,
直觀來想,要把陣列變成遞增數列,
那就是當前面的數字大於後面的數字的時候出問題,應該修改。

然而,修改數字有多種情況,以致於不是很容易想清楚,舉三個例子如下:
「4」,2,3
-1,「4」,2,3
2,3,「3」,2,4

這邊我用引號括起來的數字是出問題的地方(這邊出問題指此數比下一個數字大),
但是你會發現出問題的數字有時候改前面(如第1,2個例子應修改4),
有時候改後面(如第3個例子應修改3後面的2)

那規律是什麼呢?
首先看出問題的數字前面是否有數字,

  • 如果前面沒有數字的情況,將此數改成下一個數字就可以,
  • 如果前面的數字比下一個數字小也一樣改成下一個數字

比如說 [4,2,3] -> [2,2,3]
[-1,4,2,3] -> [-1,2,2,3]

但是若前面的數字比下一個數字大,就只能去修改下一個數字了,
比如說[2,3,3,2,4] -> [2,3,3,3,4]

一開始,我們用一個變量cnt記錄修改次數(本題是一次),
如果碰到數字出問題,且修改次數用完的情況下就回傳False
程式實作如下:

class Solution:
    def checkPossibility(self, nums: List[int]) -> bool:
        cnt = 1 # 有一次修改機會
        for i in range(len(nums)-1):
            if nums[i]>nums[i+1]:
                if cnt == 0:
                    return False
                if i==0 or nums[i-1]<=nums[i+1]:
                    nums[i]=nums[i+1]
                else:
                    nums[i+1]=nums[i]
                cnt -=1
        return True

心得: 感覺此題比某些Medium題還困難


尚未有邦友留言

立即登入留言