网站建设 调研报告淘客联盟做任务网站

Problem: 752. 打开转盘锁

题目描述

思路及解法

1.用一个集合 deads 存储所有的“死锁”状态，一个集合 visited 存储所有已经访问过的状态，以避免重复访问，一个队列 q 进行广度优先搜索（BFS）;并将 deadends 数组中的每个元素加入 deads 集合。
2.将初始状态 “0000” 加入队列 q 并标记为已访问。

3.进行广度优先搜索（BFS）：

3.1.获取当前队列的大小 sz，表示当前层级中的节点数。
3.2.遍历当前层级中的每个节点：

3.2.1.从队列中取出一个节点 cur。如果 cur 在 deads 中，则跳过该节点。如果 cur 等于目标状态 target，则返回当前步数 step。
3.2.2.生成当前状态 cur 的所有相邻状态（每一位向上拨或向下拨）：对于每个相邻状态 up 和 down，如果尚未访问过，则加入队列并标记为已访问，最后使得步数step++

复杂度

时间复杂度:

$O(N\times M)$;其中$N$为状态空间0000 - 9999，$M$为每个状态的子节点树（即为8.具体到本题中可以认为时间复杂度为常量级别，同理空间复杂度也为常量级别）

空间复杂度:

$O(N)$

Code

class Solution {/*** Open the Lock** @param deadends Given string* @param target   Given string* @return int*/public int openLock(String[] deadends, String target) {// Record the death password to be skippedSet<String> deads = new HashSet<>();for (String s : deadends) {deads.add(s);}// Record passwords that have been exhausted to prevent backtrackingSet<String> visited = new HashSet<>();Queue<String> q = new LinkedList<>();// Start breadth-first search from the starting pointint step = 0;q.offer("0000");visited.add("0000");while (!q.isEmpty()) {int sz = q.size();// Spreads all nodes in the current queue aroundfor (int i = 0; i < sz; ++i) {String cur = q.poll();// Determine whether the destination is reachedif (deads.contains(cur)) {continue;}if (cur.equals(target)) {return step;}// Adds the untraversed adjacents of a node to the queuefor (int j = 0; j < 4; ++j) {String up = plusOne(cur, j);if (!visited.contains(up)) {q.offer(up);visited.add(up);}String down = minusOne(cur, j);if (!visited.contains(down)) {q.offer(down);visited.add(down);}}}step++;}return -1;}/*** Flip s[j] up once** @param s Given string* @param j Current number value* @return String*/private String plusOne(String s, int j) {char[] ch = s.toCharArray();if (ch[j] == '9') {ch[j] = '0';} else {ch[j] += 1;}return new String(ch);}/*** Move s[i] down once** @param s Given string* @param j Current number value* @return String*/private String minusOne(String s, int j) {char[] ch = s.toCharArray();if (ch[j] == '0') {ch[j] = '9';} else {ch[j] -= 1;}return new String(ch);}
}