* @lc app=leetcode.cn id=1466 lang=golang * * [1466] 重新规划路线 * * https://leetcode.cn/problems/reorder-routes-to-make-all-paths-lead-to-the-city-zero/description/ * * algorithms * Medium (51.13%) * Likes: 147 * Dislikes: 0 * Total Accepted: 17.3K * Total Submissions: 33.8K * Testcase Example: '6\n[[0,1],[1,3],[2,3],[4,0],[4,5]]' * * n 座城市，从 0 到 n-1 编号，其间共有 n-1 * 条路线。因此，要想在两座不同城市之间旅行只有唯一一条路线可供选择（路线网形成一颗树）。去年，交通运输部决定重新规划路线，以改变交通拥堵的状况。 * * 路线用 connections 表示，其中 connections[i] = [a, b] 表示从城市 a 到 b 的一条有向路线。 * * 今年，城市 0 将会举办一场大型比赛，很多游客都想前往城市 0 。 * * 请你帮助重新规划路线方向，使每个城市都可以访问城市 0 。返回需要变更方向的最小路线数。 * * 题目数据 保证 每个城市在重新规划路线方向后都能到达城市 0 。 * * * * 示例 1： * * * * 输入：n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]] * 输出：3 * 解释：更改以红色显示的路线的方向，使每个城市都可以到达城市 0 。 * * 示例 2： * * * * 输入：n = 5, connections = [[1,0],[1,2],[3,2],[3,4]] * 输出：2 * 解释：更改以红色显示的路线的方向，使每个城市都可以到达城市 0 。 * * 示例 3： * * 输入：n = 3, connections = [[1,0],[2,0]] * 输出：0 * * * * * 提示： * * * 2 <= n <= 5 * 10^4 * connections.length == n-1 * connections[i].length == 2 * 0 <= connections[i][0], connections[i][1] <= n-1 * connections[i][0] != connections[i][1] * * */.

* @lc app=leetcode.cn id=1926 lang=golang * * [1926] 迷宫中离入口最近的出口 * * https://leetcode.cn/problems/nearest-exit-from-entrance-in-maze/description/ * * algorithms * Medium (39.74%) * Likes: 72 * Dislikes: 0 * Total Accepted: 18.4K * Total Submissions: 46.3K * Testcase Example: '[["+","+",".","+"],[".",".",".","+"],["+","+","+","."]]\n[1,2]' * * 给你一个 m x n 的迷宫矩阵 maze （下标从 0 开始），矩阵中有空格子（用 '.' 表示）和墙（用 '+' 表示）。同时给你迷宫的入口 * entrance ，用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列。 * * 每一步操作，你可以往 上，下，左 或者 右 移动一个格子。你不能进入墙所在的格子，你也不能离开迷宫。你的目标是找到离 entrance 最近 * 的出口。出口 的含义是 maze 边界 上的 空格子。entrance 格子 不算 出口。 * * 请你返回从 entrance 到最近出口的最短路径的 步数 ，如果不存在这样的路径，请你返回 -1 。 * * * * 示例 1： * * 输入：maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance * = [1,2] * 输出：1 * 解释：总共有 3 个出口，分别位于 (1,0)，(0,2) 和 (2,3) 。 * 一开始，你在入口格子 (1,2) 处。 * - 你可以往左移动 2 步到达 (1,0) 。 * - 你可以往上移动 1 步到达 (0,2) 。 * 从入口处没法到达 (2,3) 。 * 所以，最近的出口是 (0,2) ，距离为 1 步。 * * * 示例 2： * * 输入：maze = [["+","+","+"],[".",".","."],["+","+","+"]], entrance = [1,0] * 输出：2 * 解释：迷宫中只有 1 个出口，在 (1,2) 处。 * (1,0) 不算出口，因为它是入口格子。 * 初始时，你在入口与格子 (1,0) 处。 * - 你可以往右移动 2 步到达 (1,2) 处。 * 所以，最近的出口为 (1,2) ，距离为 2 步。 * * * 示例 3： * * 输入：maze = [[".","+"]], entrance = [0,0] * 输出：-1 * 解释：这个迷宫中没有出口。 * * * * * 提示： * * * maze.length == m * maze[i].length == n * 1 <= m, n <= 100 * maze[i][j] 要么是 '.' ，要么是 '+' 。 * entrance.length == 2 * 0 <= entrancerow < m * 0 <= entrancecol < n * entrance 一定是空格子。 * * */.

* @lc app=leetcode.cn id=399 lang=golang * * [399] 除法求值 * * https://leetcode.cn/problems/evaluate-division/description/ * - algorithms - Medium (59.00%) - Likes: 1043 - Dislikes: 0 - Total Accepted: 86.7K - Total Submissions: 147.1K - Testcase Example: '[["a","b"],["b","c"]]\n' + '[2.0,3.0]\n' + '[["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]' * * 给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 * values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。 * * 另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj * = ? 的结果作为答案。 * * 返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 * 替代这个答案。 * * 注意：输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。 * * 注意：未在等式列表中出现的变量是未定义的，因此无法确定它们的答案。 * * * * 示例 1： * * * 输入：equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = * [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]] * 输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000] * 解释： * 条件：a / b = 2.0, b / c = 3.0 * 问题：a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? * 结果：[6.0, 0.5, -1.0, 1.0, -1.0 ] * 注意：x 是未定义的 => -1.0 * * 示例 2： * * * 输入：equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], * queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]] * 输出：[3.75000,0.40000,5.00000,0.20000] * * * 示例 3： * * * 输入：equations = [["a","b"]], values = [0.5], queries = * [["a","b"],["b","a"],["a","c"],["x","y"]] * 输出：[0.50000,2.00000,-1.00000,-1.00000] * * * * * 提示： * * * 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 * Ai, Bi, Cj, Dj 由小写英文字母与数字组成 * * */.

* @lc app=leetcode.cn id=547 lang=golang * * [547] 省份数量 * * https://leetcode.cn/problems/number-of-provinces/description/ * * algorithms * Medium (62.15%) * Likes: 1072 * Dislikes: 0 * Total Accepted: 291.9K * Total Submissions: 469.8K * Testcase Example: '[[1,1,0],[1,1,0],[0,0,1]]' * * * * 有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c * 间接相连。 * * 省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。 * * 给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 * isConnected[i][j] = 0 表示二者不直接相连。 * * 返回矩阵中 省份 的数量。 * * * * 示例 1： * * * 输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]] * 输出：2 * * * 示例 2： * * * 输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]] * 输出：3 * * * * * 提示： * * * 1 * n == isConnected.length * n == isConnected[i].length * isConnected[i][j] 为 1 或 0 * isConnected[i][i] == 1 * isConnected[i][j] == isConnected[j][i] * * * * */.

* @lc app=leetcode.cn id=733 lang=golang * * [733] 图像渲染 * * https://leetcode.cn/problems/flood-fill/description/ * * algorithms * Easy (58.56%) * Likes: 415 * Dislikes: 0 * Total Accepted: 147.9K * Total Submissions: 252.2K * Testcase Example: '[[1,1,1],[1,1,0],[1,0,1]]\n1\n1\n2' * * 有一幅以 m x n 的二维整数数组表示的图画 image ，其中 image[i][j] 表示该图画的像素值大小。 * * 你也被给予三个整数 sr ,  sc 和 newColor 。你应该从像素 image[sr][sc] 开始对图像进行 上色填充 。 * * 为了完成 上色工作 ，从初始像素开始，记录初始坐标的 上下左右四个方向上 * 像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应 四个方向上 * 像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为 newColor 。 * * 最后返回 经过上色渲染后的图像 。 * * * * 示例 1: * * * * * 输入: image = [[1,1,1],[1,1,0],[1,0,1]]，sr = 1, sc = 1, newColor = 2 * 输出: [[2,2,2],[2,2,0],[2,0,1]] * 解析: 在图像的正中间，(坐标(sr,sc)=(1,1)),在路径上所有符合条件的像素点的颜色都被更改成2。 * 注意，右下角的像素没有更改为2，因为它不是在上下左右四个方向上与初始点相连的像素点。 * * * 示例 2: * * * 输入: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, newColor = 2 * 输出: [[2,2,2],[2,2,2]] * * * * * 提示: * * * m == image.length * n == image[i].length * 1 <= m, n <= 50 * 0 <= image[i][j], newColor < 2^16 * 0 <= sr < m * 0 <= sc < n * * */.

* @lc app=leetcode.cn id=841 lang=golang * * [841] 钥匙和房间 * * https://leetcode.cn/problems/keys-and-rooms/description/ * * algorithms * Medium (68.66%) * Likes: 347 * Dislikes: 0 * Total Accepted: 101.6K * Total Submissions: 147.8K * Testcase Example: '[[1],[2],[3],[]]' * * 有 n 个房间，房间按从 0 到 n - 1 编号。最初，除 0 * 号房间外的其余所有房间都被锁住。你的目标是进入所有的房间。然而，你不能在没有获得钥匙的时候进入锁住的房间。 * * 当你进入一个房间，你可能会在里面找到一套不同的钥匙，每把钥匙上都有对应的房间号，即表示钥匙可以打开的房间。你可以拿上所有钥匙去解锁其他房间。 * * 给你一个数组 rooms 其中 rooms[i] 是你进入 i 号房间可以获得的钥匙集合。如果能进入 所有 房间返回 true，否则返回 * false。 * * * * * * * 示例 1： * * * 输入：rooms = [[1],[2],[3],[]] * 输出：true * 解释： * 我们从 0 号房间开始，拿到钥匙 1。 * 之后我们去 1 号房间，拿到钥匙 2。 * 然后我们去 2 号房间，拿到钥匙 3。 * 最后我们去了 3 号房间。 * 由于我们能够进入每个房间，我们返回 true。 * * * 示例 2： * * * 输入：rooms = [[1,3],[3,0,1],[2],[0]] * 输出：false * 解释：我们不能进入 2 号房间。 * * * * * 提示： * * * n == rooms.length * 2 <= n <= 1000 * 0 <= rooms[i].length <= 1000 * 1 <= sum(rooms[i].length) <= 3000 * 0 <= rooms[i][j] < n * 所有 rooms[i] 的值 互不相同 * * */.

* @lc app=leetcode.cn id=994 lang=golang * * [994] 腐烂的橘子 * * https://leetcode.cn/problems/rotting-oranges/description/ * * algorithms * Medium (51.17%) * Likes: 781 * Dislikes: 0 * Total Accepted: 135.2K * Total Submissions: 264.2K * Testcase Example: '[[2,1,1],[1,1,0],[0,1,1]]' * * 在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一： * * * 值 0 代表空单元格； * 值 1 代表新鲜橘子； * 值 2 代表腐烂的橘子。 * * * 每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。 * * 返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。 * * * * 示例 1： * * * * * 输入：grid = [[2,1,1],[1,1,0],[0,1,1]] * 输出：4 * * * 示例 2： * * * 输入：grid = [[2,1,1],[0,1,1],[1,0,1]] * 输出：-1 * 解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个正向上。 * * * 示例 3： * * * 输入：grid = [[0,2]] * 输出：0 * 解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。 * * * * * 提示： * * * m == grid.length * n == grid[i].length * 1 <= m, n <= 10 * grid[i][j] 仅为 0、1 或 2 * * */.