矩阵
约 4907 字大约 16 分钟
腐烂的橘子leetcode994
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
时间复杂度：O(nm)。即进行一次广度优先搜索的时间，其中 n,m 分别为 grid 的行数与列数。
空间复杂度：O(nm)。需要额外的 dis 数组记录每个新鲜橘子被腐烂的最短时间，大小为 O(nm)，且广度优先搜索中队列里存放的状态最多不会超过 nm 个，最多需要 O(nm) 的空间，所以最后的空间复杂度为 O(nm)。
class Solution {
//在 BFS 或 DFS 遍历中，这两个数组用于计算从当前单元格 (r, c) 到相邻单元格的坐标
//dr（row direction）表示在行方向上的偏移量。向上、向左、向下和向右的行偏移量
int[] dr = new int[]{-1, 0, 1, 0};
//dc（column direction）表示在列方向上的偏移量。向上、向左、向下和向右的列偏移量
int[] dc = new int[]{0, -1, 0, 1};
public int orangesRotting(int[][] grid) {
int R = grid.length, C = grid[0].length;
Queue<Integer> queue = new ArrayDeque<Integer>();
//每个橘子对应的腐烂时间
Map<Integer, Integer> depth = new HashMap<Integer, Integer>();
for (int r = 0; r < R; ++r) {
for (int c = 0; c < C; ++c) {
if (grid[r][c] == 2) {//将所有腐烂的橘子加入到队列中
int code = r * C + c;//编码
queue.add(code);
depth.put(code, 0);
}
}
}
int ans = 0;//ans 记录了这些腐烂时间的最大值，也就是所有橘子完全腐烂所需的最长时间
while (!queue.isEmpty()) {
int code = queue.remove();
int r = code / C, c = code % C;//解码
for (int k = 0; k < 4; ++k) {//用于计算从当前单元格 (r, c) 到相邻单元格的坐标
int nr = r + dr[k];//上左下右移动找到新鲜橘子
int nc = c + dc[k];
if (0 <= nr && nr < R && 0 <= nc && nc < C && grid[nr][nc] == 1) {
grid[nr][nc] = 2;
int ncode = nr * C + nc;
queue.add(ncode);
depth.put(ncode, depth.get(code) + 1);//每一次腐烂别的橘子时都+1，depth 中存储了所有被腐烂的橘子的最短腐烂时间
ans = depth.get(ncode);
}
}
}
for (int[] row: grid) {
for (int v: row) {
if (v == 1) {
return -1;
}
}
}
return ans;
}
}
207课程表
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
示例 1：
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
示例 2：
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。
时间复杂度: O(n+m)，其中 n 为课程数，m 为先修课程的要求数。这其实就是对图进行深度优先搜索的时间复杂度。
空间复杂度: O(n+m)。题目中是以列表形式给出的先修课程关系，为了对图进行深度优先搜索，我们需要存储成邻接表的形式，空间复杂度为 O(n+m)。在深度优先搜索的过程中，我们需要最多 O(n) 的栈空间（递归）进行深度优先搜索，因此总空间复杂度为 O(n+m)。
对于图中的任意一个节点，它在搜索的过程中有三种状态，即：
-「未搜索」：我们还没有搜索到这个节点；
-「搜索中」：我们搜索过这个节点，但还没有回溯到该节点，即该节点还没有入栈，还有相邻的节点没有搜索完成）；
-「已完成」：我们搜索过并且回溯过这个节点，即该节点已经入栈，并且所有该节点的相邻节点都出现在栈的更底部的位置，满足拓扑排序的要求。
在每一轮的搜索搜索开始时，我们任取一个「未搜索」的节点开始进行深度优先搜索。我们将当前搜索的节点 u 标记为「搜索中」，遍历该节点的每一个相邻节点 v：
- 如果 v 为「未搜索」，那么我们开始搜索 v，待搜索完成回溯到 u；
- 如果 v 为「搜索中」，那么我们就找到了图中的一个环，因此是不存在拓扑排序的；
- 如果 v 为「已完成」，那么说明 v 已经在栈中了，而 u 还不在栈中，因此 u 无论何时入栈都不会影响到 (u,v) 之前的拓扑关系，以及不用进行任何操作。
- 当 u 的所有相邻节点都为「已完成」时，我们将 u 放入栈中，并将其标记为「已完成」。
在整个深度优先搜索的过程结束后，如果我们没有找到图中的环，那么栈中存储这所有的 n 个节点，从栈顶到栈底的顺序即为一种拓扑排序。
class Solution {
List<List<Integer>> edges;
int[] visited;
boolean valid = true;
public boolean canFinish(int numCourses, int[][] prerequisites) {
edges = new ArrayList<List<Integer>>();
for (int i = 0; i < numCourses; ++i) {
edges.add(new ArrayList<Integer>());//表示课程的依赖关系图
}
visited = new int[numCourses];
for (int[] info : prerequisites) {
edges.get(info[1]).add(info[0]);//edges.get(i) 存储的是所有必须在课程 i 之后完成的课程。
}
for (int i = 0; i < numCourses && valid; ++i) {
if (visited[i] == 0) {//对每个课程进行 DFS，判断是否存在循环依赖。只有 visited[i] == 0 时，才会进行 DFS。
dfs(i);
}
}
return valid;
}
public void dfs(int u) {
visited[u] = 1;//标记当前课程为正在访问中:
for (int v: edges.get(u)) {
if (visited[v] == 0) {
dfs(v);
if (!valid) {
return;
}
} else if (visited[v] == 1) {//说明出现了环，设置 valid = false 并返回。
valid = false;
return;
}
}
visited[u] = 2;
}
}
拓扑排序中最前面的节点，该节点一定不会有任何入边，也就是它没有任何的先修课程要求。当我们将一个节点加入答案中后，我们就可以移除它的所有出边，代表着它的相邻节点少了一门先修课程的要求。如果某个相邻节点变成了「没有任何入边的节点」，那么就代表着这门课可以开始学习了。按照这样的流程，我们不断地将没有入边的节点加入答案，直到答案中包含所有的节点（得到了一种拓扑排序）或者不存在没有入边的节点（图中包含环）。
上面的想法类似于广度优先搜索，因此我们可以将广度优先搜索的流程与拓扑排序的求解联系起来。
我们使用一个队列来进行广度优先搜索。初始时，所有入度为 0 的节点都被放入队列中，它们就是可以作为拓扑排序最前面的节点，并且它们之间的相对顺序是无关紧要的。
在广度优先搜索的每一步中，我们取出队首的节点 u：
我们将 u 放入答案中；
我们移除 u 的所有出边，也就是将 u 的所有相邻节点的入度减少 1。如果某个相邻节点 v 的入度变为 0，那么我们就将 v 放入队列中。
在广度优先搜索的过程结束后。如果答案中包含了这 n 个节点，那么我们就找到了一种拓扑排序，否则说明图中存在环，也就不存在拓扑排序了。
Kahns 算法
时间复杂度: O(n+m)，其中 n 为课程数，m 为先修课程的要求数。这其实就是对图进行广度优先搜索的时间复杂度。
空间复杂度: O(n+m)。题目中是以列表形式给出的先修课程关系，为了对图进行广度优先搜索，我们需要存储成邻接表的形式，空间复杂度为 O(n+m)。在广度优先搜索的过程中，我们需要最多 O(n) 的队列空间（迭代）进行广度优先搜索。因此总空间复杂度为 O(n+m)。
class Solution {
List<List<Integer>> edges;
int[] indeg;
public boolean canFinish(int numCourses, int[][] prerequisites) {
edges = new ArrayList<List<Integer>>();
for (int i = 0; i < numCourses; ++i) {
edges.add(new ArrayList<Integer>());
}
indeg = new int[numCourses];
for (int[] info : prerequisites) {
edges.get(info[1]).add(info[0]);//表示课程的依赖关系图。edges.get(i) 存储的是所有必须在课程 i 之后完成的课程。
++indeg[info[0]];//indeg[i] 表示课程 i 有多少个前置课程
}
Queue<Integer> queue = new LinkedList<Integer>();
for (int i = 0; i < numCourses; ++i) {
if (indeg[i] == 0) {
queue.offer(i);
}
}
int visited = 0;
while (!queue.isEmpty()) {
++visited;
int u = queue.poll();
for (int v: edges.get(u)) {
--indeg[v];//在 --indeg[v]; 的过程中，v 的入度不一定会直接变为 0，只有在它的所有前置课程都完成时，入度才会变为 0
if (indeg[v] == 0) {
queue.offer(v);
}
}
}
return visited == numCourses;
}
}
208实现 Trie (前缀树)
Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。
请你实现 Trie 类：
Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。
Trie，又称前缀树或字典树，是一棵有根树，其每个节点包含以下字段：
指向子节点的指针数组 children。数组长度为 26，即小写英文字母的数量。此时 children[0] 对应小写字母 a，children[1] 对应小写字母 b，…，children[25] 对应小写字母 z。布尔字段 isEnd，表示该节点是否为字符串的结尾。
从字典树的根开始，插入字符串。对于当前字符对应的子节点，有两种情况：
子节点存在。沿着指针移动到子节点，继续处理下一个字符。
子节点不存在。创建一个新的子节点，记录在 children 数组的对应位置上，然后沿着指针移动到子节点，继续搜索下一个字符。
重复以上步骤，直到处理字符串的最后一个字符，然后将当前节点标记为字符串的结尾。
从字典树的根开始，查找前缀。对于当前字符对应的子节点，有两种情况：
子节点存在。沿着指针移动到子节点，继续搜索下一个字符。
子节点不存在。说明字典树中不包含该前缀，返回空指针。
重复以上步骤，直到返回空指针或搜索完前缀的最后一个字符。
若搜索到了前缀的末尾，就说明字典树中存在该前缀。此外，若前缀末尾对应节点的 isEnd 为真，则说明字典树中存在该字符串。
时间复杂度：初始化为 O(1)，其余操作为 O(∣S∣)，其中 ∣S∣ 是每次插入或查询的字符串的长度。
空间复杂度：O(∣T∣⋅Σ)，其中 ∣T∣ 为所有插入字符串的长度之和，Σ 为字符集的大小，本题 Σ=26。
class Trie {
private Trie[] children;
private boolean isEnd;
public Trie() {
children = new Trie[26];
isEnd = false;
}
public void insert(String word) {
Trie node = this;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
int index = ch - 'a';
if (node.children[index] == null) {
node.children[index] = new Trie();
}
node = node.children[index];
}
node.isEnd = true;
}
public boolean search(String word) {
Trie node = searchPrefix(word);
return node != null && node.isEnd;
}
public boolean startsWith(String prefix) {
return searchPrefix(prefix) != null;
}
private Trie searchPrefix(String prefix) {
Trie node = this;
for (int i = 0; i < prefix.length(); i++) {
char ch = prefix.charAt(i);
int index = ch - 'a';
if (node.children[index] == null) {
return null;
}
node = node.children[index];
}
return node;
}
}
73矩阵置零
给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
//可以用两个标记数组分别记录每一行和每一列是否有零出现，
//为了节省这一部分空间，可以用矩阵的第一行和第一列代替方法一中的两个标记数组
时间复杂度：O(mn)，其中 m 是矩阵的行数，n 是矩阵的列数。我们至多只需要遍历该矩阵两次。
空间复杂度：O(1)。我们只需要常数空间存储若干变量。
class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
boolean flagCol0 = false;
//第一列既用来标记行需要置零，又需要保存自己是否应该被置零的状态。
//假如在标记阶段直接修改第一列的值，往下遍历会导致标记混淆，无法区分第一列本身是否需要被置零。
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) {//判断每一行的第一列是否为0
flagCol0 = true;//第一列为0
}
//标记哪行哪列有0
for (int j = 1; j < n; j++) {//第二列开始，所在行的第一列元素 matrix[i][0] 和所在列的第一行元素 matrix[0][j] 置为零。
if (matrix[i][j] == 0) {
matrix[i][0] = matrix[0][j] = 0;
}
}
}
//先从最后一行开始遍历，这样可以避免影响未处理的行。
//对每个 matrix[i][j]，如果 matrix[i][0] == 0 或 matrix[0][j] == 0，那么 matrix[i][j] 被置为零。
//最后，根据 flagCol0 判断是否需要将第一列全部置零。
for (int i = m - 1; i >= 0; i--) {
for (int j = 1; j < n; j++) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
if (flagCol0) {
matrix[i][0] = 0;
}
}
}
}
54螺旋矩阵
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
示例 2：
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]
时间复杂度：O(mn)，其中 m 和 n 分别是输入矩阵的行数和列数。矩阵中的每个元素都要被访问一次。
空间复杂度：O(1)。除了输出数组以外，空间复杂度是常数。
可以将矩阵看成若干层，首先输出最外层的元素，其次输出次外层的元素，直到输出最内层的元素。
定义矩阵的第 k 层是到最近边界距离为 k 的所有顶点。
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> order = new ArrayList<Integer>();
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return order;
}
int rows = matrix.length, columns = matrix[0].length;
int left = 0, right = columns - 1, top = 0, bottom = rows - 1;
while (left <= right && top <= bottom) {
for (int column = left; column <= right; column++) {//扫描所有列0-columns - 1
order.add(matrix[top][column]);
}
for (int row = top + 1; row <= bottom; row++) {//扫描第一行最后一列到最后一行最后一列
order.add(matrix[row][right]);
}
if (left < right && top < bottom) {
for (int column = right - 1; column > left; column--) {//扫描最后一行逆序
order.add(matrix[bottom][column]);
}
for (int row = bottom; row > top; row--) {//扫描第一列逆序
order.add(matrix[row][left]);
}
}
left++;
right--;
top++;
bottom--;
}
return order;
}
}
59螺旋矩阵II
给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
示例:
输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]
//注意始终坚持左闭右开
class Solution {
public int[][] generateMatrix(int n) {
int[][] nums = new int[n][n];
int startX = 0, startY = 0; // 每一圈的起始点
int offset = 1;
int count = 1; // 矩阵中需要填写的数字
int loop = 1; // 记录当前的圈数
int i, j; // j 代表列, i 代表行;
while (loop <= n / 2) {
// 顶部
// 左闭右开，所以判断循环结束时， j 不能等于 n - offset
for (j = startY; j < n - offset; j++) {
nums[startX][j] = count++;
}
// 右列
// 左闭右开，所以判断循环结束时， i 不能等于 n - offset
for (i = startX; i < n - offset; i++) {
nums[i][j] = count++;
}
// 底部
// 左闭右开，所以判断循环结束时， j != startY
for (; j > startY; j--) {
nums[i][j] = count++;
}
// 左列
// 左闭右开，所以判断循环结束时， i != startX
for (; i > startX; i--) {
nums[i][j] = count++;
}
startX++;
startY++;
offset++;
loop++;
}
if (n % 2 == 1) { // n 为奇数时，单独处理矩阵中心的值
nums[startX][startY] = count;
}
return nums;
}
}
48旋转图像
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
时间复杂度：O(N^2)，其中 N 是 matrix 的边长。对于每一次翻转操作，我们都需要枚举矩阵中一半的元素。
空间复杂度：O(1)。为原地翻转得到的原地旋转。
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
// 水平翻转
for (int i = 0; i < n / 2; ++i) {
for (int j = 0; j < n; ++j) {
int temp = matrix[i][j];
matrix[i][j] = matrix[n - i - 1][j];
matrix[n - i - 1][j] = temp;
}
}
// 主对角线翻转
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
}
}
240搜索二维矩阵 II
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
时间复杂度：O(m+n)。在搜索的过程中，如果我们没有找到 target，那么我们要么将 y 减少 1，要么将 x 增加 1。由于 (x,y) 的初始值分别为 (0,n−1)，因此 y 最多能被减少 n 次，x 最多能被增加 m 次，总搜索次数为 m+n。在这之后，x 和 y 就会超出矩阵的边界。
空间复杂度：O(1)。
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length, n = matrix[0].length;
int x = 0, y = n - 1;
while (x < m && y >= 0) {
if (matrix[x][y] == target) {
return true;
}
if (matrix[x][y] > target) {
--y;
} else {
++x;
}
}
return false;
}
}
74搜索二维矩阵
给你一个满足下述两条属性的 m x n 整数矩阵：
每行中的整数从左到右按非严格递增顺序排列。
每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
时间复杂度：O(logmn)，其中 m 和 n 分别是矩阵的行数和列数。
空间复杂度：O(1)。
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length, n = matrix[0].length;
int low = 0, high = m * n - 1;
while (low <= high) {
int mid = (high - low) / 2 + low;
int x = matrix[mid / n][mid % n];
if (x < target) {
low = mid + 1;
} else if (x > target) {
high = mid - 1;
} else {
return true;
}
}
return false;
}
}