建设网站租用空间,西安高风险区全部降为低风险,wordpress 下一篇,东莞企业网站推广运营题目链接#xff1a;https://leetcode.cn/problems/zlDJc7/
题目大意#xff1a;给出一个四位数字的密码锁#xff0c;初始状态是0000#xff0c;目标是targer。每一次转动只能让一个位的轮盘转动一下#xff08;0往后转是9#xff09;。有一个vectorstring dea…题目链接https://leetcode.cn/problems/zlDJc7/
题目大意给出一个四位数字的密码锁初始状态是0000目标是targer。每一次转动只能让一个位的轮盘转动一下0往后转是9。有一个vectorstring 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 step1;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(vectorstring deadends, string target) {setstring de;setstring known;string init(0000);for (int i 0; i deadends.size(); i)de.insert(deadends[i]);queuestring 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 step1;elseq.push(acc);}string dec getDec(q.front(), idx);if (!known.count(dec) !de.count(dec)) {known.insert(dec);if (dec target)return step1;elseq.push(dec);}}q.pop();}step;}return -1;}
};
