算法题解---双向队列的优化
2022/6/5 1:20:28
本文主要是介绍算法题解---双向队列的优化,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目
Leetcode:2290
两题均可用bfs算法做出,但很难做到最优。
而如果将queue替换成deque将可以将速度提升一倍
思路
主要是将优先级较高的放在队列前面,提前出队,优先级低的放在队列尾处。
如何判断优先级将是至关重要的
- 如果路过该点会使的之后的答案与题目要求相违背
- 即该点优先级较低,可以放入队尾
- 反之,可以放入队头
代码
queue未优化
int dx[4]={0,0,1,-1}; int dy[4]={1,-1,0,0}; typedef pair<int,int> pii; class Solution { public: int minimumObstacles(vector<vector<int>>& grid) { auto & g = grid; int m = g.size(); int n= g[0].size(); vector<vector<int> > st(m+10,vector<int>(n+10,0x3f3f3f3f)); queue<pii> heap; heap.push({0,0}); int cnt=0; if(g[0][0])cnt++;st[0][0]=0; while(heap.size()){ auto top = heap.front(); heap.pop(); for(int i=0;i<4;i++){ int x= top.first+dx[i],y=top.second+dy[i]; if(x<0||x>=m||y<0||y>=n||st[x][y]<=(st[top.first][top.second]+g[x][y]))continue; st[x][y]=st[top.first][top.second]+g[x][y]; heap.push({x,y}); } } // for(int i=0;i<m;i++){ // for(int j=0;j<n;j++){ // cout<<st[i][j]<<" "; // }cout<<endl; // } return cnt+st[m-1][n-1]; } };
deque优化
int dx[4]={0,0,1,-1}; int dy[4]={1,-1,0,0}; typedef pair<int,int> pii; class Solution { public: int minimumObstacles(vector<vector<int>>& grid) { auto & g = grid; int m = g.size(); int n= g[0].size(); vector<vector<int> > st(m+10,vector<int>(n+10,0x3f3f3f3f)); deque<pii> heap; heap.push_front({0,0}); int cnt=0; if(g[0][0])cnt++;st[0][0]=0; while(heap.size()){ auto top = heap.front(); heap.pop_front(); for(int i=0;i<4;i++){ int x= top.first+dx[i],y=top.second+dy[i]; if(x<0||x>=m||y<0||y>=n||st[x][y]<=(st[top.first][top.second]+g[x][y]))continue; st[x][y]=st[top.first][top.second]+g[x][y]; if(g[x][y]) heap.push_back({x,y}); else heap.push_front({x,y}); } } // for(int i=0;i<m;i++){ // for(int j=0;j<n;j++){ // cout<<st[i][j]<<" "; // }cout<<endl; // } return cnt+st[m-1][n-1]; } };
这篇关于算法题解---双向队列的优化的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?