[已解决]Python：每日一题 291

zltzlt

今天的题目：

给定一个正整数 n，生成一个包含 1 到 n² 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

示例 1：

输入：2
输出：
[
[1, 2],
[4, 3],
]

示例 2：

输入：3
输出：
[
[1, 2, 3],
[8, 9, 4],
[7, 6, 5]
]

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

Seawolf

2019-12-19 01:45:26

1. def func(self, n):
   
2.     ret = [[0] * n for _ in range(n)]
   
3.     i, j, di, dj = 0, 0, 0, 1
   
4.     for k in xrange(n*n):
   
5.         ret[i][j] = k + 1
   
6.         if ret[(i+di)%n][(j+dj)%n]:
   
7.             di, dj = dj, -di
   
8.         i += di
   
9.         j += dj
   
10.     return ret

复制代码

跳转到最佳答案楼层

小小小菜菜菜

改成这样

1. def get_matrix(n=4):
   
2. 
   
3.     abc = [[0 for i in range(n)] for j in range(n)]
   
4.     i = 1
   
5.     k = 0
   
6. 
   
7.     while i < n**2:
   
8.         for u in range(0+k, n-1-k):
   
9.             abc[0+k][u] = i
   
10.             i += 1
    
11. 
    
12.         for r in range(0+k, n-1-k):
    
13.             abc[r][n-1-k] = i
    
14.             i += 1
    
15. 
    
16.         for d in range(n-1-k, 0+k, -1):
    
17.             abc[n-1-k][d] = i
    
18.             i += 1
    
19. 
    
20.         for l in range(n-1-k, 0+k, -1):
    
21.             abc[l][0+k] = i
    
22.             i += 1
    
23. 
    
24.         k += 1
    
25. 
    
26.     if n%2 != 0:
    
27.         abc[k][k] = n**2
    
28. 
    
29.     return abc

复制代码

zltzlt

小小小菜菜菜 发表于 2019-12-18 20:42

不能使用第三方库哦。

TJBEST

n最大多大

阴阳神万物主

TJBEST 发表于 2019-12-18 21:18
n最大多大

上不设限

                               
登录/注册后可看大图

阴阳神万物主

楼主，示例1的输出把逗号漏掉了真的好吗？

1. def solve(n:int)->list:
   
2.     def get_pos():
   
3.         side = [0,n,0,n]#[上,下,左,右]
   
4.         y = x = 0
   
5.         while side[1]-side[0] or side[3]-side[2]:#未完
   
6.             for y in range(side[2],side[3]):#向右
   
7.                 yield (x,y)
   
8.             else:
   
9.                 side[0] += (1 if side[0]<side[1] else 0)
   
10.             for x in range(side[0],side[1]):#向下
    
11.                 yield (x,y)
    
12.             else:
    
13.                 side[3] -= (1 if side[3]>side[2] else 0)
    
14.             for y in range(side[3]-1,side[2]-1,-1):#向左
    
15.                 yield (x,y)
    
16.             else:
    
17.                 side[1] -= (1 if side[1]>side[0] else 0)
    
18.             for x in range(side[1]-1,side[0]-1,-1):#向上
    
19.                 yield (x,y)
    
20.             else:
    
21.                 side[2] += (1 if side[2]<side[3] else 0)
    
22.     res = [[0]*n for i in range(n)]
    
23.     num = 1
    
24.     for pos in get_pos():
    
25.         x,y = pos
    
26.         res[x][y] = num
    
27.         num += 1
    
28.     return res
    
29. 
    
30. if __name__ == '__main__':
    
31.     print('示例1 输出：',solve(2))
    
32.     print('示例2 输出：',solve(3))
    
33.     print('自测 输出：',solve(1),solve(0))
    

复制代码

我来康康差不多的逻辑，楼主能变出什么花儿来

                               
登录/注册后可看大图

                               
登录/注册后可看大图

                               
登录/注册后可看大图

时间复杂度应当为 O(n^2)

zltzlt

阴阳神万物主 发表于 2019-12-18 21:33
楼主，示例1的输出把逗号漏掉了真的好吗？

我来康康差不多的逻辑，楼主能变出什么花儿来

当然是通过啦

执行用时：24 ms

阴阳神万物主

zltzlt 发表于 2019-12-18 22:16
当然是通过啦

执行用时：24 ms

要不是定义一个类可能算开挂，我就定义类了。

Croper

拙劣模仿冬雪雪冬大佬的zip法：

1. def func291_1(n):
   
2.     if (n==0):
   
3.         return []
   
4.     ret=[[n**2]]
   
5.     i=n**2;
   
6.     while (i>1):
   
7.         ret=[list(c) for c in zip(*reversed(ret))]
   
8.         ret.insert(0,list(range(i-len(ret[0]),i)))
   
9.         i-=len(ret[0])
   
10.     return ret;
    

复制代码

数学法：

1. def func291_2(n):
   
2.     ret=[];
   
3.     for y in range(n):
   
4.         ret.append([])
   
5.         for x in range(n):
   
6.             layer=min(x,y,n-1-x,n-1-y);
   
7.             i=(x+y-2*layer+1) if (x==n-1-layer or y==layer) else (4*n-6*layer-3-x-y)
   
8.             ret[y].append(4*(n-layer)*layer+i);
   
9.     return ret;
   

复制代码

TJBEST

速度有点慢 实测 1000时 我的代码耗时 大约 3.5秒左右 不甚理想

1. def fun291(n):
   
2.     def getNum(x,y,num):
   
3.         #判断圈数
   
4.         loop = min([x,y,num-1-x,num-1-y])
   
5.         firstNum = 0
   
6.         if loop > 0:
   
7.             firstNum = 1 + 4 * num * loop - 4 * loop *loop
   
8.         else:
   
9.             firstNum = 1
   
10.         #四个标记位
    
11.         if x == loop:
    
12.             return firstNum + (pointy - loop)
    
13.         elif y == num - 1 - loop:
    
14.             return firstNum + (num - 1 - 2*loop) + (pointx - loop)
    
15.         elif x == num - loop - 1:
    
16.             return firstNum + (num - 1 - 2*loop) + (num - 1 - 2*loop) + (num - 1 - loop- pointy)
    
17.         else:
    
18.             return firstNum + (num - 1 - 2*loop) + (num - 1 - 2*loop) + (num - 1 - 2*loop) + (num - 1 - loop - pointx)
    
19. 
    
20.         
    
21.     result = []
    
22.     for pointx in range(0,n):
    
23.         line = []
    
24.         for pointy in range(0,n):
    
25.             element = getNum(pointx,pointy,n)
    
26.             line.append(element)
    
27.         result.append(line)
    
28.     return result

复制代码

TJBEST

阴阳神万物主 发表于 2019-12-18 21:33
楼主，示例1的输出把逗号漏掉了真的好吗？

我来康康差不多的逻辑，楼主能变出什么花儿来

你这个方法不错，我觉得应该是好东西

Seawolf

1. def func(self, n):
   
2.     ret = [[0] * n for _ in range(n)]
   
3.     i, j, di, dj = 0, 0, 0, 1
   
4.     for k in xrange(n*n):
   
5.         ret[i][j] = k + 1
   
6.         if ret[(i+di)%n][(j+dj)%n]:
   
7.             di, dj = dj, -di
   
8.         i += di
   
9.         j += dj
   
10.     return ret

复制代码

hrp

阴阳神万物主 发表于 2019-12-18 21:33
楼主，示例1的输出把逗号漏掉了真的好吗？

我来康康差不多的逻辑，楼主能变出什么花儿来

大佬你的数学逻辑是怎么练出来的，我看这些想到一半就开始头晕

fan1993423

Seawolf 发表于 2019-12-19 01:45

这个思路妙，不过func不用self，而且也没有xrange

danteer

1. 
   
2. def func(n):
   
3.     list1 = [[] for i in range(n)]
   
4.     number = 0
   
5.     count = 0
   
6.    
   
7.     while count < ((n//2) + (n%2)):
   
8.         temp = (n-2*count-1)*4
   
9.         if temp == 0:
   
10.             list1[n//2].insert(n//2,number+1)
    
11.             break
    
12.         
    
13.         for i in range(number + temp//4 + 1,number,-1):
    
14.             list1[count].insert(count,i)
    
15.         
    
16.         for i in range(number + temp//4 + 2,number + (temp//4)*2 + 1):
    
17.             list1[count+i-number-temp//4-1].insert(count,i)
    
18.         
    
19.         for i in range(number + (temp//4)*2 + 1,number + (temp//4)*3 + 2):
    
20.             list1[-count-1].insert(count,i)
    
21.         
    
22.         for i in range(number + (temp//4)*3 + 2,number + (temp//4)*4 + 1):
    
23.             list1[-count-i+number+(temp//4)*3].insert(count,i)
    
24.         
    
25.         number += temp
    
26.         count += 1
    
27.    
    
28.     return list1

复制代码

阴阳神万物主

hrp 发表于 2019-12-19 01:59
大佬你的数学逻辑是怎么练出来的，我看这些想到一半就开始头晕

这不是数学逻辑，仅仅是逻辑，涉及数学的不过只有建立了一个 平面直角坐标系 而已。
然后将 (0,0) 到 (n-1,n-1) 的连线作为正方形的对角线，再把正方形画出来，顺时针沿着正方形的边走，越走越往内而已呀，走一格报一个坐标，按照题意绕圈圈啊。

TJBEST

阴阳神万物主 发表于 2019-12-19 12:10
这不是数学逻辑，仅仅是逻辑，涉及数学的不过只有建立了一个 平面直角坐标系 而已。
然后将 (0,0) 到 (n ...

主要是这个生成器用的好，要是我可能就用序列或者其他结构记录了，你这样速度和空间都节省了。

Stubborn

1. def fun291(n: int):
   
2.     r, n = [[n ** 2]], n ** 2
   
3.     while n > 1: n, r = n - len(r), [[*range(n - len(r), n)]] + [*zip(*r[::-1])]
   
4.     return r

复制代码

archlzy

1. def fun291(n):
   
2.     temp_list = [[0]*n for i in range(n)]
   
3.     i,j = 0,0
   
4.     i_b,j_b = 0,1
   
5.     boo_pool= [(0,1),(1,0),(0,-1),(-1,0)]
   
6.     m = 0
   
7.     for _ in range(n*n):
   
8.         temp_list[i][j] = _+1
   
9.         i += i_b
   
10.         j += j_b
    
11.         try:
    
12.             if temp_list[i+i_b][j+j_b] != 0:
    
13.                 m += 1
    
14.                 i_b,j_b = boo_pool[m%4]
    
15.         except:
    
16.             m += 1
    
17.             i_b,j_b = boo_pool[m%4]
    
18.     return temp_list

复制代码

闲愚

命名不规范，写的有点乱所以加了注释，没有用递归

1. def solve(n):
   
2.     # 生成n * n的矩阵result，并且用0占位
   
3.     result = []
   
4.     for i in range(n):
   
5.         result.append([])
   
6.     for i in range(n):
   
7.         for j in range(n):
   
8.             result[i].append(0)
   
9.     # 将填入的所有数字放入列表list1
   
10.     list1 = list(range(1,n ** 2 + 1))
    
11.     pile_num = 0 # 矩阵赋值的第pile_num层
    
12.     while 1:
    
13.         if len(list1) > 1:
    
14.             # 对result的第pile_num层赋值，赋值方法：按行赋值，赋前n - 1个数，后旋转，循环四次即赋慢一层的值
    
15.             rot_count = 4 # 旋转次数
    
16.             while rot_count > 0:
    
17.                 # 赋第pile_num层的第一行的前n - 1个数
    
18.                 for i in range(pile_num,n - 1 - pile_num):
    
19.                     result[pile_num][i] = list1[0]
    
20.                     del list1[0]
    
21.                 # 复制当前result给list2
    
22.                 list2 = []
    
23.                 for i in range(n):
    
24.                     list2.append([])
    
25.                 for i in range(n):
    
26.                     for j in range(n):
    
27.                         list2[i].append(result[i][j])
    
28.                 # 利用list2使result逆时针旋转
    
29.                 for i in range(n):
    
30.                     for j in range(n):
    
31.                         result[i][j] = list2[j][n - i - 1]
    
32.                 rot_count -= 1
    
33.             pile_num += 1
    
34.         elif len(list1) == 1:
    
35.             result[n // 2][n // 2] = list1[0]
    
36.             del list1[0]
    
37.         else:
    
38.             break
    
39.     return result
    
40. 
    
41. if __name__ == '__main__':
    
42.     print('自测1：')
    
43.     result1 = solve(2)
    
44.     for i in range(len(result1)):
    
45.         print(result1[i])
    
46. 
    
47.     print('自测2：')
    
48.     result1 = solve(3)
    
49.     for i in range(len(result1)):
    
50.         print(result1[i])
    
51. 
    
52.     print('自测1：')
    
53.     result1 = solve(5)
    
54.     for i in range(len(result1)):
    
55.         print(result1[i])
    

复制代码