面试经典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. 与上一题的区别就是需要把每次队首的元素放入结果数组中，最后符合条件的输出结果数组，否则输出空数组。