面试经典150题——图的广度优先搜索

1、蛇梯棋

1.1 题目链接

点击跳转到题目位置

1.2 题目描述

给你一个大小为 n x n 的整数矩阵 board ，方格按从 1 到 n2 编号，编号遵循 转行交替方式 ，从左下角开始 （即，从 board[n - 1][0] 开始）的每一行改变方向。

你一开始位于棋盘上的方格 1。每一回合，玩家需要从当前方格 curr 开始出发，按下述要求前进：

• 选定目标方格 next ，目标方格的编号在范围 [curr + 1, min(curr + 6, n2)] 。
  该选择模拟了掷 六面体骰子 的情景，无论棋盘大小如何，玩家最多只能有 6 个目的地。
• 传送玩家：如果目标方格 next 处存在蛇或梯子，那么玩家会传送到蛇或梯子的目的地。否则，玩家传送到目标方格 next 。
• 当玩家到达编号 n² 的方格时，游戏结束。
  如果 board[r][c] != -1 ，位于 r 行 c 列的棋盘格中可能存在 “蛇” 或 “梯子”。那个蛇或梯子的目的地将会是 board[r][c]。编号为 1 和 n2 的方格不是任何蛇或梯子的起点。

注意，玩家在每次掷骰的前进过程中最多只能爬过蛇或梯子一次：就算目的地是另一条蛇或梯子的起点，玩家也 不能 继续移动。

• 举个例子，假设棋盘是 [[-1,4],[-1,3]] ，第一次移动，玩家的目标方格是 2 。那么这个玩家将会顺着梯子到达方格 3 ，但 不能 顺着方格 3 上的梯子前往方格 4 。（简单来说，类似飞行棋，玩家掷出骰子点数后移动对应格数，遇到单向的路径（即梯子或蛇）可以直接跳到路径的终点，但如果多个路径首尾相连，也不能连续跳多个路径）

返回达到编号为 n² 的方格所需的最少掷骰次数，如果不可能，则返回 -1。

1.3 解题代码

class Solution {
    int[] getXY(int curr, int n){
        int x = (curr - 1) / n;
        int y = (curr - 1) % n;        
        int[] point = new int[2];
        point[0] = n - 1 - x;
        if((x & 1) == 1){
            point[1] = (n - 1) - y;
        } else{
            point[1] = y;
        }
        return point; 
    }

    public int snakesAndLadders(int[][] board) {
        int n = board.length;
        int[] hash = new int[n * n + 1];
        int num = 0;
        Queue<Integer> q = new LinkedList<>();
        q.offer(1);
        hash[0] = 1;
        while(!q.isEmpty()){
            int len = q.size();
            num++;
            for(int i = 0; i < len; ++i){
                int curr = q.peek();
                q.poll();
                for(int j = 1; j <= 6; ++j){
                    int next_curr = curr + j;
                    if(next_curr > n * n){
                        break;
                    }
                    int[] point = getXY(next_curr, n);
                    int x = point[0];
                    int y = point[1];
                    if(board[x][y] != -1){// 如果存在梯子
                        next_curr = board[x][y];          
                    }
                    if(next_curr == n * n){
                        return num;
                    }
                    if(hash[next_curr] == 0){
                        hash[next_curr] = 1;
                        q.offer(next_curr);
                    } 
                }
            }
        }
    return -1;
    }
}

1.4 解题思路

1. 使用广度优先搜索（哈希+队列）。
2. 每次获取下一步所到的点，注意不能连续爬阶梯和蛇。

2、最小基因变化

2.1 题目链接

点击跳转到题目位置

2.2 题目描述

基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 ‘A’、‘C’、‘G’ 和 ‘T’ 之一。

假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。

• 例如，“AACCGGTT” --> “AACCGGTA” 就是一次基因变化。

另有一个基因库 bank 记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。（变化后的基因必须位于基因库 bank 中）

给你两个基因序列 start 和 end ，以及一个基因库 bank ，请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化，返回 -1 。

注意：起始基因序列 start 默认是有效的，但是它并不一定会出现在基因库中。

提示：

• start.length == 8
• end.length == 8
• 0 <= bank.length <= 10
• bank[i].length == 8
• start、end 和 bank[i] 仅由字符 [‘A’, ‘C’, ‘G’, ‘T’] 组成

2.3 解题代码

class Solution {
    public int minMutation(String startGene, String endGene, String[] bank) {
        Map<String, Integer> vis = new HashMap<String, Integer>();
        Queue<String> q = new LinkedList<String>();
        q.offer(startGene);
        vis.put(startGene, 1);
        int num = 0;
        while(!q.isEmpty()){
            int len = q.size();
            for(int i = 0; i < len; ++i){
                String str = q.peek();
                if(str.equals(endGene)){
                    return num;
                }
                q.poll();
                for(int j = 0; j < bank.length; ++j){
                    int flag = 0;
                    for(int k = 0; k < str.length(); ++k){
                        if(str.charAt(k) != bank[j].charAt(k)){
                            ++flag;
                        }
                    }
                    if(flag == 1){
                        if(!vis.containsKey(bank[j])){
                            vis.put(bank[j], 1); 
                            q.offer(bank[j]);
                        }
                    }
                }
            }
            ++num;
        }
    return -1;        
    }
}

2.4 解题思路

1. 使用广度优先搜索（哈希+队列）。
2. 每一轮队列取出的基因都是经过相同次数变化出来的。
3. 每次去查看当前队首的基因能否变成基因库里面的队列，如果能变成，则判断是否已经在前面的轮次已经变成了，如果没有变成，则将该基因放入队列中，并用哈希表标记其已经变成过了。
4. 最后如果基因已经变成了最终的基因，则返回变的次数即可。

3、单词接龙

3.1 题目链接

点击跳转到题目位置

3.2 题目描述

字典 wordList 中从单词 beginWord 到 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> … -> sk：

• 每一对相邻的单词只差一个字母。
• 对于 1 <= i <= k 时，每个 s_i 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
• s_k == endWord

给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。

提示：

• 1 <= beginWord.length <= 10
• endWord.length == beginWord.length
• 1 <= wordList.length <= 5000
• wordList[i].length == beginWord.length
• beginWord、endWord 和 wordList[i] 由小写英文字母组成
• beginWord != endWord
• wordList 中的所有字符串 互不相同

3.3 解题代码

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Map<String, Integer> vis = new HashMap<String, Integer>();
        Queue<String> q = new LinkedList<String>();
        q.offer(beginWord);
        vis.put(beginWord, 1);
        int num = 1;
        while(!q.isEmpty()){
            int len = q.size();
            for(int i = 0; i < len; ++i){
                String str = q.peek();
                if(str.equals(endWord)){
                    return num;
                }
                q.poll();
                for(int j = 0; j < wordList.size(); ++j){
                    int flag = 0;
                    for(int k = 0; k < str.length(); ++k){
                        if(str.charAt(k) != wordList.get(j).charAt(k)){
                            ++flag;
                        }
                    }
                    if(flag == 1){
                        if(!vis.containsKey(wordList.get(j))){
                            vis.put(wordList.get(j), 1); 
                            q.offer(wordList.get(j));
                        }
                    }
                }
            }
            ++num;
        }
    return 0;        
    }
}

3.4 解题思路

1. 使用与最小基因变化一样的代码足够通过。