广州番禺最新疫情_河南网站建设品牌_中央新闻今日要闻_北京推广优化经理

题目：1345. 跳跃游戏 IV - 力扣（LeetCode）

经典bfs，关键是建立所有“arr[i] == arr[j]”的连接。我的做法是用额外的存储，记录每个整数的前后整数都是哪个，再对数组排序。每个整数搜索的下个节点就是prev、next和数组中相邻且相等的整数：

struct Node {int val;int index;int jumps = -1;Node* prev = nullptr;Node* next = nullptr;Node(int val) {this->val = val;}
};
bool myComp(Node* a, Node* b) {return a->val < b->val;
}
class Solution {
public:int minJumps(vector<int>& arr) {size_t n = arr.size();if (n <= 1) {return 0;}vector<Node*> nodes(n);for (int i = 0; i < n; i++) {nodes[i] = new Node(arr[i]);if (i > 0) {nodes[i - 1]->next = nodes[i];nodes[i]->prev = nodes[i - 1];}}list<Node*> bfs;bfs.push_back(nodes[0]);nodes[0]->jumps = 0;Node* tail = nodes[n - 1];sort(nodes.begin(), nodes.end(), myComp);for (int i = 0; i < n; i++) {nodes[i]->index = i;}Node* t;int i;while (!bfs.empty()) {t = bfs.front();bfs.pop_front();i = t->index - 1;while (i >= 0 && nodes[i]->val == t->val && nodes[i]->jumps == -1) {nodes[i]->jumps = t->jumps + 1;bfs.push_back(nodes[i]);i--;}i = t->index + 1;while (i < n && nodes[i]->val == t->val && nodes[i]->jumps == -1) {nodes[i]->jumps = t->jumps + 1;bfs.push_back(nodes[i]);i++;}if (t->prev && t->prev->jumps == -1) {t->prev->jumps = t->jumps + 1;bfs.push_back(t->prev);}if (t->next && t->next->jumps == -1) {t->next->jumps = t->jumps + 1;bfs.push_back(t->next);}if (tail->jumps != -1) {return tail->jumps;}}return (int) n - 1;}
};