算法题--按顺时针顺序填充二维数组

image.png

0. 链接

题目链接

1. 题目

Given a positive integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

Example:

Input: 3
Output:
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

2. 思路1：模拟NPC走格子

记录四个端点的位置left,right,top,bottom，四个方向右下左上，先从左到右，再从上到下，然后从右到左，最后从下到上，

终止条件为 left > right 或者 top > bottom, 表示没有格子需要处理了 

3. 代码

# coding:utf8
from typing import List


class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        DIRECTION_RIGHT = 1
        DIRECTION_DOWN = 2
        DIRECTION_LEFT = 3
        DIRECTION_UP = 4

        left = 0
        right = n - 1
        top = 0
        bottom = n - 1

        array = [[0] * n for _ in range(n)]

        value = 1
        i = 0
        j = 0
        array[i][j] = value
        direction = DIRECTION_RIGHT

        while left <= right and top <= bottom:
            if direction == DIRECTION_RIGHT:
                if j < right:
                    j += 1
                    value += 1
                    array[i][j] = value
                else:
                    direction = DIRECTION_DOWN
                    top += 1
            elif direction == DIRECTION_DOWN:
                if i < bottom:
                    i += 1
                    value += 1
                    array[i][j] = value
                else:
                    direction = DIRECTION_LEFT
                    right -= 1
            elif direction == DIRECTION_LEFT:
                if j > left:
                    j -= 1
                    value += 1
                    array[i][j] = value
                else:
                    direction = DIRECTION_UP
                    bottom -= 1
            elif direction == DIRECTION_UP:
                if i > top:
                    i -= 1
                    value += 1
                    array[i][j] = value
                else:
                    direction = DIRECTION_RIGHT
                    left += 1

        return array


def print_matrix(matrix):
    for each_list in matrix:
        print(each_list)

    print('=' * 50)


solution = Solution()
print_matrix(solution.generateMatrix(3))
print_matrix(solution.generateMatrix(5))

输出结果

[1, 2, 3]
[8, 9, 4]
[7, 6, 5]
==================================================
[1, 2, 3, 4, 5]
[16, 17, 18, 19, 6]
[15, 24, 25, 20, 7]
[14, 23, 22, 21, 8]
[13, 12, 11, 10, 9]
==================================================

4. 结果

image.png