LeetCode——752. 打开转盘锁

一、题目

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每个拨轮可以自由旋转：例如把 ‘9’ 变为 ‘0’，‘0’ 变为 ‘9’ 。每次旋转都只能旋转一个拨轮的一位数字。

锁的初始数字为 ‘0000’ ，一个代表四个拨轮的数字的字符串。

列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。

字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/open-the-lock/description/

二、C++解法

我的思路及代码

BFS

当前状态到下一个状态无非就是4个位置往上拨，或者下拨。那么把这个状态抽象为一张图，即是从根节点出发有8个子节点的多叉树，最后我们要找的target就在其中某个结点。因为要找到最短的路径，所以我们采用BFS齐头并进的办法。由于题目中提到了 deadends 所以我们可以采用一组哈希表来存储 deadends 同时来记录我们已经访问到的组合，以免走回头路。具体代码如下。

class Solution {
public:void plusOne(string &ans,int index){if(ans[index] == '9')ans[index] = '0';else ans[index]++;}void minusOne(string &ans,int index){if(ans[index] == '0')ans[index] = '9';else ans[index]--;}int openLock(vector<string>& deadends, string target) {if(target == "0000")return 0;queue<string> q;unordered_map<string,bool> map;for(int k=0;k<deadends.size();k++){if(deadends[k]=="0000")return -1;else{map[deadends[k]] = true;}}q.push("0000");int ans=0;string s1,s2;map["0000"] = true;while(q.size()){int size = q.size();ans++;for(int i=0;i<size;i++){      for(int j=0;j<4;j++){s1 = q.front();plusOne(s1,j);if(s1==target)return ans;if(!map[s1]){map[s1]=true;q.push(s1);}} for(int j=0;j<4;j++){s2 = q.front();minusOne(s2,j);if(s2==target)return ans;if(!map[s2]){map[s2]=true;q.push(s2);}}q.pop();}}return -1;}
};

双向BFS

在我们知道终点的情况下，可以采用双向的BFS，同时从起点和终点开始发散，由于队列不方便查找元素，于是采用集合来代替，当一个集合中出现了另外一个集合的元素时，则说明已经找到了路径。在遍历中使用 temp 来临时存储每次扩散的结果，扩散结束后将 temp 的值给 set1 然后交换 set1 和 set2 的值，这样可以保证每次遍历的时候实际上是在交换遍历。

class Solution {
public:void plusOne(string &ans,int index){if(ans[index] == '9')ans[index] = '0';else ans[index]++;}void minusOne(string &ans,int index){if(ans[index] == '0')ans[index] = '9';else ans[index]--;}int openLock(vector<string>& deadends, string target) {//特殊情况if(target == "0000")return 0;//初始化unordered_set<string> set1;unordered_set<string> set2;unordered_set<string> dead;for(int k=0;k<deadends.size();k++){//特殊情况if(deadends[k]=="0000")return -1;elsedead.insert(deadends[k]);}set1.insert("0000");set2.insert(target);int ans=0;string s1,s2;while(set1.size()||set2.size()){unordered_set<string> temp;for(string ss:set1){ if(set2.count(ss))return ans;if(dead.count(ss))continue;dead.insert(ss);for(int i=0;i<4;i++){s1 = ss;s2 = ss;plusOne(s1,i);if(!dead.count(s1))temp.insert(s1);minusOne(s2,i);if(!dead.count(s2))temp.insert(s2);}}ans++;set1 = set2;set2 = temp;}return -1;}
};

官方参考代码

启发式搜索

struct AStar {// 计算启发函数static int getH(const string& status, const string& target) {int ret = 0;for (int i = 0; i < 4; ++i) {int dist = abs(int(status[i]) - int(target[i]));ret += min(dist, 10 - dist);}return ret;};AStar(const string& status, const string& target, int g): status_{status}, g_{g}, h_{getH(status, target)} {f_ = g_ + h_;}bool operator< (const AStar& that) const {return f_ > that.f_;}string status_;int f_, g_, h_;
};class Solution {
public:int openLock(vector<string>& deadends, string target) {if (target == "0000") {return 0;}unordered_set<string> dead(deadends.begin(), deadends.end());if (dead.count("0000")) {return -1;}auto num_prev = [](char x) -> char {return (x == '0' ? '9' : x - 1);};auto num_succ = [](char x) -> char {return (x == '9' ? '0' : x + 1);};auto get = [&](string& status) -> vector<string> {vector<string> ret;for (int i = 0; i < 4; ++i) {char num = status[i];status[i] = num_prev(num);ret.push_back(status);status[i] = num_succ(num);ret.push_back(status);status[i] = num;}return ret;};priority_queue<AStar> q;q.emplace("0000", target, 0);unordered_set<string> seen = {"0000"};while (!q.empty()) {AStar node = q.top();q.pop();for (auto&& next_status: get(node.status_)) {if (!seen.count(next_status) && !dead.count(next_status)) {if (next_status == target) {return node.g_ + 1;}q.emplace(next_status, target, node.g_ + 1);seen.insert(move(next_status));}}}return -1;}
};

启发式搜索不讨论时空复杂度。