leetcode_390 消除遊戲

語言: CN / TW / HK

要求

給定一個從1 到 n 排序的整數列表。\ 首先,從左到右,從第一個數字開始,每隔一個數字進行刪除,直到列表的末尾。\ 第二步,在剩下的數字中,從右到左,從倒數第一個數字開始,每隔一個數字進行刪除,直到列表開頭。\ 我們不斷重複這兩步,從左到右和從右到左交替進行,直到只剩下一個數字。\ 返回長度為 n 的列表中,最後剩下的數字。

示例: ``` 輸入: n = 9, 1 2 3 4 5 6 7 8 9 2 4 6 8 2 6 6

輸出: 6 ```

核心程式碼

python class Solution: def lastRemaining(self, n: int) -> int: base = 1 res = 1 while base * 2 <= n: res += base base *= 2 if base * 2 > n: break if int(n / base) % 2 == 1: res += base base *= 2 return res

image.png

解題思路:每刪一次,數字之間的距離會變為之前的兩倍,並且: - 從左往右刪的時候,每次都是刪掉第一個數字; - 從右往左刪的時候,則有可能刪掉第一個或者第二個數字; - 如果剩下的數字個數是偶數,刪掉的是第二個數字; - 如果剩下的數字個數是奇數,刪掉的是第一個數字; 所以我們只需要計算出並記錄當前陣列的第一個數字,只要第一個數字有了,後面的數字都可以計算出來了。

對於上面程式碼的理解:就是我們的從左向右走一遍,去掉了相隔1的數字,那麼我們數字之間的距離就變成了2倍,在回來在刪除一遍,距離變成4倍,但是回來的時候我們要判斷是否需要刪除第一位置的資料,進行了一次判斷。理解欠缺,此題還要在看看。