文章目錄

• 1 題目理解
• 2 BFS
• 3 用int構建狀態

1 題目理解

一個鐘表有4個槽，每個槽可以停在0-9，10個狀態。鐘表每個槽的輪子可以轉，例如可以從0轉到9，也可以從0轉到1。
鐘表的起始狀態是"0000"。每個數字代表一個槽的狀態。
輸入：字符串數組deadends，表示不能死亡狀態，進入這個狀態鐘表就被鎖住了，不能動了。輸入字符串target表示想要達到的狀態。
輸出：到達最終狀態的最少需要多少步。如果不能達到則為-1。
規則：每一步，鐘表只能轉動一個槽，只能轉一下，
例子：
Input: deadends = [“0201”,“0101”,“0102”,“1212”,“2002”], target = “0202”
Output: 6
Explanation:
A sequence of valid moves would be “0000” -> “1000” -> “1100” -> “1200” -> “1201” -> “1202” -> “0202”.
Note that a sequence like “0000” -> “0001” -> “0002” -> “0102” -> “0202” would be invalid,
because the wheels of the lock become stuck after the display becomes the dead end “0102”.

2 BFS

要求最短路徑長度，所以使用BFS。
在某一種狀態下，要先判斷這個狀態能不能動。如果deadends包含target，則不能達到。

在正常狀態下，某一狀態的變化，可以變化其中一個槽，變化的動作可以是加1，也可以是減1。變化之后進入新的狀態。

class Solution {public int openLock(String[] deadends, String target) {Set<String> set = new HashSet<String>();for(String str : deadends){set.add(str);}String start = "0000";if(set.contains(target) || set.contains(start)) return -1;Queue<String> queue = new LinkedList<String>();queue.offer(start);set.add(start);int step = 0;while(!queue.isEmpty()){int size = queue.size();//System.out.println(queue);for(int r=0;r<size;r++){if(target.equals(queue.peek())){return step;}char[] current = queue.poll().toCharArray();for(int i=0;i<4;i++){char ch = current[i];int v = current[i]-48;current[i] = (char)(((v+1+10)%10)+48);String newState = new String(current);if(!set.contains(newState)){queue.offer(newState);set.add(newState);}current[i] = (char)(((v-1+10)%10)+48);String newState2 = new String(current);if(!set.contains(newState2)){queue.offer(newState2);set.add(newState2);}current[i] = ch;}}step++;}return -1;}}

時間復雜度：可以選擇的數據范圍n=10，狀態位數x=4，$O(10^4?4?4)$。最壞情況下有$10^4$種狀態。每個狀態可以有4*2=8種變化，所以是O(x)。枚舉后得到新的狀態，構建字符串，需要O(x)時間。所以最終結果是：$O(n^x?x?x)$

3 用int構建狀態

因為每個位置的值在0-9之間，可以用4位二進制表示，我們可以用int表示狀態，這樣速度方面會更快。

class Solution {private final static int[] increments = new int[]{ 1, -1 };public int openLock(String[] deadends, String target) {int step = 0;Set<Integer> used = new HashSet<Integer>();String start = "0000";int startInt = 0;int targetInt = buildState(target);for(String deadend : deadends){used.add(buildState(deadend));}if(used.contains(startInt) || used.contains(targetInt)) return -1;used.add(startInt);Queue<Integer> queue = new LinkedList<Integer>();queue.offer(startInt);while(!queue.isEmpty()){int size =queue.size();for(int i=0;i<size;i++){int nodeInt = queue.poll();if(nodeInt==targetInt) return step;for(int increment : increments){for(int j =0;j<4;j++){int newNode = updateState(nodeInt,j,increment);if(!used.contains(newNode)){used.add(newNode);queue.offer(newNode);}}}}step++;}return -1;}private int updateState(int state, int d, int inc) {int mask = (1 << 4) - 1;int[] num = new int[]{state & mask,(state >> 4) & mask,(state >> 8) & mask,(state >> 12) & mask};int n = num[d];if (n == 0 && inc == -1) {num[d] = 9;} else if (n == 9 && inc == 1) {num[d] = 0;} else {num[d] += inc;}int res = 0;for (int i = 3; i >= 0; i--) {res <<= 4;res |= num[i];}return res;}private int buildState(String state) {char[] c = state.toCharArray();int res = 0;for (int i = 0; i < c.length; i++) {int d = c[i] - '0';res <<= 4;res |= d;}return res;} }

總結

以上是生活随笔為你收集整理的752. Open the Lock的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。