笔记之Leetcode螺旋矩阵问题

59 螺旋矩阵 II

原题链接:spiral matrix ii,先看下什么是螺旋矩阵:

1 2 3
8 9 4
7 6 5

即从起始位置顺时针从1递增填充直到 nn。
题目相当于是构建一个如上的 n
n 二维数组,在按照顺时针旋转的时候,我们可以使用循环,使(row, col) 不断的变化。而说到循环的话,就要抓住当前循环的变量,以及它的起始值和循环终止值。考虑到顺时针循环射击到上下左右四个方向,可以设置4个变量 top,right,bottom,left 用于循环的时候作为 row 或 col 的起始和终止条件。举例来说:

1 -> 2 -> 3

此时是从左往右,row 不变,为 top 的值;col 从 left 递增到 right。col 循环结束后,top 加 1——加1的目的是为了用于后面的循环。
接下来:

4 | 5

从上往下,col 不变,为right 的值;row 从 top 递增到 bottom。 row 循环解释后,right 减 1。
其余类推。

int** generateMatrix(int n, int* returnSize, int** returnColumnSizes){
    int **result = (int **)malloc(sizeof(int *) * n);
    *returnSize = n;  
    *returnColumnSizes = malloc(sizeof(int) * n);
    for(int i = 0; i < n; i ++) {
        result[i] = (int *)malloc(sizeof(int) * n);
        (*returnColumnSizes)[i] = n;
    }

    int i = 1, row = 0, col = 0;
    int left = 0, right = n - 1, top = 0, bottom = n - 1;
    while(i <= n * n) {
        //right
        for(col = left; col <= right; col++) {//col
            result[top][col] = i++;
        }
        top++;
        //to bottom
        for(row = top; row <= bottom;row++) { //row
            result[row][right] = i++;
        }
        right --;
        //to left
        for(col = right; col >= left; col--) { //col
            result[bottom ][col] = i++;
        }
        bottom--;
        //to up
        for(row = bottom; row >= top; row--) { //row
            result[row][left] = i++;
        }
        left ++;
    }
    return result;
}

54 螺旋矩阵

原题链接:spiral matrix,该题做法和59题类似,但54题不一样的地方在于是 mxn 的矩阵,按照顺时针螺旋顺序,返回矩阵中所有的元素。另外,当 while 对 i 递增时,函数题内需要对 left-right,top-bottom 的大小做比较,避免发生上下或左右的越界。
直接上代码:

//c
/**
 * 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 *result = (int *)malloc(sizeof(int) * (*returnSize));
    int i = 1, row = 0, col = 0;
    int top = 0, right = (*matrixColSize) - 1,  bottom = matrixSize - 1, left = 0;
    while(i <= (*returnSize)) {
        //to right
        for(col = left; col <= right; col ++){
            result[i - 1] = matrix[top][col];
            i++;
        }
        top ++;
        if(top > bottom) break;
        //to bottom
        for(row = top; row <= bottom; row ++) {
            result[i - 1] = matrix[row][right];
            i ++;
        }
        right --;
        if(right < left) break;
        //to left
        for(col = right; col >= left; col --) {
            result[i - 1] = matrix[bottom][col];
            i++;
        }
        bottom --;
        if(bottom < top) break;
        //to top
        for(row = bottom; row >= top; row --) {
            result[i - 1] = matrix[row][left];
            i++;
        }
        left ++;
        if(left > right) break;
    } 
    return result;
}