hot100|矩阵|C语言

73. 矩阵置零 – 力扣（LeetCode）

标记数组

void setZeroes(int** matrix, int matrixSize, int* matrixColSize) {
    // 记录要置零的行和列
    int rowZero[matrixSize];
    int colZero[*matrixColSize];
    for(int i=0;i<matrixSize;++i){
        rowZero[i]=0;
    }
    for(int j=0;j<*matrixColSize;++j){
        colZero[j]=0;
    }

    for(int i=0;i<matrixSize;++i){
        for(int j=0;j<*matrixColSize;++j){
            if(matrix[i][j]==0){
                rowZero[i]=1;
                colZero[j]=1;
            }
        }
    }
    for(int i=0;i<matrixSize;++i){
        if(rowZero[i]==1){
            for(int j=0;j<*matrixColSize;++j){
                matrix[i][j]=0;
            }
        }
    }
    for(int j=0;j<*matrixColSize;++j){
        if(colZero[j]==1){
            for(int i=0;i<matrixSize;++i){
                matrix[i][j]=0;
            }
        }
    }
    return;
}

两个标记变量优化空间

void setZeroes(int** matrix, int matrixSize, int* matrixColSize) {
    // 使用两个标记变量存储第一行和第一列是否存在0
    // 使用数组第一行和第一列存储矩阵除去第一行第一列是否存在0
    // 第一行是否存在0
    bool row0_Exist0=false;
    for(int j=0;j<*matrixColSize;++j){
        if(matrix[0][j]==0){
            row0_Exist0=true;
            break;
        }    
    }
    // 第一列是否存在0
    bool col0_Exist0=false;
    for(int i=0;i<matrixSize;++i){
        if(matrix[i][0]==0){
            col0_Exist0=true;
            break;
        }
    }
    // 矩阵除去第一行第一列是否存在0
    for(int i=1;i<matrixSize;++i){
        for(int j=1;j<*matrixColSize;++j){
            if(matrix[i][j]==0){
                matrix[i][0]=0;
                matrix[0][j]=0;
            }
        }
    }
    // 更新矩阵除去第一行第一列部分
    for(int i=1;i<matrixSize;++i){
        for(int j=1;j<*matrixColSize;++j){
            if(matrix[i][0]==0 || matrix[0][j]==0){
                matrix[i][j]=0;
            }
        }
    }
    // 更新矩阵第一行
    if(row0_Exist0){
        for(int j=0;j<*matrixColSize;++j){
            matrix[0][j]=0;
        }
    }
    // 更新矩阵第一列
    if(col0_Exist0){
        for(int i=0;i<matrixSize;++i){
            matrix[i][0]=0;
        }
    }
    return;
}

54. 螺旋矩阵 – 力扣（LeetCode）

模拟

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* spiralOrder(int** matrix, int matrixSize, int* matrixColSize, int* returnSize) {
    // 模拟
    *returnSize=matrixSize*(*matrixColSize);
    int *res=(int *)malloc(*returnSize*sizeof(int));
    if(res==NULL){

        return NULL;
    }
    int top=0,bottom=matrixSize-1;
    int left=0,right=*matrixColSize-1;
    int idx=0;
    while(idx<*returnSize){
        // 向右转
        for(int j=left;j<=right && idx < *returnSize;++j){
            res[idx++]=matrix[top][j];
        }
        ++top;
        // 向下转
        for(int i=top;i<=bottom && idx < *returnSize;++i){
            res[idx++]=matrix[i][right];
        }
        --right;
        // 向左转
        for(int j=right;j>=left && idx < *returnSize;--j){
            res[idx++]=matrix[bottom][j];
        }
        --bottom;
        // 向上转
        for(int i=bottom;i>=top && idx < *returnSize;--i){
            res[idx++]=matrix[i][left];
        }
        ++left;
    }
    return res;
}

48. 旋转图像 – 力扣（LeetCode）

分解基本操作

// 交换
void swap(int *a,int *b){
    int tmp=*a;
    *a=*b;
    *b=tmp;
    return;
}

// 水平翻转
void flipMatrix_Horizontal(int** matrix, int rowNum, int colNum) {
    for(int i=0;i<rowNum/2;++i){
        for(int j=0;j<colNum;++j){
            swap(&matrix[i][j],&matrix[rowNum-1-i][j]);
        }
    }
    return;
}

// 主对角线翻转
void flipMatrix_MainDiagonal(int** matrix, int rowNum, int colNum){
    for(int i=0;i<rowNum-1;++i){
        for(int j=i+1;j<colNum;++j){
            swap(&matrix[i][j],&matrix[j][i]);
        }
    }
}

void rotate(int** matrix, int matrixSize, int* matrixColSize) {
    // 水平翻转+主对角线翻转=顺时针旋转90度
    int rowNum=matrixSize,colNum=*matrixColSize;
    flipMatrix_Horizontal(matrix,rowNum,colNum);
    flipMatrix_MainDiagonal(matrix,rowNum,colNum);
    return;    
}

240. 搜索二维矩阵 II – 力扣（LeetCode）

暴力枚举

bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target){
    // 遍历
    bool res=false;
    for(int i=0;i<matrixSize;++i){
        for(int j=0;j<*matrixColSize;++j){
            if(matrix[i][j]==target){
                res=true;
                break;
            }
        }
    }
    return res;
}

Z字查找 类二叉搜索树

bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target){
    // 类二叉搜索树 Z字查找
    bool res=false;
    int m=matrixSize,n=*matrixColSize;
    int i=0,j=n-1;
    while(i<m && j>=0){
        if(matrix[i][j]==target){
            res=true;
            break;
        }else if(matrix[i][j]>target){
            --j;
        }else{
            ++i;
        }
    }
    return res;
}