Re: [閒聊] 每日LeetCode

作者: idiont (supertroller)   2023-03-05 08:24:06
1345. Jump Game IV
給一個整數陣列 arr,現在一開始在第一個位置,
每一步都能:
1. 往後一格移動(如果可以)
2. 往前一格移動(如果可以)
3. 往數字一樣的格子移動, i.e. arr[i] == arr[j] (從 i 移動到 j)
求最少需要幾步才能走到最後一個位置。
Example 1:
Input: arr = [100,-23,-23,484,100,23,23,23,3,484]
Output: 3
Explanation:
0->4->3->9 (100走到100,往回走一格,484走到484到最後一格)
Example 2:
Input: arr = [7]
Output: 0
Explanation:
一開始就在最後一格,不需要移動
Example 3:
Input: arr = [7,6,9,6,9,6,9,7]
Output: 1
Explanation:
0->7 (7移動到7)
解題思路:
建邊做 BFS,就能計算出開頭到最後所需的最短步數。
建邊的方法,按照規則1、2的不需要特別處理,BFS pop 出來的時候直接檢查就行,
按照規則3的不能枚舉建邊會變成 O(n^2),我們可以改用一個 map 來記錄,
每個 key 對應到一個陣列,陣列裡面存了那些值跟 key 相同的 index,
這樣我們 BFS pop 出來時就直接找這個陣列然後每個都走過,
之後要把這個陣列清空,避免其他點又重新看過這個陣列,否則又會變 O(n^2)。
C++ code:
class Solution {
public:
int minJumps(vector<int>& arr) {
map<int, vector<int>> mp;
for(int i = arr.size() - 1; i >= 0; i
作者: RapeKingMiko (白賊櫻王)   2023-03-05 10:46:00
大師
作者: NTHUlagka (拉卡)   2023-03-05 11:48:00
大師
作者: a9486l (a9486l)   2023-03-05 11:49:00
大師

Links booklink

Contact Us: admin [ a t ] ucptt.com