为了好玩,我正在 CodeWars 中解决一个问题,但我遇到了一些问题:
了解我需要在哪里修改代码以正确控制 m 和 n 的“转折点”,使它们开始减少而不是增加。
适当重构此代码。
该算法的目的是像“蜗牛”一样遍历一个二维列表,例如
[[1,2,3],
[4,5,6],
[7,8,9]]
应该返回
[1,2,3,6,9,8,7,4,5]
对于任何大小为 n*n 的列表
我没有很强的数学或 CS 背景,但我真的很喜欢这两者,并尝试深入理解这些问题。
我知道,例如,如果 n
表示行,m
表示二维列表的列,我需要增加最小值 n
为蜗牛的每个“电路”增加 1,并减少每个电路的最大 m
,但我无法理解需要在何处发生。
我已经简要地研究了一些递归解决方案,但在我开始深入研究这些解决方案之前,我希望有人可以看看这个并帮助我理解我的想法在哪里是错误的。 p>
def snail(array):
new_snail = []
n,m = 0,0
j = 1
while j <= len(array):
print(n,m)
if n == 0 and m == 0:
while m < len(array)-j:
new_snail.append(array[n][m])
m += 1
while n < len(array)-j:
new_snail.append(array[n][m])
n += 1
else:
while m > 0:
new_snail.append(array[n][m])
m -= 1
while n > 0:
new_snail.append(array[n][m])
n -= 1
m += 1
n += 1
j+=1
return new_snail
该算法在 3x3 2D 列表上的输出目前是
[1, 2, 3, 6, 9, 8, 7, 4, 5, 4]
,表示到达终点后向后移动。
在更大的 4x4 二维列表上,
array = [[1,2,3,4],
[4,5,6,7],
[8,9,10,11],
[12,13,14,15]]
输出是[1, 2, 3, 4, 7, 11, 15, 14, 13, 12, 8, 4, 5, 4, 5, 4]
,所以我是在第一行来回。
感谢您查看,我希望这符合 SO 问题的指导方针。我不太关心获得练习分数/正确练习,更关心理解为什么我的代码错误/实践不佳。
更新
我相信我对问题的理解越来越好,并且取得了一些进展,但让我失望的仍然是列表的范围。我觉得我在这方面真的很弱。我最终在一个方向上走得太远,而我针对该方向的所有解决方案都非常笨拙。
def snail(array):
new_snail = []
visited = "*"
i,j = 0,0
current_dir = "right"
def change_dir(direction):
if direction == "right":
return "down"
elif direction == "down":
return "left"
elif direction == "left":
return "up"
elif direction == "up":
return "right"
def move(ipos,jpos,direction):
i,j = ipos,jpos
if i == -1:
i += 1
elif i == len(array):
i -= 1
elif j == -1:
j +=1
elif j == len(array):
j -= 1
if direction == "right":
return i, j+1
elif direction == "down":
return i+1, j
elif direction == "left":
return i, j-1
elif direction == "up":
return i-1, j
new_snail.append(array[0][0])
array[0][0] = "*"
while len(new_snail) < len(array)**2:
i,j = move(i,j,current_dir)
if 0 <= i <= len(array)-1 and 0 <= j <= len(array)-1:
if array[i][j] != visited:
new_snail.append(array[i][j])
array[i][j] = "*"
else:
current_dir = change_dir(current_dir)
else:
current_dir = change_dir(current_dir)
return new_snail
最佳答案
我只是提供一个思路,代码要自己写。
蜗牛的头有四个方向,依次为右(j += 1)、下(i += 1)、左(j -= 1)、上(i -= 1)。
蜗牛会绕着这四个方向(右,下,左,上,右,下,左...)走,直到到达边界或访问的数字时转向下一个方向。当蜗牛不能走到任何格子时结束。
cannot walk to any grid
的定义:在该方向和下一个方向都不能踏入下一个格子。
带注释的示例代码
directions = [
lambda i, j: (i, j + 1),
lambda i, j: (i + 1, j),
lambda i, j: (i, j - 1),
lambda i, j: (i - 1, j),
]
array = [[1,2,3,4],
[4,5,6,7],
[8,9,10,11],
[12,13,14,15]]
def in_matrix(i, j):
return 0 <= i < len(array) and 0 <= j < len(array)
def is_visited(i, j):
return array[i][j] == 0
def snail(array):
direction_cnt = 0
i, j = 0, 0
ret = []
ret.append(array[i][j])
array[i][j] = 0 # mark as visited
while True:
direction_func = directions[direction_cnt % 4] # turning directions in circle
tmp_i, tmp_j = direction_func(i, j) # attempt to head one step
if (not in_matrix(tmp_i, tmp_j)) or is_visited(tmp_i, tmp_j): # over border or visted
direction_cnt += 1 # change direction
else:
i, j = tmp_i, tmp_j # confirm this step
ret.append(array[i][j])
array[i][j] = 0 # mark as visited
if len(ret) == len(array)**2: # simple terminal criteria
return ret
if __name__ == '__main__':
print snail(array)
关于python - 蜗牛算法 - 控制遍历的最大/最小位置,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56169104/