Re: [閒聊] 每日LeetCode
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--){
mp[arr[i]].push_back(i);
}
vector<bool> vis(arr.size());
queue<int> que;
que.push(0);
vis[0] = true;
int ans = 0;
while(que.size() > 0){
int T = que.size();
while(T--){
int p = que.front();
que.pop();
if(p == arr.size() - 1) return ans;
if(p + 1 < arr.size() && !vis[p+1]){
que.push(p+1);
vis[p+1] = true;
}
if(p - 1 >= 0 && !vis[p-1]){
que.push(p-1);
vis[p-1] = true;
}
for(auto i : mp[arr[p]]){
if(!vis[i]){
if(i == arr.size() - 1) return ans + 1;
que.push(i);
vis[i] = true;
}
}
mp[arr[p]].clear();
}
ans++;
}
return 0;
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.229.216 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1677975848.A.29E.html
推
03/05 10:46,
2年前
, 1F
03/05 10:46, 1F
推
03/05 11:48,
2年前
, 2F
03/05 11:48, 2F
推
03/05 11:49,
2年前
, 3F
03/05 11:49, 3F
討論串 (同標題文章)
完整討論串 (本文為第 260 之 719 篇)：