春招冲刺百题计划|矩阵
Java基础复习
第一题：螺旋矩阵（多复习，谨记这不是子问题，而是走到不能再走才结束这个方向）
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
//学一下大神的简洁代码，作者：Rikka
List<Integer> ans = new ArrayList<>();
//能够直接给出答案（走不了）的情况
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return ans;
int u = 0, d = matrix.length - 1;
int l = 0, r = matrix[0].length - 1;
while (true) {
for (int i = l; i <= r; i++) { // 左->右
ans.add(matrix[u][i]);
}
//没有可走的行了
if (++u > d) break;
for (int i = u; i <= d; i++) { // 上->下
ans.add(matrix[i][r]);
}
//没有可走的列了
if (--r < l) break;
for (int i = r; i >= l; i--) { // 右->左
ans.add(matrix[d][i]);
}
if (--d < u) break;
for (int i = d; i >= u; i--) { // 下->上
ans.add(matrix[i][l]);
}
if (++l > r) break;
}
return ans;
}
}
第二题：生命游戏（增加状态实现在原始矩阵上进行操作，位运算的妙处）
class Solution {
public void gameOfLife(int[][] board) {
//在原地处理的思路：拓展状态（原来的活细胞现在死了，原来的死细胞现在活了）（有大神直接利用位运算来处理状态的记录，
//相当于将这个board拓展成了多维数组，真的太强了，作者：自在飞花）
if(board.length==0||board[0].length==0){
return;
}
int rows[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int cols[] = {-1, 0, 1, -1, 1, -1, 0, 1};
for(int i=0; i<board.length; i++){
for(int j=0; j<board[0].length; j++){
int sum=0;
for(int k=0; k<rows.length; k++){
if(i+rows[k]>=0&&i+rows[k]<board.length&&j+cols[k]>=0&&j+cols[k]<board[0].length){
sum += board[i+rows[k]][j+cols[k]]&1;
}
}
if(board[i][j]==1){
if(sum==2||sum==3)
board[i][j] |= 2;
}else{
if(sum==3)
board[i][j] |= 2;
}
}
}
for(int i=0; i<board.length; i++){
for(int j=0; j<board[0].length; j++){
board[i][j] >>= 1; //右移一位，用第二bit覆盖第一个bit。
}
}
}
//很简单的模拟。不能再原地处理，但是题目希望你在原地处理。
// if(board.length==0||board[0].length==0){
// return;
// }
// int rows[] = {-1, -1, -1, 0, 0, 1, 1, 1};
// int cols[] = {-1, 0, 1, -1, 1, -1, 0, 1};
// int newBoard[][] = new int[board.length][board[0].length];
// for(int i=0; i<board.length; i++){
// for(int j=0; j<board[0].length; j++){
// newBoard[i][j] = board[i][j];
// }
// }
// for(int i=0; i<board.length; i++){
// for(int j=0; j<board[0].length; j++){
// int sum=0;
// for(int k=0; k<rows.length; k++){
// if(i+rows[k]>=0&&i+rows[k]<board.length&&j+cols[k]>=0&&j+cols[k]<board[0].length){
// sum += newBoard[i+rows[k]][j+cols[k]];
// }
// }
// if(newBoard[i][j]==0&&sum==3){
// board[i][j] = 1;
// }
// if(newBoard[i][j]==1&&sum<2){
// board[i][j] = 0;
// }
// if(newBoard[i][j]==1&&(sum==3||sum==2)){
// board[i][j] = 1;
// }
// if(newBoard[i][j]==1&&sum>3){
// board[i][j] = 0;
// }
// }
// }
}
第三题：旋转图像（越简单的要求越要命呀）
class Solution {
public void rotate(int[][] matrix) {
//自己想不出来，还是用的leetcode官方给出的解题思路，觉得自己好垃圾哦，根本就是一个垃圾。
//创建辅助数组
//遍历原来的数组，赋值条件【newMatrix[col][n−row−1]=matrix[row][col]】
int[][] newMatrix = new int[matrix.length][matrix[0].length];
for(int i=0; i<matrix.length; i++){
for(int j=0; j<matrix[0].length; j++){
newMatrix[j][matrix[0].length-i-1] = matrix[i][j];
}
}
for(int i=0; i<matrix.length; i++){
for(int j=0; j<matrix[0].length; j++){
matrix[i][j] = newMatrix[i][j];
}
}
//如果需要原地实现的话，需要比较复杂的推导过程，最后得到一个循环的公式，实现1的控件复杂度。
}
}
第四题：矩阵置零
非常粗暴的用map记录下来。
class Solution {
public void setZeroes(int[][] matrix) {
//感觉可以用增加状态的方法写：不行哦，因为并不是0-1
//那我应该怎么办？其实原地最大的问题是要区分原来的0和后来设置的0。
//我可不可以记录行号和列号，利用map。
Map<Integer, Integer> rows = new HashMap<>();
Map<Integer, Integer> cols = new HashMap<>();
rows.clear();
cols.clear();
for(int i=0; i<matrix.length; i++){
for(int j=0; j<matrix[0].length; j++){
if(matrix[i][j]==0){
if(!rows.containsKey(i)){
rows.put(i, 1);
}
if(!cols.containsKey(j)){
cols.put(j, 1);
}
}
}
}
System.out.println(rows);
System.out.println(cols);
for (Integer i : rows.keySet()) {
for(int j=0; j<matrix[0].length; j++){
matrix[i][j]=0;
}
}
for (Integer j : cols.keySet()) {
for(int i=0; i<matrix.length; i++){
matrix[i][j]=0;
}
}
}
}
我这样做和重新搞一个矩阵没什么区别。
题解的方法，在空间优化上是使用了原本矩阵的第0行和第0列作为标记数组。
class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
boolean flagCol0 = false, flagRow0 = false;
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) {
flagCol0 = true;
}
}
for (int j = 0; j < n; j++) {
if (matrix[0][j] == 0) {
flagRow0 = true;
}
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = matrix[0][j] = 0;
}
}
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}
if (flagCol0) {
for (int i = 0; i < m; i++) {
matrix[i][0] = 0;
}
}
if (flagRow0) {
for (int j = 0; j < n; j++) {
matrix[0][j] = 0;
}
}
}
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/set-matrix-zeroes/solutions/669901/ju-zhen-zhi-ling-by-leetcode-solution-9ll7/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
原文地址：https://blog.csdn.net/anncyuyan/article/details/137527639
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！