Re: [姆咪] 每日LeetCode

看板Sad_turtle作者sixB (6B)時間4周前 (2026/05/21 03:52)推噓1(1推 0噓 1→)

留言2則, 2人參與討論串2/2 (看更多)

1345. jump game iv じゃんけんぽん上古時代的hard真的好爽喔水題== 算dp嗎 bfs 應該queue就行了沒有很漂亮我懶：） class Solution { public: int minJumps(vector<int>& arr) { int n = arr.size(); vector<int> step(n, n); step[0] = 0; unordered_map<int, vector<int>> mp; // mp<num, idx> for(int i = 0; i < n; i++){ mp[arr[i]].push_back(i); } unordered_set<int> round; round.insert(arr[0]); for(int cnt = 1; step[n-1] == n; cnt++){ // cout << "cnt = " << cnt << '\n'; unordered_set<int> next_round; for(auto num: round){ // cout << num << '\n'; for(auto idx : mp[num]){ if(step[idx] < cnt){ if((idx+1) < n and step[idx+1] > cnt){ step[idx+1] = cnt; next_round.insert(arr[idx+1]); } if((idx-1) >= 0 and step[idx-1] > cnt){ step[idx-1] = cnt; next_round.insert(arr[idx-1]); } } else { step[idx] = cnt; next_round.insert(arr[idx]); } // std::string s = std::format("{}: {}", idx, step[idx]); // cout << s << '\n'; } } round = move(next_round); } return step[n-1]; } }; -- 很姆的咪姆之咪 http://i.imgur.com/5sw7QOj.jpg