目录

• 题目
• 分析与题解
  • 分析图相邻节点
  • STL queue
  • 哈希表查找
  • 完整代码

题目

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

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

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

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

示例 1:

输入：deadends = ["0201","0101","0102","1212","2002"], target = "0202"
输出：6
解释：
可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。
注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的，
因为当拨动到 "0102" 时这个锁就会被锁定。

示例 2:

输入: deadends = ["8888"], target = "0009"
输出：1
解释：
把最后一位反向旋转一次即可 "0000" -> "0009"。

示例 3:

输入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
输出：-1
解释：
无法旋转到目标数字且不被锁定。

示例 4:

输入: deadends = ["0000"], target = "8888"
输出：-1

提示：

• 死亡列表 deadends 的长度范围为 [1, 500]。
• 目标数字 target 不会在 deadends 之中。
• 每个 deadends 和 target 中的字符串的数字会在 10,000 个可能的情况 '0000' 到 '9999' 中产生。

分析与题解

仔细想想，这就可以抽象成一幅图，每个节点有 8 个相邻的节点，又让你求最短距离，这就是典型的 BFS 框架。

分析图相邻节点

四位数字进行逐位的数字更改，每次更改可以向上拨调大一位数字，也可以向下拨动调小一位数字。由于密码实际是以字符串形式进行存储的，所以每次修改的是某位的字符大小。对于临界位(比如0调小变成9或者9增大变成0)需要单独进行讨论，其他情况直接在ANSⅡ码的数值上进行加减即可。

string plusOne(string str, int i){
        if(str[i]=='9')
            str[i] = '0';
            //字符形式的数字也是正序相邻
        else str[i] = str[i] + 1;
        return str;
    }

    string minusOne(string str, int i){
        if(str[i]=='0')
            str[i] = '9';
        else str[i] = str[i] - 1;
        return str;
    }

因此我们对四位数字进行循环，并在循环内同时对求出上调和下调所得出的新密码，并分别对其进行可行性的讨论。

//四位数字，2个方向
                //8种相邻情况，进行图的构建
                for(int i=0;i<4;i++){
                    string up = plusOne(cur, i);
                    //这里仅筛选不走重复路径
                    //关于是否为死亡密码
                    //放到下一个批次遍历图前进行讨论
                    if(!visited.count(up)){
                        q.push(up);
                        visited.insert(up);
                    }

                    string down = minusOne(cur, i);
                    if(!visited.count(down)){
                        q.push(down);
                        visited.insert(down);
                    }
                }

STL queue

在搜索的过程中会对很多不同组合的四位数字进行讨论，我们需要一个容器对上述路径进行存储。这里考虑使用队列(queue)。

queue<string> q;
q.push("0000");
//在 queue 的尾部添加一个元素的副本。
//这是通过调用底层容器的成员函数 push_back() 来完成的。

初始化队列并使用push()函数添加初始密码。

因为我们逐层进行路径的搜索，所以我们希望将距离起点路径长度相同的密码在同一批次进行考虑。

while(!q.empty()){
            int size = q.size();
            //一个批次一个批次的对路径进行讨论
            for(int i=0;i<size;i++){
            //对同一批次密码进行筛选
            string cur = q.front();
            q.pop();
                
                
            }

这里我们用遍历size存储队列中已有元素的个数，再利用队列只能在队尾添加新元素，只能从头部移除元素的疼醒,分批次对节点进行遍历。

需要注意queue相关的操作：

queue.front();
//返回queue头部首位元素的引用，但不会移除首位元素
queue.pop();
//删除queue的首位元素

哈希表查找

题目提供了deadends，包括了会造成死锁的密码组合。我们在后面对路径进行筛选时，会多次对列表的密码进行讨论。为了提高查找效率，我们尝试使用无序哈希表进行存储。

//先建立无序哈希表存储deadset和visited
//visited用于防止走回头路
unordered_set<string> visited;
unordered_set<string> deadset(deadends.begin(), deadends.end());

因为deadend和deadset存储着相同类型的元素的向量，所以可向上述代码这样进行初始化。

在同一批次的循环内，我们设置寻找终点的终止条件(其实就是字符串相等)，另外我们使用哈希表的count(tmp)函数来对死锁密码进行筛选，查找tmp元素在哈希表中的个数。

由于unordered_set中没有相同的元素，所以结果通常为0或1。

for(int i=0;i<size;i++){
                //先取处队列首位的元素 
                string cur = q.front();
                q.pop();

                //如果包含在死亡密码中，则直接跳过
                if(deadset.count(cur))  continue;
                if(cur==target) return step;
                
                //未完待续..
            }

另外考虑到会走回头路的问题。比如说我们从 "0000" 拨到 "1000"，但是等从队列拿出 "1000" 时，还会拨出一个 "0000"，这样的话会产生死循环。

我们也使用哈希表创建了一个visited容器，将目前已经走过的路径使用insert()函数进行收集。当已走过的节点从queue中移除后，仍然保留在visited容器中，当我们从相邻的八位节点中进行筛选时，防止走回头路造成死循环。

				//四位数字，2个方向
                //8种相邻情况，进行图的构建
                for(int i=0;i<4;i++){
                    string up = plusOne(cur, i);
                    //这里仅筛选不走重复路径
                    //关于是否为死亡密码
                    //放到下一个批次遍历图前进行讨论
                    if(!visited.count(up)){
                        q.push(up);
                        visited.insert(up);
                    }

                    string down = minusOne(cur, i);
                    if(!visited.count(down)){
                        q.push(down);
                        visited.insert(down);
                    }
                }

完整代码

class Solution {
public:
    string plusOne(string str, int i){
        if(str[i]=='9')
            str[i] = '0';
            //字符形式的数字也是正序相邻
        else str[i] = str[i] + 1;
        return str;
    }

    string minusOne(string str, int i){
        if(str[i]=='0')
            str[i] = '9';
        else str[i] = str[i] - 1;
        return str;
    }

    int openLock(vector<string>& deadends, string target) {
        //先建立无序哈希表存储deadset和visited
        //visited用于防止走回头路
        unordered_set<string> visited;
        unordered_set<string> deadset(deadends.begin(), deadends.end());

        //建立队列来讨论接下来的路径
        queue<string> q;
        q.push("0000");
        //先在visited中加入初始密码
        visited.insert("0000");
        //初始化步数为0
        int step = 0;

        while(!q.empty()){
            int size = q.size();
            //一个批次一个批次的对路径进行讨论
            for(int i=0;i<size;i++){
                //先取处队列首位的元素 
                string cur = q.front();
                q.pop();

                //如果包含在死亡密码中，则直接跳过
                if(deadset.count(cur))  continue;
                if(cur==target) return step;
                
                //四位数字，2个方向
                //8种相邻情况，进行图的构建
                for(int i=0;i<4;i++){
                    string up = plusOne(cur, i);
                    //这里仅筛选不走重复路径
                    //关于是否为死亡密码
                    //放到下一个批次遍历图前进行讨论
                    if(!visited.count(up)){
                        q.push(up);
                        visited.insert(up);
                    }

                    string down = minusOne(cur, i);
                    if(!visited.count(down)){
                        q.push(down);
                        visited.insert(down);
                    }
                }
            }
            step++;
        }
        return -1;
    }
};