Leetcode.752 打开转盘锁

1. 思路

我们可以使用广度优先搜索，找出从初始数字 0000到解锁数字 target 的最小旋转次数。
具体地，我们在一开始将 (0000,0) 加入队列，并使用该队列进行广度优先搜索。在搜索的过程中，设当前搜索到的数字为 status，旋转的次数为 step，我们可以枚举 status 通过一次旋转得到的数字。设其中的某个数字为 next_status，如果其没有被搜索过，我们将(next_status,step+1) 加入队列。如果搜索到了 target，我们就返回其对应的旋转次数。
为了避免搜索到死亡数字，我们可以使用哈希表存储 deadends 中的所有元素，这样在搜索的过程中，我们可以均摊 O(1) 地判断一个数字是否为死亡数字。同时，我们还需要一个哈希表存储所有搜索到的状态，避免重复搜索。

2. 代码

class Solution {
    public int openLock(String[] deadends, String target) {
    if (target.equals("0000")) {
      return 0;
    }
    Set<String> dead = new HashSet<String>();
    for (String deaded : deadends) {
        dead.add(deaded);
    }
    if(dead.contains("0000")){
      return -1;
    }
    int step =0;
    Queue<String> queue = new LinkedList<String>();
    queue.add("0000");
    Set<String> seen = new HashSet<String>();
    seen.add("0000");
    while (!queue.isEmpty()){
      step++;
      int size = queue.size();
      for(int i=0;i<size;i++){
        String cur = queue.poll();
        for(String nextString:get(cur)){
          if(!seen.contains(nextString)&&!dead.contains(nextString)){
            if(nextString.equals(target)){
              return step;
            }
            queue.add(nextString);
            seen.add(nextString);
          }
        }
      }
    }
    return -1;
  }
  public char numPrev(char x) {
    return x == '0' ? '9' : (char) (x - 1);
  }
  public char numSucc(char x) {
    return x == '9' ? '0' : (char) (x + 1);
  }
  public List<String> get(String status) {
    List<String> ret = new ArrayList<String>();
    char[] array = status.toCharArray();
    for (int i = 0; i < 4; ++i) {
      char num = array[i];
      array[i] = numPrev(num);
      ret.add(new String(array));
      array[i] = numSucc(num);
      ret.add(new String(array));
      array[i] = num;
    }
    return ret;
  }
}

Leetcode.773 滑动谜题

1. 思路

我们可以使用广度优先搜索，找出从初始状态 board 到目标状态 的最小交换次数。
具体地，我们在一开始将 加入队列，并使用该队列进行广度优先搜索。在搜索的过程中，设当前搜索到的状态为 ，操作的次数为 ，我们可以枚举 status 通过一次操作得到的状态。设其中的某个状态为 next_status，如果其没有被搜索过，我们就将 加入队列。如果搜索到了 ,我们就返回其对应的操作次数。
在搜索的过程中，我们需要一个哈希表存储所有搜索到的状态，避免重复搜索。
如果搜索完成后，我们仍没有搜索到 ，说明我们无法解开谜板，返回 -1。

2.代码

class Solution {
  int[][] neighbors = {{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}};
  public int slidingPuzzle(int[][] board) {
    StringBuffer stringBuffer = new StringBuffer();
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < 3; j++) {
        stringBuffer.append(board[i][j]);
      }
    }
    String initial = stringBuffer.toString();
    if (initial.equals("123450")) {
      return 0;
    }
    int step = 0;
    Queue<String> queue = new LinkedList<String>();
    queue.offer(initial);
    Set<String> seen = new HashSet<String>();
    seen.add(initial);
    while (!queue.isEmpty()) {
      step++;
      int size = queue.size();
      for (int i = 0; i < size; i++) {
        String cur = queue.poll();
        for (String nextStatus : get(cur)) {
          if (!seen.contains(nextStatus)) {
            if (nextStatus.equals("123450")) {
              return step;
            }
            queue.offer(nextStatus);
            seen.add(nextStatus);
          }
        }
      }
    }
    return -1;
  }
  private List<String> get(String cur) {
    List<String> stringList = new ArrayList<String>();
    char[] chars = cur.toCharArray();
    int index = cur.indexOf('0');
    for (int y : neighbors[index]) {
      swap(chars, index, y);
      stringList.add(String.valueOf(chars));
      swap(chars, index, y);
    }
    return stringList;
  }
  public void swap(char[] array, int x, int y) {
    char temp = array[x];
    array[x] = array[y];
    array[y] = temp;
  }
}

Leetcode. 909 蛇题棋

1. 思路

对于该问题，我们可以使用广度优先搜索。将节点编号和到达该节点的移动次数作为搜索状态，顺着该节点的出边扩展新状态，直至到达终点 ，返回此时的移动次数。若无法到达终点则返回 -1

2. 代码

class Solution {
    public int snakesAndLadders(int[][] board) {
        int n = board.length;
        boolean[] vis = new boolean[n * n + 1];
        Queue<int[]> queue = new LinkedList<int[]>();
        queue.offer(new int[]{1, 0});
        while (!queue.isEmpty()) {
            int[] p = queue.poll();
            for (int i = 1; i <= 6; ++i) {
                int nxt = p[0] + i;
                if (nxt > n * n) { // 超出边界
                    break;
                }
                int[] rc = id2rc(nxt, n); // 得到下一步的行列
                if (board[rc[0]][rc[1]] > 0) { // 存在蛇或梯子
                    nxt = board[rc[0]][rc[1]];
                }
                if (nxt == n * n) { // 到达终点
                    return p[1] + 1;
                }
                if (!vis[nxt]) {
                    vis[nxt] = true;
                    queue.offer(new int[]{nxt, p[1] + 1}); // 扩展新状态
                }
            }
        }
        return -1;
    }
    public int[] id2rc(int id, int n) {
        int r = (id - 1) / n, c = (id - 1) % n;
        if (r % 2 == 1) {
            c = n - 1 - c;
        }
        return new int[]{n - 1 - r, c};
    }
}