資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學Python中查詢最大長度的蛇形序列
假設我們有一個數字網格；我們必須找到一個蛇形序列並返回它。如果有多個蛇形序列，則只返回一個。眾所周知，蛇形序列是由網格中相鄰數字構成的，因此對於每個數字，其右側或下方的數字與其值的差值為+1或-1。因此，如果當前值位於網格單元格(a, b)中，則如果該數字為±1，我們可以向右移動(a, b+1)，或者如果該數字為±1，則向下移動(a+1, b)。
因此，如果輸入如下所示：
| 10 | 7 | 6 | 3 |
| 9 | 8 | 7 | 6 |
| 8 | 4 | 2 | 7 |
| 2 | 2 | 2 | 8 |
則輸出將為6，序列 - 10 (0, 0) 到 9 (1, 0) 到 8 (1, 1) 到 7 (1, 2) 到 6 (1, 3) 到 7 (2, 3) 到 8 (3, 3)
為了解決這個問題，我們將遵循以下步驟：
定義一個函式`get_path()`。這將接收網格、mat、i、j。
path := 新列表
pt := 一個點 [i, j]
將pt插入path的末尾
當grid[i, j]不為0時，執行：
如果 i > 0 且 grid[i, j]-1 等於 grid[i-1, j]，則
pt := [i-1, j]
將pt插入path的末尾
i := i - 1
否則，如果 j > 0 且 grid[i, j]-1 等於 grid[i, j-1]，則
pt := [i, j-1]
將pt插入path的末尾
j := j - 1
返回path
從主方法中，執行以下操作：
lookup := 建立一個大小為M x N的網格並用0填充
length_max := 0, max_row := 0, max_col := 0
對於範圍0到M中的i，執行：
對於範圍0到N中的j，執行：
如果i或j不為零，則
如果 (i > 0 且 |grid[i-1, j] - grid[i, j]| 為1)，則
lookup[i,j] = lookup[i,j],lookup[i-1,j] + 1 的最大值
如果 length_max < lookup[i,j]，則
length_max := lookup[i, j]
max_row := i
max_col := j
如果 (j > 0 且 |grid[i, j-1] - grid[i, j]| 為1)，則
如果 length_max < lookup[i][j] 不為零，則
lookup[i,j] = lookup[i,j],lookup[i,j-1] + 1 的最大值
length_max := lookup[i, j]
max_row := i
max_col := j
顯示 length_max
path := get_path(lookup, grid, max_row, max_col)
以相反的順序列印path中的所有元素
示例
讓我們看看下面的實現，以便更好地理解；
M = 4
N = 4
def get_path(grid, mat, i, j):
path = list()
pt = [i, j]
path.append(pt)
while (grid[i][j] != 0):
if (i > 0 and grid[i][j]-1 == grid[i-1][j]):
pt = [i-1, j]
path.append(pt)
i -= 1
elif (j > 0 and grid[i][j]-1 == grid[i][j-1]):
pt = [i, j-1]
path.append(pt)
j -= 1
return path
def get_sequence(grid):
lookup = [[0 for i in range(N)] for j in range(M)]
length_max = 0
max_row = 0
max_col = 0
for i in range(M):
for j in range(N):
if (i or j):
if (i > 0 and
abs(grid[i-1][j] - grid[i][j]) == 1):
lookup[i][j] = max(lookup[i][j],lookup[i-1][j] + 1)
if (length_max < lookup[i][j]):
length_max = lookup[i][j]
max_row = i
max_col = j
if (j > 0 and
abs(grid[i][j-1] - grid[i][j]) == 1):
lookup[i][j] = max(lookup[i][j],lookup[i][j-1] + 1)
if (length_max < lookup[i][j]):
length_max = lookup[i][j]
max_row = i
max_col = j
print("Maximum length:", length_max)
path = get_path(lookup, grid, max_row, max_col)
print("Sequence is:")
for ele in reversed(path):
print(grid[ele[0]][ele[1]], " [", ele[0], ", ", ele[1], "]", sep = "")
grid = [
[10, 7, 6, 3],
[9, 8, 7, 6],
[8, 4, 2, 7],
[2, 2, 2, 8]]
get_sequence(grid)輸入
[[10, 7, 6, 3], [9, 8, 7, 6], [8, 4, 2, 7], [2, 2, 2, 8]]
輸出
Maximum length: 6 Sequence is: 10 [0, 0] 9 [1, 0] 8 [1, 1] 7 [1, 2] 6 [1, 3] 7 [2, 3] 8 [3, 3]
503 次瀏覽
