笔记之Leetcode螺旋矩阵问题

59 螺旋矩阵 II

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

1 2 3
8 9 4
7 6 5

即从起始位置顺时针从1递增填充直到 nn。
题目相当于是构建一个如上的 nn 二维数组，在按照顺时针旋转的时候，我们可以使用循环，使(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;
}

Comments

Categories

Tags