Java - LeetCode面试经典150题 - 矩阵 (四)
矩阵
36. 有效的数独
题目
请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
注意：
一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
空白格用 '.' 表示。
提示：
board.length == 9
board[i].length == 9
board[i][j] 是一位数字（1-9）或者 '.'
示例 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) {
boolean[] vis=new boolean[10];
// 判断 一行
for (int i=0;i<9;i++){
Arrays.fill(vis,false);
for (int j=0;j<9;j++){
if (board[i][j]=='.') continue;
int c=board[i][j]-'0';
if (vis[c]) return false;
vis[c]=true;
}
}
// 判断 一列
for (int j=0;j<9;j++){
Arrays.fill(vis,false);
for (int i=0;i<9;i++){
if (board[i][j]=='.') continue;
int c=board[i][j]-'0';
if (vis[c]) return false;
vis[c]=true;
}
}
// 判断 九宫格
for (int l=0;l<9;l +=3){
for (int r=0;r<9;r +=3){
Arrays.fill(vis,false);
for (int i=l;i<l+3;i++){
for (int j=r;j<r+3;j++){
if (board[i][j]=='.') continue;
int c=board[i][j]-'0';
if (vis[c]) return false;
vis[c]=true;
}
}
}
}
return true;
}
}
54. 螺旋矩阵
题目
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
提示：
m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100
示例 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) {
int n=matrix.length;
int m=matrix[0].length;
boolean[][] vis=new boolean[n][m];
int cnt=n*m;
List<Integer> res=new ArrayList<>();
int i=0,j=-1;
while (true){
if (cnt==0) break;
while (j+1<m&&!vis[i][j+1]){
res.add(matrix[i][j+1]);
vis[i][j+1]=true;
cnt--;
j++;
}
while (i+1<n&&!vis[i+1][j]){
res.add(matrix[i+1][j]);
vis[i+1][j]=true;
cnt--;
i++;
}
while (j-1>=0&&!vis[i][j-1]){
res.add(matrix[i][j-1]);
vis[i][j-1]=true;
cnt--;
j--;
}
while (i-1>=0&&!vis[i-1][j]){
res.add(matrix[i-1][j]);
vis[i-1][j]=true;
cnt--;
i--;
}
}
return res;
}
}
48. 旋转图像
题目
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
提示：
n == matrix.length == matrix[i].length
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]
示例 2：
输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
解析：
进行两次对称即可完成图像顺时针旋转90度
先将图像按照左上角到右下角的对角线进行对称
然后将新图像按照中间的竖线进行对称即可完成
代码：
class Solution {
public static void rotate(int[][] matrix) {
int n=matrix.length;
for (int i=0;i<n;i++)
for (int j=i;j<n;j++){
int t=matrix[i][j];
matrix[i][j]=matrix[j][i];
matrix[j][i]=t;
}
// for (int i=0;i<n;i++){
// for (int j=0;j<n;j++) System.out.print(matrix[i][j]+" ");
// System.out.println();
// }
for (int l=0,r=n-1;l<r;l++,r--){
for (int i=0;i<n;i++){
int t=matrix[i][l];
matrix[i][l]=matrix[i][r];
matrix[i][r]=t;
}
}
// for (int i=0;i<n;i++){
// for (int j=0;j<n;j++) System.out.print(matrix[i][j]+" ");
// System.out.println();
// }
}
}
73. 矩阵置零
题目
给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
提示：
m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-2^31 <= matrix[i][j] <= 2^31 - 1
示例 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]]
解析：
根据题意是将元素为0位置的所在的行和列的所有元素置为0，但要注意是原元素，变化后为0的元素，不包括在内。
所以需要将原元素为0的元素挑出，再进行置0操作。
代码：
class Solution {
public static void setZeroes(int[][] matrix) {
int n=matrix.length;
int m=matrix[0].length;
List<int[]> res=new ArrayList<>();
for (int i=0;i<n;i++){
for (int j=0;j<m;j++){
if (matrix[i][j]==0){
int[] a=new int[2];
a[0]=i;
a[1]=j;
res.add(a);
}
}
}
boolean[] vis1=new boolean[n];
boolean[] vis2=new boolean[m];
for (int[] a:res){
int i=a[0],j=a[1];
if (!vis1[i]){
for (int r=0;r<m;r++) matrix[i][r]=0;
vis1[i]=true;
}
if (!vis2[j]){
for (int l=0;l<n;l++) matrix[l][j]=0;
vis2[j]=true;
}
}
// for (int i=0;i<n;i++){
// for (int j=0;j<m;j++)
// System.out.print(matrix[i][j]+" ");
// System.out.println();
// }
}
}
289. 生命游戏
题目
根据 百度百科 ， 生命游戏 ，简称为 生命 ，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。
给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态： 1 即为 活细胞 （live），或 0 即为 死细胞 （dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：
如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。给你 m x n 网格面板 board 的当前状态，返回下一个状态。
提示：
m == board.length
n == board[i].length
1 <= m, n <= 25
board[i][j] 为 0 或 1
示例 1：
输入：board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
输出：[[0,0,0],[1,0,1],[0,1,1],[0,1,0]]
示例 2：
输入：board = [[1,1],[1,0]]
输出：[[1,1],[1,1]]
解析：
按照题意进行模拟即可，但是要注意，所有的点的状态都是需要同时被更新的，所以每个点的状态的判断都是通过原二维数组的状态判断的。
代码：
class Solution {
public void gameOfLife(int[][] board) {
int n=board.length;
int m=board[0].length;
int[][] a=new int[n][m];
for (int i=0;i<n;i++){
for (int j=0;j<m;j++){
int cnt=0;
for (int l=i-1;l<=i+1;l++)
for (int r=j-1;r<=j+1;r++){
if (l==i&&r==j)continue;
if (l<0||l>=n) continue;
if (r<0||r>=m) continue;
if (board[l][r]==1) cnt++;
}
if (cnt<2) a[i][j]=0;
else if (cnt==2) a[i][j]=board[i][j];
else if (cnt==3) a[i][j]=1;
else a[i][j]=0;
}
}
for (int i=0;i<n;i++)
for (int j=0;j<m;j++)
board[i][j]=a[i][j];
}
}