73. 矩阵置零
给定一个 m x n 的矩阵,如果一个元素为 0 ,则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
输入:matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出:[[1,0,1],[0,0,0],[1,0,1]]
关键在于:一次扫描全表记录为0的坐标,然后对记录的坐标整行整列赋值0
class Solution {public void setZeroes(int[][] matrix) {int n=matrix.length,m=matrix[0].length;int[] x=new int[202];int[] y=new int[202];int x1=0,y1=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(matrix[i][j]==0){//记录为0点的坐标x[x1++]=i;y[y1++]=j;System.out.println(i+j);}}}//记录的坐标for(int i=0;i<x1;i++){int xx=0;while(xx<m){//行=0matrix[x[i]][xx++]=0;}int yy=0;while(yy<n){//列=0System.out.println("yy"+yy+y[i]);int a=yy,b=y[i];// matrix[a][b]=0;matrix[yy][y[i]]=0;yy++;}}}
}
54. 螺旋矩阵
给你一个 m 行 n 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。
输入:matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出:[1,2,3,6,9,8,7,4,5]
class Solution {public List<Integer> spiralOrder(int[][] matrix) {List<Integer> list=new ArrayList<Integer>();int n=matrix.length,m=matrix[0].length;int[][] map = new int[n][m];int next[][]={{0,1},{1,0},{0,-1},{-1,0}};//右下左上顺时针int x=0,y=0,k=0;for(int i=1;i<=n*m;i++)//这个循环只是表明要走n*n步而已{list.add(matrix[x][y]);map[x][y]=-1;//访问后标记int tx=x+next[k][0];int ty=y+next[k][1];//下一个位置if(tx<0||ty<0||tx>=n||ty>=m||map[tx][ty]==-1)//下一个位置到达边界条件{k=(k+1)%4;//转换方向tx=x+next[k][0];//新的下一位置ty=y+next[k][1];}x=tx;y=ty;//确定的下一步的位置}return list;}
}
59. 螺旋矩阵 II
给你一个正整数 n ,生成一个包含 1 到 n2 所有元素,且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
输入:n = 3
输出:[[1,2,3],[8,9,4],[7,6,5]]
本质就是模拟填数的过程。
但一下代码耗时长
class Solution {public int[][] generateMatrix(int n) {int[][] map = new int[n][n];int x=0,y=0,k=0;int[][] next={{0,1},{1,0},{0,-1},{-1,0}};//转向顺序:右、下、左、上for(int i=1;i<=n*n;i++){System.out.println(x+"y"+y+"i"+i);map[x][y]=i;int tx=x+next[k][0];int ty=y+next[k][1];if(tx<0||ty<0||tx>=n||ty>=n||map[tx][ty]!=0){//转向k=(k+1)%4;tx=x+next[k][0];ty=y+next[k][1];}x=tx;y=ty;}return map;}
}
48. 旋转图像
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像,这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
输入:matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出:[[7,4,1],[8,5,2],[9,6,3]]
关键在于:找到规律,进行先矩阵转置(就是[i][j],[j][i]互换),再左右对称的两列互换。
class Solution {public void rotate(int[][] matrix) {//先矩阵转置,再左右对称的两列互换int n=matrix.length;//转置(i,j互换)for(int i=0;i<n;i++){//对一半进行操作for(int j=0;j<i;j++){int tmp = matrix[i][j];matrix[i][j]=matrix[j][i];matrix[j][i]=tmp;}}//交换两列for(int i=0;i<n;i++){for(int j=0;j<n/2;j++){int tmp = matrix[i][j];matrix[i][j]=matrix[i][n-1-j];matrix[i][n-1-j]=tmp;}}}
}
240. 搜索二维矩阵 II
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性:
每行的元素从左到右升序排列。
每列的元素从上到下升序排列
输入:matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出:true
从右上角看是一颗二叉搜索树
然后就二分查找。
class Solution {public boolean searchMatrix(int[][] matrix, int target) {//[i+1][j],[i][j+1]< [i+1][j+1]int n=matrix.length,m=matrix[0].length;int i=0,j=m-1;//从右上角开始while(i<n&&j>=0){if(matrix[i][j]==target) return true;if(target>matrix[i][j])i++;else j--;}return false;}
}
注:一开始由于我总想着通过关键点[i+1]][j+1]的比较,来找到特定的行和列,而导致错误,实际上不能确定行列只能排除左上角。
74. 搜索二维矩阵
给你一个满足下述两条属性的 m x n 整数矩阵:
每行中的整数从左到右按非严格递增顺序排列。
每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ,如果 target 在矩阵中,返回 true ;否则,返回 false 。
输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出:true
做完上题再看这题,很自然就从右上角看到了二叉搜索树,按照同样的思路用二分查找。
class Solution {public boolean searchMatrix(int[][] matrix, int target) {//非严格递增就是可以相等int n=matrix.length,m=matrix[0].length;int i=0,j=m-1;//从右上角开始while(i<n&&j>=0){if(matrix[i][j]==target) return true;if(target>matrix[i][j])i++;else j--;}return false;}
}