目录

286. 墙与门417. 太平洋大西洋水流问题1469. 寻找所有的独生节点582. 杀掉进程863. 二叉树中所有距离为 K 的结点752. 打开转盘锁1319. 连通网络的操作次数1368. 使网格图至少有一条有效路径的最小代价1192. 查找集群内的「关键连接」

286. 墙与门

你被给定一个 m × n 的二维网格 rooms ，网格中有以下三种可能的初始化值：

-1 表示墙或是障碍物0 表示一扇门INF 无限表示一个空的房间。然后，我们用 231 - 1 = 2147483647 代表 INF。你可以认为通往门的距离总是小于 2147483647 的。

你要给每个空房间位上填上该房间到最近门的距离，如果无法到达门，则填 INF 即可。

示例 1：

输入：rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]

输出：[[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]

示例 2：

输入：rooms = [[-1]]

输出：[[-1]]

示例 3：

输入：rooms = [[2147483647]]

输出：[[2147483647]]

示例 4：

输入：rooms = [[0]]

输出：[[0]]

思路：

我发现这种东西只要是在二维图上进行涂涂画画的，包括之前美团的用不同颜色的笔画2*2的格子这种。基本就一个取巧的办法：逆推。

既然如此，我们这题可以逆推：

找到门，寻找可以到达的地方即可

代码实现：

class Solution {public void wallsAndGates(int[][] rooms) {for (int i = 0; i < rooms.length; i++) {for (int j = 0; j < rooms[0].length; j++) {if (rooms[i][j] == 0) {dfs(rooms, i, j, 0);}}}}public void dfs(int[][] rooms, int row, int col, int dist) {if (row < 0 || row >= rooms.length || col < 0 || col >= rooms[0].length || rooms[row][col] < dist) {return;} else if (dist != 0 && rooms[row][col] <= dist) {return;}rooms[row][col] = dist;dfs(rooms, row + 1, col, dist + 1);dfs(rooms, row - 1, col, dist + 1);dfs(rooms, row, col + 1, dist + 1);dfs(rooms, row, col - 1, dist + 1);}}

417. 太平洋大西洋水流问题

有一个 m × n 的矩形岛屿，与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界，而 “大西洋” 处于大陆的右边界和下边界。

这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights ， heights[r][c] 表示坐标 (r, c) 上单元格 高于海平面的高度 。

岛上雨水较多，如果相邻单元格的高度 小于或等于 当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。

返回网格坐标 result 的 2D 列表 ，其中 result[i] = [ri, ci] 表示雨水从单元格 (ri, ci) 流动 既可流向太平洋也可流向大西洋 。

示例 1：

输入: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]

输出: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

示例 2：

输入: heights = [[2,1],[1,2]]

输出: [[0,0],[0,1],[1,0],[1,1]]

思路：

逆向思维，

水漫金山

代码实现：

class Solution {private int m;//行private int n;//列boolean[][] Pacific;//到太平洋boolean[][] Atlantic;//到大西洋List<List<Integer>> res = new ArrayList<>();public List<List<Integer>> pacificAtlantic(int[][] heights) {m = heights.length;n = heights[0].length;Pacific = new boolean[m][n];Atlantic = new boolean[m][n];//逆向思维，水漫金山for (int i = 0; i < m; i++) {dfs(heights, Pacific, i, 0);//太平洋逆流而上dfs(heights, Atlantic, i, n - 1);//大西洋逆流而上}for (int j = 0; j < n; j++) {dfs(heights, Pacific, 0, j);//太平洋逆流而上dfs(heights, Atlantic, m - 1, j);//大西洋逆流而上}return res;}private void dfs(int[][] heights, boolean[][] Ocean, int x, int y) {if (Ocean[x][y]) return;Ocean[x][y] = true;//水来了if (Pacific[x][y] && Atlantic[x][y]) {//大西洋和天平洋都能来，不说了，trueres.add(Arrays.asList(x, y));}if (x - 1 >= 0 && heights[x][y] <= heights[x - 1][y]) {//上dfs(heights, Ocean, x - 1, y);}if (x + 1 < m && heights[x][y] <= heights[x + 1][y]) {//下dfs(heights, Ocean, x + 1, y);}if (y - 1 >= 0 && heights[x][y] <= heights[x][y - 1]) {//左dfs(heights, Ocean, x, y - 1);}if (y + 1 < n && heights[x][y] <= heights[x][y + 1]) {//右dfs(heights, Ocean, x, y + 1);}}}

1469. 寻找所有的独生节点

二叉树中，如果一个节点是其父节点的唯一子节点，则称这样的节点为 “独生节点” 。二叉树的根节点不会是独生节点，因为它没有父节点。

给定一棵二叉树的根节点 root ，返回树中 所有的独生节点的值所构成的数组 。数组的顺序 不限 。

示例 1：

输入：root = [1,2,3,null,4]

输出：[4]

解释：浅蓝色的节点是唯一的独生节点。

节点 1 是根节点，不是独生的。

节点 2 和 3 有共同的父节点，所以它们都不是独生的。

示例2

输入：root = [7,1,4,6,null,5,3,null,null,null,null,null,2]

输出：[6,2]

输出：浅蓝色的节点是独生节点。

请谨记，顺序是不限的。 [2,6] 也是一种可接受的答案。

示例3：

输入：root = [11,99,88,77,null,null,66,55,null,null,44,33,null,null,22]

输出：[77,55,33,66,44,22]

解释：节点 99 和 88 有共同的父节点，节点 11 是根节点。

其他所有节点都是独生节点。

示例4：

输入：root = [197]

输出：[]

示例5：

输入：root = [31,null,78,null,28]

输出：[78,28]

思路：

很简单，我层层遍历，只要我的儿子节点只有一个，我记将这个儿子添加进res，最后return就行了

代码实现：

/*** Definition for a binary tree node.* public class TreeNode {*int val;*TreeNode left;*TreeNode right;*TreeNode() {}*TreeNode(int val) { this.val = val; }*TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;*}* }*/class Solution {List<Integer> res = new ArrayList<>();public List<Integer> getLonelyNodes(TreeNode root) {if(root == null){return res;}if(root.left != null && root.right == null){res.add(root.left.val);}if(root.right != null && root.left == null){res.add(root.right.val);}getLonelyNodes(root.left);getLonelyNodes(root.right);return res;}}

582. 杀掉进程

系统中存在 n 个进程，形成一个有根树结构。给你两个整数数组 pid 和 ppid ，其中 pid[i] 是第 i 个进程的 ID ，ppid[i] 是第 i 个进程的父进程 ID 。

每一个进程只有 一个父进程 ，但是可能会有 一个或者多个子进程 。只有一个进程的 ppid[i] = 0 ，意味着这个进程 没有父进程 。

当一个进程 被杀掉 的时候，它所有的子进程和后代进程都要被杀掉。

给你一个整数 kill 表示要杀掉​​进程的 ID ，返回杀掉该进程后的所有进程 ID 的列表。可以按 任意顺序 返回答案。

示例 1：

输入：pid = [1,3,10,5], ppid = [3,0,5,3], kill = 5

输出：[5,10]

解释：涂为红色的进程是应该被杀掉的进程。

示例 2：

输入：pid = [1], ppid = [0], kill = 1

输出：[1]

思路：

我只要杀死一个进程，他的子进程都会被一起kill掉，所以我只要找到被kill的进程的pid和他的子进程的pid将他们返回就行了

遍历ppid，用HashMap记录key的子进程集合value采用队列的形式，讲map中key为kill的value取出并用队列将他存放按照层序遍历的方式，将子进程号，孙子进程号全部找出

代码实现：

class Solution {public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {Map<Integer, List<Integer>> map = new HashMap<>();for (int i = 0; i < pid.size(); i++) {if (ppid.get(i) != 0) {puteIfAbsent(ppid.get(i), key -> new ArrayList<>()).add(pid.get(i));}}List<Integer> killed = new ArrayList<>();Queue<Integer> queue = new ArrayDeque<>();queue.offer(kill);while (!queue.isEmpty()) {int head = queue.remove();killed.add(head);if (map.containsKey(head)) {for (int child : map.get(head)) {queue.offer(child);}}}return killed;}}

863. 二叉树中所有距离为 K 的结点

给定一个二叉树（具有根结点 root）， 一个目标结点 target ，和一个整数值 k 。

返回到目标结点 target 距离为 k 的所有结点的值的列表。 答案可以以 任何顺序 返回。

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2

输出：[7,4,1]

解释：所求结点为与目标结点（值为 5）距离为 2 的结点，值分别为 7，4，以及 1

示例 2:

输入: root = [1], target = 1, k = 3

输出: []

思路：

先找到目标节点，寻找过程中将每个节点的父节点记录下来沿3个方向（左、右、上）进行k次搜索找到节点，将他保存最后返回所有保存的节点值

代码实现：

/*** Definition for a binary tree node.* public class TreeNode {*int val;*TreeNode left;*TreeNode right;*TreeNode(int x) { val = x; }* }*/class Solution {// 用map记录每个节点的父节点private Map<TreeNode, TreeNode> parents = new HashMap<>();private Set<TreeNode> used = new HashSet<>();//不可重复集合用来标注已经访问的节点private TreeNode targetNode;// 找到目标节点后以目标节点为开始位置向三个方向蔓延public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {find(root, null, target);List<Integer> res = new LinkedList<>();dfs(targetNode, res, K);return res;}private void find(TreeNode root, TreeNode parent, TreeNode target) {if (null == root) {return;}if (root.val == target.val) {targetNode = root;}parents.put(root, parent);find(root.left, root, target);find(root.right, root, target);}private void dfs(TreeNode root, List<Integer> collector, int distance) {if (root != null && !used.contains(root)) {// 标记为已访问used.add(root);if (distance <= 0) {collector.add(root.val);return;}dfs(root.left, collector, distance - 1);//左孩子dfs(root.right, collector, distance - 1);//右孩子dfs(parents.get(root), collector, distance - 1);//他爹}}}

752. 打开转盘锁

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每个拨轮可以自由旋转：例如把 ‘9’ 变为 ‘0’，‘0’ 变为 ‘9’ 。每次旋转都只能旋转一个拨轮的一位数字。

锁的初始数字为 ‘0000’ ，一个代表四个拨轮的数字的字符串。

列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。

字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。

示例 1:

输入：deadends = [“0201”,“0101”,“0102”,“1212”,“2002”], target = “0202”

输出：6

解释：

可能的移动序列为 “0000” -> “1000” -> “1100” -> “1200” -> “1201” -> “1202” -> “0202”。

注意 “0000” -> “0001” -> “0002” -> “0102” -> “0202” 这样的序列是不能解锁的，

因为当拨动到 “0102” 时这个锁就会被锁定。

示例 2:

输入: deadends = [“8888”], target = “0009”

输出：1

解释：把最后一位反向旋转一次即可 “0000” -> “0009”。

示例 3:

输入: deadends = [“8887”,“8889”,“8878”,“8898”,“8788”,“8988”,“7888”,“9888”], target = “8888”

输出：-1

解释：无法旋转到目标数字且不被锁定。

思路：

用一个队列进行层序遍历

用一个集合记录已经访问过的路劲节点

只要访问过了或者遇到了死亡数字，直接返回

代码实现：

class Solution {public int openLock(String[] deadends, String target) {Set<String> dd = new HashSet<>();for (String s : deadends) {dd.add(s);}Queue<String> queue = new LinkedList<>();Set<String> visit = new HashSet<>();int count = 0;queue.offer("0000");visit.add("0000");//已访问的节点while (!queue.isEmpty()) {//当前数字状态能产生下一个密码的情况全都存放在queue中，只要已经访问过或者是死亡数字，立马停止接下来的动作int temp = queue.size();for (int i = 0; i < temp; i++) {String cur = queue.poll();if (dd.contains(cur)) {continue;}if (cur.equals(target)) {return count;}for (int j = 0; j < 4; j++) {String plus = plusOne(cur, j);if (!visit.contains(plus)) {queue.offer(plus);visit.add(plus);}String minu = minuOne(cur, j);if (!visit.contains(minu)) {queue.offer(minu);visit.add(minu);}}}count++;}return -1;}public String plusOne(String s, int j) {char[] c = s.toCharArray();if (c[j] == '9') {c[j] = '0';} else {c[j] += 1;}return new String(c);}public String minuOne(String s, int j) {char[] c = s.toCharArray();if (c[j] == '0') {c[j] = '9';} else {c[j] -= 1;}return new String(c);}}

1319. 连通网络的操作次数

用以太网线缆将 n 台计算机连接成一个网络，计算机的编号从 0 到 n-1。线缆用 connections 表示，其中 connections[i] = [a, b] 连接了计算机 a 和 b。

网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。

给你这个计算机网络的初始布线 connections，你可以拔开任意两台直连计算机之间的线缆，并用它连接一对未直连的计算机。请你计算并返回使所有计算机都连通所需的最少操作次数。如果不可能，则返回 -1 。

示例 1：

输入：n = 4, connections = [[0,1],[0,2],[1,2]]

输出：1

解释：拔下计算机 1 和 2 之间的线缆，并将它插到计算机 1 和 3 上。

示例 2：

输入：n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]

输出：2

示例 3：

输入：n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]

输出：-1

解释：线缆数量不足。

示例 4：

输入：n = 5, connections = [[0,1],[0,2],[3,4],[2,3]]

输出：0

思路：

n台机子，肯定至少需要n-1跟连接，如果连接数小于这个数，肯定完成不了，返回-1将整个连接梳理好，每个节点就只负责一条连接最后肯定有一个节点不需要负责，然后剩下的就是没有连接上的机子

代码实现：

class Solution {private int[] parent;//跟计算机i相连的计算机有parent[i]public int makeConnected(int n, int[][] connections) {// n 个节点相互连通至少需要n-1条线if (connections.length < n - 1) {return -1;}// 初始化parent = new int[n];for (int i = 0; i < n; i++) {parent[i] = i;//计算机i跟自己肯定是连接的呀}// 合并for (int[] connection : connections) {union(connection[0], connection[1]);//将这两个连在一起的看成一个整块儿}int count = 0;for (int i = 0; i < n; i++) {if (parent[i] == i) {count++;//断线的}}return count - 1;}private int find(int node) {return parent[node] == node ? node : (parent[node] = find(parent[node]));}private void union(int node1, int node2) {int root1 = find(node1);int root2 = find(node2);if (root1 == root2) {//发现其实其实这两个节点已经连上了只不过不是直连return;}parent[root1] = root2;}}

1368. 使网格图至少有一条有效路径的最小代价

给你一个 m x n 的网格图 grid 。 grid 中每个格子都有一个数字，对应着从该格子出发下一步走的方向。 grid[i][j] 中的数字可能为以下几种情况：

1 ，下一步往右走，也就是你会从 grid[i][j] 走到 grid[i][j + 1]2 ，下一步往左走，也就是你会从 grid[i][j] 走到 grid[i][j - 1]3 ，下一步往下走，也就是你会从 grid[i][j] 走到 grid[i + 1][j]4 ，下一步往上走，也就是你会从 grid[i][j] 走到 grid[i - 1][j]

注意网格图中可能会有 无效数字 ，因为它们可能指向 grid 以外的区域。

一开始，你会从最左上角的格子 (0,0) 出发。我们定义一条 有效路径 为从格子 (0,0) 出发，每一步都顺着数字对应方向走，最终在最右下角的格子 (m - 1, n - 1) 结束的路径。有效路径 不需要是最短路径 。

你可以花费 cost = 1 的代价修改一个格子中的数字，但每个格子中的数字 只能修改一次 。

请你返回让网格图至少有一条有效路径的最小代价。

示例 1：

输入：grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]

输出：3

解释：你将从点 (0, 0) 出发。

到达 (3, 3) 的路径为： (0, 0) --> (0, 1) --> (0, 2) --> (0, 3) 花费代价 cost = 1 使方向向下 --> (1, 3) --> (1, 2) --> (1, 1) --> (1, 0) 花费代价 cost = 1 使方向向下 --> (2, 0) --> (2, 1) --> (2, 2) --> (2, 3) 花费代价 cost = 1 使方向向下 --> (3, 3)

总花费为 cost = 3.

示例 2：

输入：grid = [[1,1,3],[3,2,2],[1,1,4]]

输出：0

解释：不修改任何数字你就可以从 (0, 0) 到达 (2, 2) 。

示例 3：

输入：grid = [[1,2],[4,3]]

输出：1

示例 4：

输入：grid = [[2,2,2],[2,2,2]]

输出：3

示例 5：

输入：grid = [[4]]

输出：0

思路：

首先我记录不更改方向所能到达的所有点的位置我在将通过步骤1获得的这些点进行挨个遍历，只要发现能到(m-1,n-1)这个位置，我就跳出循环，否则，将这些点挨个更改，更改后能到达的所有点也全部记录，同时将步骤1中获得的点全部删除。如此循环往复，每循环一次，意味着操作数+1，这也是DFS的思

代码实现：

class Solution {static int[][] step = {{}, {0, 1}, {0, -1}, {1, 0}, {-1, 0}};//右/左/下/上boolean[][] reached;int[][] grid;int m, n;public int minCost(int[][] grid) {m = grid.length;n = grid[0].length;this.grid = grid;//将输入参数变量变成全局变量LinkedList<int[]> zeroCost = new LinkedList<>();reached = new boolean[m][n];appendZeroCost(0, 0, zeroCost);//从(0,0)点能不更改地上图标方向达到的点int res = 0;while (!reached[m - 1][n - 1]) {//只要我不能到达右下角我就进行操作int len = zeroCost.size();while (len-- > 0) {int[] tuple = zeroCost.poll();//在能到达的所有点上动手if (tuple[0] == m - 1 && tuple[1] == n - 1) {break;//达到了，结束}for (int i = 1; i < 5; ++i) {//更改方向if (i == grid[tuple[0]][tuple[1]]) {continue;//这个方向本来就就是这个格子指向的方向}int nextX = tuple[0] + step[i][0], nextY = tuple[1] + step[i][1];//更改方向appendZeroCost(nextX, nextY, zeroCost);}}++res;}return res;}public void appendZeroCost(int x, int y, LinkedList<int[]> list) {while (x >= 0 && x < m && y >= 0 && y < n && !reached[x][y]) {//尽力到达能到达的最远的地方list.offer(new int[]{x, y});reached[x][y] = true;int nextX = x + step[grid[x][y]][0], nextY = y + step[grid[x][y]][1];//移动x = nextX;y = nextY;}}}

1192. 查找集群内的「关键连接」

力扣数据中心有 n 台服务器，分别按从 0 到 n-1 的方式进行了编号。它们之间以「服务器到服务器」点对点的形式相互连接组成了一个内部集群，其中连接 connections 是无向的。从形式上讲，connections[i] = [a, b] 表示服务器 a 和 b 之间形成连接。任何服务器都可以直接或者间接地通过网络到达任何其他服务器。

「关键连接」 是在该集群中的重要连接，也就是说，假如我们将它移除，便会导致某些服务器无法访问其他服务器。

请你以任意顺序返回该集群内的所有 「关键连接」。

示例 1：

输入：n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]

输出：[[1,3]]

解释：[[3,1]] 也是正确的。

示例 2:

输入：n = 2, connections = [[0,1]]

输出：[[0,1]]

思路：

看到这图，一下就想到了tarjan算法，如果你不知道这个算法是什么，可以看我这篇文章

从题目中我们就可以分析出，关键连接就是两个强连通分量顶点相连接的那条线，找出来添加到结果集上就行了。

代码实现：

class Solution {private int time;//时间戳private int[] dfn, low;public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {dfn = new int[n];//访问时间戳low = new int[n];//最早时间戳List<List<Integer>> list = new ArrayList<>();for (int i = 0; i < n; ++i) {list.add(new ArrayList<>());}for (List<Integer> conn : connections) {list.get(conn.get(0)).add(conn.get(1));list.get(conn.get(1)).add(conn.get(0));}List<List<Integer>> resultList = new ArrayList<>();for (int i = 0; i < n; ++i)if (dfn[i] == 0) {tarjanAlgorithm(i, -1, list, resultList);//list就是连通的信息}return resultList;}private void tarjanAlgorithm(int current, int previous, List<List<Integer>> list, List<List<Integer>> resultList) {//current就是x，就是当前访问时间戳dfn[current] = low[current] = ++time;//因为time默认初始化为0，所以这里用++timefor (int neighbor : list.get(current)) {//list就是连通的信息，当前节点相连的节点有哪些if (neighbor == previous) continue;//自己就是联通量if (dfn[neighbor] == 0) {//当前未访问tarjanAlgorithm(neighbor, current, list, resultList);if (dfn[current] < low[neighbor]) {//如果当前时间戳比能访问到的最早时间戳还要早，别的不说，我自己就是顶点List<Integer> conn = new ArrayList<>();conn.add(current);conn.add(neighbor);resultList.add(conn);}}low[current] = Math.min(low[current], low[neighbor]);//更新最早时间戳}}}

如果觉得《每日刷题总结——广度优先搜索 / 深度优先搜索》对你有帮助，请点赞、收藏，并留下你的观点哦！