iT邦幫忙

0

【LeetCode巧解欣賞】457. Circular Array Loop

題目: 457. Circular Array Loop
題意: 給你一個circular array,陣列上的數字代表走幾格(正數往右、負數往左走),問你陣列是否存在cycle?
cycle的定義是從某一點開始走,可以回到原點。但是cycle只能往同一個方向走,並且長度要大於1才算cycle。

例子:

Input: [2,-1,1,2,2]
Output: true
說明: 從index 0出發,走0->2->3->0回到原點

Input: [-1,2]
Output: false
說明: 你可以從index 1開始走回到index 1,但是cycle的長度只有1而不算cycle

Input: [-2,1,-1,-2,-2]
Output: false
說明: index 1->2->1->2->...不算cycle,因為1->2是往右跳,2->1是往左跳

乍看之下這一題好像不太難,
但是在眾多的限制下,很容易把這一題寫成O(n^2)時間,
要不然就是程式碼會寫的很長

我在某個地方看到程式碼很短又能夠O(n)時間解開的,
只能說真的有點厲害,
以欣賞的角度來看

巧解

class Solution:
    def circularArrayLoop(self, nums: List[int]) -> bool:
        for i, num in enumerate(nums):
            mark = str(i)
            while type(nums[i]) == int and num * nums[i] > 0 and nums[i] % len(nums) != 0:
                jump = nums[i] 
                nums[i] = mark
                i = (i + jump) % len(nums)
            if nums[i] == mark:
                return True
        return False

看討論區的其它解答好像沒看到這麼精簡的,
只要把nums裡面的數字掃一遍就做完,所以時間是O(n)

解析: 如何判斷cycle長度只有1而回傳False?

藏在while的條件判斷nums[i] % len(nums) != 0
如果cycle長度只有1,表示自己會一直跳回自己這個點,
就不會進while迴圈

解析: 如何判斷存在cycle方向有正有負而回傳False?

藏在while的條件判斷num * nums[i] > 0
前後兩數相乘大於0表示方向相同

解析: 如何判斷存在cycle?

可以在程式碼內印出一些資訊看各個數值變化的情形,
例如:

class Solution:
    def circularArrayLoop(self, nums: List[int]) -> bool:
        for i, num in enumerate(nums):
            mark = str(i)
            print("while外",i,num,nums)
            while type(nums[i]) == int and num * nums[i] > 0 and nums[i] % len(nums) != 0:
                print("    begin",i,num,nums)
                jump = nums[i] 
                nums[i] = mark
                i = (i + jump) % len(nums)
                print("    end",i,num,nums)
            if nums[i] == mark:
                return True
        return False

input = [1,2,-1,1,3,2]
印出:

while外 0 1 [1, 2, -1, 1, 3, 2]
    begin 0 1 [1, 2, -1, 1, 3, 2]
    end 1 1 ['0', 2, -1, 1, 3, 2]
    begin 1 1 ['0', 2, -1, 1, 3, 2]
    end 3 1 ['0', '0', -1, 1, 3, 2]
    begin 3 1 ['0', '0', -1, 1, 3, 2]
    end 4 1 ['0', '0', -1, '0', 3, 2]
    begin 4 1 ['0', '0', -1, '0', 3, 2]
    end 1 1 ['0', '0', -1, '0', '0', 2]

本題是0->1->3->4->1 產生cycle,可以看到同一個方向的cycle跳出for迴圈時,
會碰到mark標記

解析: 為何設 mark = str(i)而不是常數(e.g. '0')

避免因為反向跳,跳出while迴圈誤判成True,
比如說input是[-2,1,-1,-2,-2]的時候,
我們知道 index 1->2->1->2->...不算cycle,因為1->2是往右跳,2->1是往左跳,
看一下debug資訊:

while外 0 -2 [-2, 1, -1, -2, -2]
    begin 0 -2 [-2, 1, -1, -2, -2]
    end 3 -2 ['0', 1, -1, -2, -2]
    begin 3 -2 ['0', 1, -1, -2, -2]
    end 1 -2 ['0', 1, -1, '0', -2]
while外 1 1 ['0', 1, -1, '0', -2]
    begin 1 1 ['0', 1, -1, '0', -2]
    end 2 1 ['0', '1', -1, '0', -2]
while外 2 -1 ['0', '1', -1, '0', -2]
    begin 2 -1 ['0', '1', -1, '0', -2]
    end 1 -1 ['0', '1', '2', '0', -2]
...

關鍵在for迴圈run到i=1時,
由於index 2的方向跟1是相反的,所以2沒有標記

然而for迴圈run到i=2時,
先是往回跳一格到index 1,由於type(nums[i])不是int(已被標記過),
while迴圈結束,
這時因為有不同的標記而不會回傳True,
如果將程式改成mark = '0'就會錯誤回傳True

心得: 這個解答實在太精簡了,
估計我把程式蓋起來再重寫也有點寫不出來,
可以好好欣賞解答的思路


尚未有邦友留言

立即登入留言