975. Odd Even Jump

975. Odd Even Jump

根據網路上的數據，這一題曾經是 Google 面試的高頻動態規劃題目，Leetcode 的難度是困難的題目，一般而言我刷題的目標都是放在困難度中等的題目，不過有些困難的題目如果不是存在著特殊解法，是很好幫助我們去看看如何把不同的演算法。

這一個題目是問說，有一個陣列，裡面有不同的數字隨機排列，目標是要找出有幾個點可以通過一個特殊的規則跳到終點，也就是陣列中的最後一個位置，特殊的規則如下：

是第「奇數」次跳躍時，下一次可以跳的點是在當前位置 arr[i] 右側的任意一個位置 j ，只要 j > i 且 arr[j] 的值大於或等於 arr[i] ，如果說有很多地點可以跳，那就選比 arr[i] 還大的值中，最小的那一個點，如果遇上有多個相同的數字，選擇最近的那個跳過去（j最小）。也就是說要考量的點按照順序如下：

1. j > i
2. arr[j] >= arr[i]
3. 滿足以上條件最小的 arr[j]
4. 滿足以上條件最小的 j

arr = [1, 3, 2, 2]
i = 0 的時候，j = 1, j = 2, j = 3 都符合第二個條件
但是只有 j = 2, = 3 滿足第二個條件
但是要選比較小的 index ，所以只能跳到 2

是第「偶數」次跳躍時，下一次可以跳的點是在當前位置 arr[i] 右側的任意一個位置 j ，只要 j > i 且 arr[j] 的值小於或等於arr[i] ，如果說有很多地點可以跳，那就選比 arr[i] 還小的值中，最大的那一個點，如果遇上有多個相同的數字，選擇最近的那個跳過去（j最小）。

考慮的順序同奇數次跳躍其實光到這一步，要理解整個題目的規則就有點難度了，就網路上分享的經驗中，Google 的確喜歡考這樣的題目，考察面試者的反應與理解題目的思路。

暴力解

這個題目我一開始還是先使用暴力解，我會把我的想法一步一步記錄起來。

我想先解決最簡單的第一個問題，那就是每次我要如何判斷是奇數跳或是偶數跳？這是一個在現實應用中也很常用到的技巧，奇偶變換的問題，其實就是布林值的轉換，我不用確切記得當前的步數是第幾步，我只要知道我目前是在奇數的位置，下一步就一定是偶數。

下面的程式碼完成了主要的概念，我用 curr 記錄目前是從哪個點開始出發，每次跳躍我都會前進一些 index ，一直到如果我可以走到最後，就代表當前的位置 i 存在著路徑可以走到最後一個位置。

class Solution:
    def oddEvenJumps(self, arr: List[int]) -> int:
        ans = 0
        for i in range(len(arr) - 1):
            curr = i 
            isOdd = True
            while curr < len(arr):
                if isOdd:
                    # TODO
                else:
                    # TODO
                isOdd = not isOdd
            if curr == len(arr) - 1:
                # path does exist            
                ans += 1
            else:
                # path doesn't exist
                continue
        return ans

接著要處理題目比較困難的部分了，我一開始想到的直覺方法是直接去掃描整個右半部的陣列，先找出所有大於當前位置的值，然後再找出這些值得最小值，再比較哪個 index 最小，這樣想想其實沒有很好做，我後來就想到了其實我可以直接使用 heap 來處理就好，因為我要找的是最值，沒有排序找最值最好的方法就是用 heap ，加入 heap 的方式很簡單，我只要選擇比當前最大值大的值加入進去就好，也順便把 index 放進去，最後直接取最上面的值，就是最小值了。

這裡要注意的一點是，右半部可能並沒有路徑可以走，那這樣的話就是 heap 會是空值，我會返回 -1 作為，往右前進的索引並不存在。

class Solution:
    def oddEvenJumps(self, arr: List[int]) -> int:

        def oddSearch(curr):
            heap = []
            heapq.heapify(heap)
            for i in range(curr+1, len(arr)):
                if arr[curr] <= arr[i]:
                    heapq.heappush(heap, (arr[i], i))
            if not heap:
                return -1
            else:
                val, index = heapq.heappop(heap)
            return index

        def evenSearch(curr):
            heap = []
            heapq.heapify(heap)
            for i in range(curr+1, len(arr)):
                if arr[curr] >= arr[i]:
                    heapq.heappush(heap, (-arr[i], i))
            if not heap:
                return -1
            else:
                val, index = heapq.heappop(heap)
            return index

        ans = 1
        res = []
        memo = {}
        for i in range(len(arr) - 1):
            curr = i 
            isOdd = True
            while curr < len(arr):
                if isOdd:
                    index = oddSearch(curr)
                    if index == -1:
                        break
                    curr = index
                else:
                    index = evenSearch(curr)
                    if index == -1:
                        break
                    curr = index
                isOdd = not isOdd
            if curr == len(arr) - 1:
                ans += 1
                res.append(i)

        return ans

這樣的時間複雜度是很高的，因為我們至少需要遍歷一次陣列，每次跳躍很不巧的可能只能跳一格，花大約 \(O(nlogn)\) 的時間處理 Heap ，總共的時間複雜度約是 \(O(n^{3}logn)\)。

動態規劃解

題目做多了，遇到這種邊走邊選擇的題目，很直覺的就可以想到要怎麼用動態規劃解，這一題困難的是在做選擇的時候，需要考慮情境，像是我如果可以到位置 j ，可能是之前的格子在奇數跳的時候跳過來的，也可能是之前的格子，在偶數跳的時候跳過來的，兩種跳法也都不一樣，我一開始在寫的時候也會想，如果要考慮情境的話，還可以用動態規劃來解嗎？因為這樣有重疊子問題嗎？

這個題目一開始我也是寫的時候也是寫不出來，我先參考了別人講解的思考過程後，才嘗試看看要怎麼寫的。

我們先看看能不能先從第一個困難點解決，那就是先解決我們要往哪邊跳，如果可以先算出在奇數時該先跳到哪裡，和偶數時要跳去哪裡，那就會很方便，可以少去每次重新檢查的行為。

建立這個座標的方式滿特別的，首先既然要比大小，所以需要將原先的陣列做排序，可是排序玩原先的位置資訊就不在了，但是偏偏我們要知道他原先的索引，才能知道怎麼做。

這個答案是別人的做法，給我幾天我可能可以想到類似的寫法，面試一個小時的時間我自己是真的做不出來。

stack = []
odd_next_jump = [0] * n

# 將原先陣列的元素與索引一起取出後排序，這樣的排序會有這樣的特性:
# 裡面的元素從小排到大，如果遇上相同的值，就會依照索引由小排到大
for ele, idx in sorted([ele, idx] for idx, ele in enumerate(arr)):
    # 所有已經被放入到 stack 的索引，其索引所對應到的值
    # 一定比我當前索引對應到的值小，所以如果其索引在我左邊（stack[-1] < i）
    # 代表 stack[-1] 目前存的索引，他的下一步會是現在的索引 i 
    while stack and stack[-1] < i:
        # 於是，我們可以把這個記錄起來
        # ex: next_higher[2] = 4 就是代表 idx 2 可以走到 idx 4 
        odd_next_jump[stack.pop()] = i
    stack.append(i)

反之亦然

stack = []
even_next_jump = [0] * n

for ele, idx in sorted([-ele, idx] for idx, ele in enumerate(arr)):
    while stack and stack[-1] < idx:
        even_next_jump[stack.pop()] = i
    stack.append(idx)

最後一步就是要完成動態規劃的部分了。

我們會需要兩個 dp 的陣列，分別是 dp_odd 和 dp_even 這個要記錄的是，每個位置是否可以透過奇數跳或是偶數跳跳過來，這也是最後一個很燒腦的部分。

首先，不管是 dp_odd 或是 dp_even 最後一個位置就是陣列中的最後一個元素，我們都設定是 True 。

dp_odd = [False] * n 
dp_even = [False] * n
dp_odd[-1] = True
dp_even[-1] = True

一直到這個部分比較好理解，接下來最後一個部分就是要透過動態規劃來完成，這裡是一個自底向上的動態規劃，只是這個自底向上的行程是從最後一個位置往前面推，為什麼呢？因為最後一個位置，其實反而是這個題目的 Base Case 。

往前走的方向是這樣判斷的，如果說 dp_odd[i] 能往前走，要看的是之後的 dp_even[k] 是不是可以到的，k 取得的方式是看看 odd_next_jump[i] 能不能到，如果不能到的話就會是 0 ，那 0 又比 i 前面，所以這時候 dp_even[0] 會是 False 這時候 dp_odd[i]就會是 False 。

整個情況其實有點難想，尤其又是從後往前推，我覺得最容易的理解方式是考中斷點，用中斷點來看所有的變數的情況是什麼樣子。

真實面試中的時候，或許我真的天資不夠聰穎，我自認應該是沒辦法不靠任何中斷點就寫出 Bug Free 的程式碼，可是我覺得理解這個題目讓我對於動態規劃的認識多了很多，畢竟是經典題目，多看無益！