1.题目
问题描述
小C发现了一种奇特的图案，叫做螺旋阵列。它由一串0和1组成，看起来像一个由外向内旋转的图形。小C想知道，能否根据给定的宽度来生成这样一个螺旋图案。
例如，宽度为5时的螺旋阵列如下：
11111
00001
11101
10001
11111宽度为10时的螺旋阵列如下：
1111111111
0000000001
1111111101
1000000101
1011110101
1010010101
1010000101
1011111101
1000000001
1111111111小C想知道，对于任意给定的宽度 n，是否能生成对应的螺旋图案，并且以一个二维数组的形式输出。
测试样例
样例1：
输入：width = 5
输出：
[[1, 1, 1, 1, 1], [0, 0, 0, 0, 1], [1, 1, 1, 0, 1], [1, 0, 0, 0, 1], [1, 1, 1, 1, 1]]
样例2：
输入：width = 8
输出：
[[1, 1, 1, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0, 0, 1], [1, 1, 1, 1, 1, 1, 0, 1], [1, 0, 0, 0, 0, 1, 0, 1], [1, 0, 1, 0, 0, 1, 0, 1], [1, 0, 1, 1, 1, 1, 0, 1], [1, 0, 0, 0, 0, 0, 0, 1], [1, 1, 1, 1, 1, 1, 1, 1]]
样例3：
输入：width = 2
输出：
[[1, 1], [0, 1]]
2.思路
有点类似Leecode的螺旋矩阵
1. 递归分解问题
- 由于螺旋矩阵具有明显的层次结构，每一层都可以看作是一个“边框”或者“外圈”围绕着内部矩阵。因此，我们从一个较小的螺旋矩阵开始，逐步递归地构建较大的矩阵。
- 当宽度为
n时，我们可以通过递归调用solution(n-2)生成宽度为n-2的矩阵，然后将它扩展成宽度为n的矩阵。
2. 处理特殊情况
- 对于最小的几个情况（宽度为2或3），直接返回对应的矩阵，这样避免了递归中不断拆解出这些特例。
width = 2时是最简单的矩阵，直接返回[ [1, 1], [0, 1] ]。width = 3时返回[ [1, 1, 1], [0, 0, 1], [1, 1, 1] ]。
3. 构建矩阵
- 对于较大的宽度，通过递归生成一个更小的矩阵（
base），然后将其边框外扩展：- 首先，初始化矩阵的两行，第一行是全1，第二行所有元素为0，最后一个元素为1。
- 然后，通过倒序遍历并反转小矩阵
base的每一行，将其添加到新矩阵的行中。 - 最后，修正最底行倒数第二个元素为1，使得螺旋形状正确。
4. 层次化的递归结构
- 通过递归的方式，实际上是将矩阵的生成问题分解为多个层次。在每个递归步骤中，生成的“内层矩阵”就像是外层矩阵的子矩阵，而外层矩阵则是在其基础上再进行扩展。
- 每次递归都在原矩阵的外层增加一个“边框”，使得螺旋效果逐渐展现。
5. 螺旋的特性
- 螺旋阵列的特性是，每一层（从外到内）逐渐围绕一个中心形成边框。每一层的内容由
1组成，中心的元素逐渐形成空心。 - 每次生成一个矩阵时，我们是从外向内逐步填充1，并且矩阵的边缘依赖于外部递归产生的内层矩阵。
当我们构建宽度为 n=5 的螺旋阵列时，递归的构建过程会通过逐层填充和扩展矩阵。我们可以将这个过程分解为以下几个步骤：
目标：生成一个 5x5 的螺旋矩阵
11111
00001
11101
10001
11111步骤 1：处理特殊情况
在我们开始构建矩阵之前，首先需要检查是否为最小的特殊情况（width = 2 或 width = 3），这时候直接返回结果。不过，n=5 不属于这种情况，我们将进入递归步骤。
步骤 2：递归生成小矩阵
我们递归地调用 solution(width - 2) 来生成一个宽度为 3 的螺旋矩阵。对于 n=3 的情况，我们直接返回：
111
001
111这个矩阵是螺旋阵列的内部部分，接下来我们要把它扩展到宽度为 5 的矩阵。
步骤 3：构建外部边框
在递归返回的小矩阵 base 基础上，我们构建外部的边框：
-
初始化矩阵：我们首先创建一个
5x5的矩阵，第一行填充1，第二行的元素初始化为0，最后一个元素是1。这是矩阵的前两行：[1, 1, 1, 1, 1] <- 第一行 [0, 0, 0, 0, 1] <- 第二行 -
填充内层：接下来，我们将递归返回的小矩阵
base加入到结果矩阵中。在这个过程中，我们需要将base的每一行反转，并加上外层的边界：# base 的最后一行是 [111] # 反转后变为 [111]，然后添加 [0, 1]，得到 [11101]这样，我们将
base从下往上添加到结果矩阵中：csharp 复制编辑 [1, 1, 1, 1, 1] <- 第一行 [0, 0, 0, 0, 1] <- 第二行 [1, 1, 1, 0, 1] <- 第三行（从 base 返回的行） [1, 0, 0, 0, 1] <- 第四行（从 base 返回的行）通过倒序填充内层，依次处理剩下的行。
-
修正最后一行：由于我们填充内层时外加了边框，最后一行的倒数第二个元素需要修正为
1，确保螺旋阵列的形状正确：[1, 1, 1, 1, 1] <- 第一行 [0, 0, 0, 0, 1] <- 第二行 [1, 1, 1, 0, 1] <- 第三行 [1, 0, 0, 0, 1] <- 第四行 [1, 1, 1, 1, 1] <- 第五行（修正最后一行）
步骤 4：返回结果
最终返回的 5x5 螺旋矩阵是：
[[1, 1, 1, 1, 1],[0, 0, 0, 0, 1],[1, 1, 1, 0, 1],[1, 0, 0, 0, 1],[1, 1, 1, 1, 1]]3.代码
def solution(width):# Please write your code here# 确保输入的宽度大于1，且生成的螺旋阵列至少有两行两列assert width > 1# 处理特殊情况：当宽度为2时，直接返回结果if width == 2:return [[1, 1], [0, 1]]# 处理宽度为3的特殊情况，直接返回结果if width == 3:return [[1, 1, 1], [0, 0, 1], [1, 1, 1]]# 对于大于3的情况，递归生成一个 smaller width 的螺旋阵列base = solution(width - 2)# 初始化螺旋矩阵的前两行，第一行为全1，第二行所有元素为0，最后一个元素为1res = [[1] * width, [0] * width]res[1][-1] = 1# 将 smaller width 的螺旋阵列按逆序添加到新的螺旋矩阵中，外部加上边界for i in range(width - 3, -1, -1):res.append(base[i][::-1] + [0, 1])# 修正最底行倒数第二个元素为1，保持螺旋形状res[-1][-2] = 1return resif __name__ == "__main__":# You can add more test cases hereprint(solution(5) == [[1,1,1,1,1],[0,0,0,0,1],[1,1,1,0,1],[1,0,0,0,1],[1,1,1,1,1]])print(solution(8) == [[1,1,1,1,1,1,1,1],[0,0,0,0,0,0,0,1],[1,1,1,1,1,1,0,1],[1,0,0,0,0,1,0,1],[1,0,1,0,0,1,0,1],[1,0,1,1,1,1,0,1],[1,0,0,0,0,0,0,1],[1,1,1,1,1,1,1,1]])print(solution(2) == [[1, 1],[0, 1]]
4.参考资料
螺旋矩阵-CSDN博客
