LeetCode 752 | 打开转盘锁
2021/12/1 23:10:13
本文主要是介绍LeetCode 752 | 打开转盘锁,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
LeetCode 752 | 打开转盘锁
题目
题解
用BFS从“0000”开始遍历,套用BFS模板就行,只是多了判断是否需要继续拓展的条件(用set存,方便查)。
class Solution { public: int openLock(vector<string>& deadends, string target) { const string start="0000"; //用set存死锁情况方便查 unordered_set<string> dead(deadends.begin(),deadends.end()); //目标值为0000直接返回0 if(target=="0000")return 0; //一开始锁就是死的,返回-1 if(dead.count(start))return -1; queue<string> q; //保存已遍历的情况 unordered_set<string> visited{"0000"}; int steps=0; q.push(start); //开始BFS while(!q.empty()){ ++steps; //对当前栈内的情况进行BFS const int size=q.size(); for(int i=0;i<size;i++){ const string curr=q.front(); q.pop(); for(int j=0;j<4;j++){//4位数字 for(int k=-1;k<=1;k+=2){//每位上下拨 string next=curr; next[j]=(next[j]-'0'+k+10)%10+'0'; //找到目标值 if(next==target)return steps; //if。。便什么也不做 if(dead.count(next)||visited.count(next))continue; //不然。。 q.push(next); visited.insert(next); } } } } return -1; } };
这篇关于LeetCode 752 | 打开转盘锁的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-24怎么切换 Git 项目的远程仓库地址?-icode9专业技术文章分享
- 2024-12-24怎么更改 Git 远程仓库的名称?-icode9专业技术文章分享
- 2024-12-24更改 Git 本地分支关联的远程分支是什么命令?-icode9专业技术文章分享
- 2024-12-24uniapp 连接之后会被立马断开是什么原因?-icode9专业技术文章分享
- 2024-12-24cdn 路径可以指定规则映射吗?-icode9专业技术文章分享
- 2024-12-24CAP:Serverless?+AI?让应用开发更简单
- 2024-12-23新能源车企如何通过CRM工具优化客户关系管理,增强客户忠诚度与品牌影响力
- 2024-12-23原创tauri2.1+vite6.0+rust+arco客户端os平台系统|tauri2+rust桌面os管理
- 2024-12-23DevExpress 怎么实现右键菜单(Context Menu)显示中文?-icode9专业技术文章分享
- 2024-12-22怎么通过控制台去看我的页面渲染的内容在哪个文件中呢-icode9专业技术文章分享