面试经典150题——图

1、岛屿数量

1.1 题目链接

点击跳转到题目位置

1.2 题目描述

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] 的值为 ‘0’ 或 ‘1’

1.3 解题代码

class Solution {
    int[][] dir = {
        {-1, 0},
        {1, 0},
        {0, 1},
        {0, -1},
    };

    public int numIslands(char[][] grid) {
        Map<Integer, Integer> hash = new HashMap<Integer, Integer>(); 
        int m = grid.length;
        int n = grid[0].length;
        int ret = 0;
        Queue<Integer> q = new LinkedList();
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                if(grid[i][j] == '1' && !hash.containsKey(500 * i + j)){
                    q.offer(500 * i + j);
                    hash.put(500 * i + j, 1);
                    ++ret;
                }
                while(!q.isEmpty()){
                    int num = q.peek();
                    q.poll();
                    int x = num / 500;
                    int y = num % 500;
                    for(int k = 0; k < 4; ++k){
                        int tx = x + dir[k][0];
                        int ty = y + dir[k][1];
                        if(tx < 0 || tx >= m || ty < 0 || ty >= n || grid[tx][ty] == '0'){
                            continue;
                        }
                        if(!hash.containsKey(tx * 500 + ty)){
                            hash.put(tx * 500 + ty, 1);
                            q.offer(tx * 500 + ty);
                        }
                    }
                }
            }
        }
        return ret;
    }
}

1.4 解题思路

1. 使用广度优先搜索来解决问题。
2. 广度优先搜索的核心思路为哈希+队列。

2、被围绕的区域

2.1 题目链接

点击跳转到题目位置

2.2 题目描述

给你一个 m x n 的矩阵 board ，由若干字符 ‘X’ 和 ‘O’ 组成，捕获 所有 被围绕的区域：

• **连接：**一个单元格与水平或垂直方向上相邻的单元格连接。
• 区域：连接所有 ‘O’ 的单元格来形成一个区域。
• **围绕：**如果您可以用 ‘X’ 单元格 连接这个区域，并且区域中没有任何单元格位于 board 边缘，则该区域被 ‘X’ 单元格围绕。

通过 原地 将输入矩阵中的所有 ‘O’ 替换为 ‘X’ 来 捕获被围绕的区域。你不需要返回任何值。

提示：

• m == board.length
• n == board[i].length
• 1 <= m, n <= 200
• board[i][j] 为 ‘X’ 或 ‘O’

2.3 解题代码

class Solution {
    int[][] dir = {
        {-1, 0},
        {1, 0},
        {0, -1},
        {0, 1},
    };
    Map<Integer, Integer> hash = new HashMap<Integer, Integer>();

    void bfs(char[][] board, int startX, int startY, int m, int n){
        Queue<Integer> q = new LinkedList();
        q.offer(startX * 500 + startY);
        hash.put(startX * 500 + startY, 1);
        while(!q.isEmpty()){
            int num = q.peek();
            q.poll();
            int x = num / 500;
            int y = num % 500;
            for(int k = 0; k < 4; ++k){
                int tx = x + dir[k][0];
                int ty = y + dir[k][1];
                if(tx < 0 || tx >= m || ty < 0 || ty >= n || board[tx][ty] == 'X'){
                    continue;
                }
                if(!hash.containsKey(tx * 500 + ty)){
                    hash.put(tx * 500 + ty, 1);
                    q.offer(tx * 500 + ty);
                }
            }
        }
    }

    public void solve(char[][] board) {
        
        int m = board.length;
        int n = board[0].length;
        for(int i = 0; i < m; ++i){
            if(board[i][0] == 'O' && !hash.containsKey(i * 500 + 0)){
                bfs(board, i, 0, m, n);
            }
            if(board[i][n - 1] == 'O' && !hash.containsKey(i * 500 + n - 1)){
                bfs(board, i, n - 1, m, n);
            }
        }
        for(int j = 0; j < n; ++j){
            if(board[0][j] == 'O' && !hash.containsKey(0 * 500 + j)){
                bfs(board, 0, j, m, n);
            }
            if(board[m - 1][j] == 'O' && !hash.containsKey((m - 1) * 500 + j)){
                bfs(board, m - 1, j, m, n);
            }
        }

        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                if(board[i][j] == 'O' && !hash.containsKey(i * 500 + j)){
                    board[i][j] = 'X';
                }
            }
        }
    }
}

2.4 解题思路

1. 广度优先搜索，首先先从地图边缘开始进行广搜，将所有与地图边缘连接且字符为’O’的点用哈希表标注起来
2. 之后遍历地图，对所有字符为‘O’，并且哈希表中不存在的点转化成‘X’。

3、克隆图

3.1 题目链接

点击跳转到题目位置

3.2 题目描述

给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。

图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）

测试用例格式：

简单起见，每个节点的值都和它的索引相同。例如，第一个节点值为 1（val = 1），第二个节点值为 2（val = 2），以此类推。该图在测试用例中使用邻接列表表示。

邻接列表 是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。

给定节点将始终是图中的第一个节点（值为 1）。你必须将 给定节点的拷贝 作为对克隆图的引用返回。

提示：

• 这张图中的节点数在 [0, 100] 之间。
• 1 <= Node.val <= 100
• 每个节点值 Node.val 都是唯一的，
• 图中没有重复的边，也没有自环。
• 图是连通图，你可以从给定节点访问到所有节点。

3.3 解题代码

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/

class Solution {
    Map<Node, Node> hash = new HashMap<Node, Node>();

    public Node cloneGraph(Node node) {
        if(node == null){
            return null;
        }
        if(!hash.containsKey(node)){
            Node newNode = new Node(node.val);
            hash.put(node, newNode);
            for(int i = 0; i < node.neighbors.size(); ++i){
                newNode.neighbors.add(cloneGraph(node.neighbors.get(i)));
            }
        }
        return hash.get(node);
    }
}

3.4 解题思路

1. 递归求解即可，题目与之前的138. 随机链表的复制一致。

4、除法求值

4.1 题目链接

点击跳转到题目位置

4.2 题目描述

给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [A_i, B_i] 和 values[i] 共同表示等式 A_i / B_i = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。

另有一些以数组 queries 表示的问题，其中 queries[j] = [C_j, D_j] 表示第 j 个问题，请你根据已知条件找出 C_j / D_j = ? 的结果作为答案。

返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。

**注意：**输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。

**注意：**未在等式列表中出现的变量是未定义的，因此无法确定它们的答案。

提示：

• 1 <= equations.length <= 20
• equations[i].length == 2
• 1 <= Ai.length, Bi.length <= 5
• values.length == equations.length
• 0.0 < values[i] <= 20.0
• 1 <= queries.length <= 20
• queries[i].length == 2
• 1 <= Cj.length, Dj.length <= 5
• A_i, B_i, C_j, D_j 由小写英文字母与数字组成

4.3 解题代码

class Solution {
    Map<String, Integer> hash = new HashMap<String, Integer>();

    int find(List<Integer> pre, List<Double> weight, int x){
        
        if(x != pre.get(x)){
            int origin = pre.get(x);
            pre.set(x, find(pre, weight, pre.get(x))); 
            weight.set(x, weight.get(x) * weight.get(origin));
        }

        return pre.get(x);
    }

    void union(List<Integer> pre, List<Double> weight, double value, int x, int y){
        int index1 = find(pre, weight, x);
        int index2 = find(pre, weight, y);
        if(index1 != index2){
            pre.set(index1, index2);
            weight.set(index1, weight.get(y) * value / weight.get(x)); 
        }
        
    }
    
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {

        int equationsSize = equations.size();
        int queriesSize = queries.size();
        
        double[] res = new double[queriesSize];

        int id = 0;
        List<Integer> pre = new ArrayList<>();
        List<Double> weight = new ArrayList<Double>();
        for(int i = 0; i < equationsSize; ++i){
            String str1 = equations.get(i).get(0);
            String str2 = equations.get(i).get(1);
            if(!hash.containsKey(str1)){
                hash.put(str1, id);
                pre.add(id);
                weight.add(1.0d);
                id++;        
            }

            if(!hash.containsKey(str2)){
                hash.put(str2, id);
                pre.add(id);
                weight.add(1.0);
                id++;
            }
            union(pre, weight, values[i], hash.get(str1), hash.get(str2));
        }

        for(int i = 0; i < queriesSize; ++i){
            String str1 = queries.get(i).get(0);
            String str2 = queries.get(i).get(1);

            if(!hash.containsKey(str1) || !hash.containsKey(str2)){
                res[i] = -1.0;
                continue;
            }

            Integer id1 = hash.get(str1);
            Integer id2 = hash.get(str2);
            if(find(pre, weight, id1) != find(pre, weight, id2)){
                res[i] = -1.0d;
                continue;
            }

            double value1 = weight.get(id1);
            double value2 = weight.get(id2);
            res[i] = value1 / value2;
        }
        
        return res;
    }
}

4.4 解题思路

1. 使用并查集解决问题。

5、课程表

5.1 题目链接

点击跳转到题目位置

5.2 题目描述

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 a_i 则 必须 先学习课程 b_i 。

• 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

提示：

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• prerequisites[i] 中的所有课程对 互不相同

5.3 解题代码

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> edge = new ArrayList<>();
        for (int i = 0; i < numCourses; ++i) {
            edge.add(new ArrayList<>());
        }
        int[] deg = new int[numCourses];
        int n = prerequisites.length;
        for(int i = 0; i < n; ++i){
            int x = prerequisites[i][0];
            int y = prerequisites[i][1];
            deg[x]++;
            edge.get(y).add(x);
        }
        Queue<Integer> q = new LinkedList<Integer>();

        for(int i = 0; i < numCourses; ++i){
            if(deg[i] == 0){
                q.offer(i);
            }
        }
        
        while(!q.isEmpty()){
            int x = q.peek();
            q.poll();
            numCourses--;
            for(int i = 0; i < edge.get(x).size(); ++i){
                int num = edge.get(x).get(i);
                deg[num]--;
                if(deg[num] == 0){
                    q.offer(num);
                }
            }
        }
        return numCourses == 0;
    }
}

5.4 解题思路

1. 使用拓扑排序来解决问题
2. 每次将度为0的结点放入队列中，每次从队首取点，并且numCourses–。如果最后图中存在环的话，则numCourses则不为0。

6、课程表 II

6.1 题目链接

点击跳转到题目位置

6.2 题目描述

现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 a_i 前 必须 先选修 b_i 。

• 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。

返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。

提示：

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= numCourses * (numCourses - 1)
• prerequisites[i].length == 2
• 0 <= a_i, b_i < numCourses
• a_i != b_i
  所有[a_i, b_i] 互不相同

6.3 解题代码

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] res = new int[numCourses];
        int k = 0;
        List<List<Integer>> edge = new ArrayList<>();
        for (int i = 0; i < numCourses; ++i) {
            edge.add(new ArrayList<>());
        }
        int[] deg = new int[numCourses];
        int n = prerequisites.length;
        for(int i = 0; i < n; ++i){
            int x = prerequisites[i][0];
            int y = prerequisites[i][1];
            deg[x]++;
            edge.get(y).add(x);
        }
        Queue<Integer> q = new LinkedList<Integer>();

        for(int i = 0; i < numCourses; ++i){
            if(deg[i] == 0){
                q.offer(i);
            }
        }
        
        while(!q.isEmpty()){
            int x = q.peek();
            res[k++] = x;
            q.poll();
            numCourses--;
            for(int i = 0; i < edge.get(x).size(); ++i){
                int num = edge.get(x).get(i);
                deg[num]--;
                if(deg[num] == 0){
                    q.offer(num);
                }
            }
        }
        if(numCourses == 0){
            return res;
        }
        return new int[0];
    }
}

6.4 解题思路

1. 使用拓扑排序解题
2. 与上一题的区别就是需要把每次队首的元素放入结果数组中，最后符合条件的输出结果数组，否则输出空数组。