做暧暧视频免费视频网站,海沧区建设局网站市政处,写一个网站,泉州高端网站建设Problem: 752. 打开转盘锁 文章目录 题目描述思路及解法复杂度Code 题目描述 思路及解法 1.用一个集合 deads 存储所有的“死锁”状态#xff0c;一个集合 visited 存储所有已经访问过的状态#xff0c;以避免重复访问#xff0c;一个队列 q 进行广度优先搜索#xff08;BF… Problem: 752. 打开转盘锁 文章目录 题目描述思路及解法复杂度Code 题目描述 思路及解法 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 × M ) O(N \times M) O(N×M);其中 N N N为状态空间0000 - 9999 M M M为每个状态的子节点树即为8.具体到本题中可以认为时间复杂度为常量级别同理空间复杂度也为常量级别 空间复杂度: O ( N ) O(N) 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 skippedSetString deads new HashSet();for (String s : deadends) {deads.add(s);}// Record passwords that have been exhausted to prevent backtrackingSetString visited new HashSet();QueueString 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);}
}
