个人练习-Leetcode-剑指 Offer II 109. 开密码锁

题目链接：https://leetcode.cn/problems/zlDJc7/

题目大意：给出一个四位数字的密码锁，初始状态是0000，目标是targer。每一次转动只能让一个位的轮盘转动一下（0往后转是9）。有一个vector<string> deadends，里面有很多四位的数字，如果转到其中的数字，就会死锁。我们在达到目标的过程中不能死锁。返回到达目标的最小步数，如果无法达到目标，返回-1

思路：BFS，每一步，每个数字有8个可能的变化。如果未访问且不属于死锁就加入队列。但这题还有挺多小细节的，做的时候debug了挺久…

首先，因为要得到步数，因此需要记录BFS的层数。所以BFS的while循环内还得加一层，qs记录当前队列长度，然后遍历完前qs个元素才给步数+1。

其次，【是否访问过某个数字】，实际上在其未加入队列，而在其作为邻居被访问时就可以标记了。在代码中表现为acc和dec就可以加入known中。当其作为q.front()再标记时，实际上可能是第二次或更多次的访问了，此时可能出现【同一数字被塞入队列多次】的情况。

比如q[1]的邻居是1234，未访问且不死锁，加入队列。而q[2]的邻居也是1234，未访问且不死锁，又加入队列。这样就塞了多次。因此，一个数字作为邻居被访问到时，就将其标记为访问过。

还有两个edge cases。

• 如果0000属于死锁，那么直接返回-1
• 如果target就是0000，就直接返回0

第二处是因为我们对一个数字的操作都在其【作为邻居被访问时】进行，而在队列中作为队首访问时，不再判断是否与target相等了。

                    string acc = getAcc(q.front(), idx);if (!known.count(acc) && !de.count(acc)) {known.insert(acc);if (acc == target)return step+1;elseq.push(acc);}

完整代码

class Solution {
public:string getAcc(string str, int idx) {string ret = str;if (ret[idx] == '9')ret[idx] = '0';elseret[idx]++;return ret;}string getDec(string str, int idx) {string ret = str;if (ret[idx] == '0')ret[idx] = '9';elseret[idx]--;return ret;}int openLock(vector<string>& deadends, string target) {set<string> de;set<string> known;string init("0000");for (int i = 0; i < deadends.size(); i++)de.insert(deadends[i]);queue<string> q;q.push(init);known.insert(init);if (de.count(init))return -1;if (target == init)return 0;int step = 0;while (!q.empty()) {int qs = q.size();for (int j = 0; j < qs; j++) {for (int idx = 0; idx < 4; idx++) {string acc = getAcc(q.front(), idx);if (!known.count(acc) && !de.count(acc)) {known.insert(acc);if (acc == target)return step+1;elseq.push(acc);}string dec = getDec(q.front(), idx);if (!known.count(dec) && !de.count(dec)) {known.insert(dec);if (dec == target)return step+1;elseq.push(dec);}}q.pop();}step++;}return -1;}
};