文章目录
- 76.【困难】最小覆盖子串
- 36.【中等】有效的数独
- 54.【中等】螺旋矩阵
- 48.【中等】旋转图像
- 73.【中等】矩阵置零
🌈你好呀！我是 山顶风景独好
💝欢迎来到我的博客，很高兴能够在这里和您见面！
💝希望您在这里可以感受到一份轻松愉快的氛围！
💝不仅可以获得有趣的内容和知识，也可以畅所欲言、分享您的想法和见解。
🚀 欢迎一起踏上探险之旅，挖掘无限可能，共同成长！
76.【困难】最小覆盖子串
- 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
注意：- 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
- 如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 ：
- 输入：s = “ADOBECODEBANC”, t = “ABC”
- 输出：“BANC”
- 解释：最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、‘B’ 和 ‘C’。
class Solution { // 定义一个公共方法，用于找到包含t的最短子串 public String minWindow(String S, String t) { // 将S转换为字符数组，方便后续操作 char[] s = S.toCharArray(); int m = s.length; // S的长度 // 初始化答案的左右边界，初始值使得最后返回的字符串为空字符串 int ansLeft = -1; int ansRight = m; // 定义滑动窗口的左边界 int left = 0; // less表示在t中但当前在s的窗口中出现次数还不足的字符数量 int less = 0; // 初始化两个数组，用于记录s和t中每个字符的出现次数 int[] cntS = new int[128]; // s 子串字母的出现次数 int[] cntT = new int[128]; // t 中字母的出现次数 // 遍历t中的每个字符，初始化cntT数组和less变量 for (char c : t.toCharArray()) { if (cntT[c]++ == 0) { less++; // 如果t中某个字符第一次出现，则less加1 } } // 遍历S，通过移动右边界来扩展窗口 for (int right = 0; right < m; right++) { // 移动子串右端点 char c = s[right]; // 右端点字母（移入子串） // 如果s中当前字符c的出现次数增加到与t中相同，说明less可以减1 if (++cntS[c] == cntT[c]) { less--; // c 的出现次数从 < 变成 >= } // 当窗口内的字符都满足在t中的出现次数时（less == 0），尝试收缩窗口 while (less == 0) { // 涵盖：所有字母的出现次数都是 >= // 如果当前窗口比之前的答案更短，则更新答案 if (right - left < ansRight - ansLeft) { // 找到更短的子串 ansLeft = left; // 记录此时的左右端点 ansRight = right; } // 移动左边界，尝试缩小窗口 char x = s[left++]; // 左端点字母（移出子串） // 如果移出的字符x在s中的出现次数小于t中，说明less需要加1 if (cntS[x]-- == cntT[x]) { less++; // x 的出现次数从 >= 变成 < } // 当less不再为0时，说明窗口内已不满足包含t的所有字符，退出循环 } } // 如果ansLeft仍然为-1，说明S中不包含t，返回空字符串；否则返回最短子串 return ansLeft < 0 ? "" : S.substring(ansLeft, ansRight + 1); }
}
36.【中等】有效的数独
请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
- 数字 1-9 在每一行只能出现一次。
- 数字 1-9 在每一列只能出现一次。
- 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
注意：
- 一个有效的数独（部分已被填充）不一定是可解的。
- 只需要根据以上规则，验证已经填入的数字是否有效即可。
- 空白格用 ‘.’ 表示。
示例 1：
- 输入：board =
[[“5”,“3”,“.”,“.”,“7”,“.”,“.”,“.”,“.”]
,[“6”,“.”,“.”,“1”,“9”,“5”,“.”,“.”,“.”]
,[“.”,“9”,“8”,“.”,“.”,“.”,“.”,“6”,“.”]
,[“8”,“.”,“.”,“.”,“6”,“.”,“.”,“.”,“3”]
,[“4”,“.”,“.”,“8”,“.”,“3”,“.”,“.”,“1”]
,[“7”,“.”,“.”,“.”,“2”,“.”,“.”,“.”,“6”]
,[“.”,“6”,“.”,“.”,“.”,“.”,“2”,“8”,“.”]
,[“.”,“.”,“.”,“4”,“1”,“9”,“.”,“.”,“5”]
,[“.”,“.”,“.”,“.”,“8”,“.”,“.”,“7”,“9”]]- 输出：true
示例 2：
- 输入：board =
[[“8”,“3”,“.”,“.”,“7”,“.”,“.”,“.”,“.”]
,[“6”,“.”,“.”,“1”,“9”,“5”,“.”,“.”,“.”]
,[“.”,“9”,“8”,“.”,“.”,“.”,“.”,“6”,“.”]
,[“8”,“.”,“.”,“.”,“6”,“.”,“.”,“.”,“3”]
,[“4”,“.”,“.”,“8”,“.”,“3”,“.”,“.”,“1”]
,[“7”,“.”,“.”,“.”,“2”,“.”,“.”,“.”,“6”]
,[“.”,“6”,“.”,“.”,“.”,“.”,“2”,“8”,“.”]
,[“.”,“.”,“.”,“4”,“1”,“9”,“.”,“.”,“5”]
,[“.”,“.”,“.”,“.”,“8”,“.”,“.”,“7”,“9”]]- 输出：false
- 解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
class Solution { public boolean isValidSudoku(char[][] board) { // 初始化9x9的行标记数组，用于记录每行中每个数字出现的次数 int[][] rows = new int[9][9]; // 初始化9x9的列标记数组，用于记录每列中每个数字出现的次数 int[][] columns = new int[9][9]; // 初始化3x3x9的子盒子标记数组，用于记录每个3x3子盒子中每个数字出现的次数 int[][][] subboxes = new int[3][3][9]; // 遍历9x9的棋盘 for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { // 获取当前位置的字符 char c = board[i][j]; // 如果当前位置不是空（'.'表示空） if (c != '.') { // 将字符转换为数字索引（'1'-'0' = 1, '2'-'0' = 2, ..., '9'-'0' = 8） // 然后减1，因为数组索引是从0开始的 int index = c - '0' - 1; // 在当前行中标记该数字出现一次 rows[i][index]++; // 在当前列中标记该数字出现一次 columns[j][index]++; // 计算当前位置所属的3x3子盒子的索引 // i/3 和 j/3 分别表示子盒子的行和列索引（0-2） // 然后在该子盒子中标记该数字出现一次 subboxes[i / 3][j / 3][index]++; // 检查当前行、列和子盒子中是否有数字重复出现（即出现次数大于1） // 如果有，则返回false，表示这不是一个有效的数独 if (rows[i][index] > 1 || columns[j][index] > 1 || subboxes[i / 3][j / 3][index] > 1) { return false; } } } } // 如果遍历完整个棋盘都没有发现重复的数字，则返回true，表示这是一个有效的数独 return true; }
}
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]
class Solution { public List<Integer> spiralOrder(int[][] matrix) { // 创建一个空的ArrayList，用于存储遍历到的元素 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++) { order.add(matrix[top][column]); // 将当前元素添加到结果列表中 } // 从上到下遍历右边界（注意，从top+1开始，因为上边界已经遍历过了） for (int row = top + 1; row <= bottom; row++) { // 从top+1开始，避免重复添加上边界的元素 order.add(matrix[row][right]); // 将当前元素添加到结果列表中 } // 如果内部还有未遍历的元素（即不是只有一行或一列的情况） if (left < right && top < bottom) { // 从右到左遍历下边界（注意，从right-1开始，因为右边界已经遍历过了） for (int column = right - 1; column > left; column--) { // 从right-1开始，避免重复添加右边界的元素 order.add(matrix[bottom][column]); // 将当前元素添加到结果列表中 } // 从下到上遍历左边界（注意，此时bottom和left的边界已经更新，可以安全遍历） for (int row = bottom; row > top; row--) { // 从bottom开始，避免重复添加下边界的元素 order.add(matrix[row][left]); // 将当前元素添加到结果列表中 } } // 更新四个边界，向内缩小一圈 left++; right--; top++; bottom--; } // 返回遍历后的结果列表 return order; }
}
48.【中等】旋转图像
- 给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
- 你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
示例 ：
- 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
- 输出：[[7,4,1],[8,5,2],[9,6,3]]
class Solution { public void rotate(int[][] matrix) { // 获取矩阵的行数（也是列数，因为矩阵是方阵） int n = matrix.length; // 外层循环，每次处理矩阵的一个“圈”。 // 因为矩阵是n*n的，所以只需要处理到n/2即可（包含中间那行/列如果n是奇数） for (int i = 0; i < n / 2; i++) { // 内层循环，每次处理当前“圈”的一行。 // 因为矩阵是对称的，所以只需要处理到(n+1)/2即可（当n是奇数时，中间的列已经在外层循环中处理过了） for (int j = 0; j < (n + 1) / 2; j++) { // 暂存matrix[i][j]的值 int tmp = matrix[i][j]; // 顺时针旋转90度，替换matrix[i][j]为右下角的值 matrix[i][j] = matrix[n - 1 - j][i]; // 替换右下角的值为左下角的值 matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j]; // 替换左下角的值为左上角的值 matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i]; // 替换左上角的值为暂存的值（即原matrix[i][j]的值），完成一个顺时针90度的旋转 matrix[j][n - 1 - i] = tmp; } } }
}
73.【中等】矩阵置零
给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
示例 1：
- 输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
- 输出：[[1,0,1],[0,0,0],[1,0,1]]
示例 2：
- 输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
- 输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]
class Solution { public void setZeroes(int[][] matrix) { // 获取矩阵的行数和列数 int m = matrix.length; // 矩阵的行数 int n = matrix[0].length; // 矩阵的列数（假设矩阵不为空） // 定义两个布尔数组，用于记录每一行和每一列是否含有0 boolean[] row = new boolean[m]; // 标记行是否有0 boolean[] col = new boolean[n]; // 标记列是否有0 // 遍历矩阵，检查每一元素是否为0，并设置对应行和列的标记 for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j] == 0) { // 如果找到0，则标记当前行和当前列为有0 row[i] = true; col[j] = true; } } } // 再次遍历矩阵，根据行和列的标记，将对应位置的元素置为0 for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { // 如果当前行或当前列被标记为有0，则置当前位置为0 if (row[i] || col[j]) { matrix[i][j] = 0; } } } }
}