矩陣最大對角模式匹配

我在進行矩陣模式匹配的技術面試時遇到了一個問題。我能夠使用蠻力解決問題，但想知道是否有更有效的解決方案，因為我的效率只有一半。預先感謝您的意見。

給定一個包含數字 0, 1, 2 和模式 [1, 2, 0, 2, 0, 2, 0] 的矩陣，找到匹配模式的最大長度，從矩陣中的任何點開始，但只能沿對角線移動。

這是我們期望函式回傳 12 的示例。

這是我們期望函式回傳 7 的地方。

并且空矩陣應該回傳 0。

這是我的代碼，就像我之前所說的那樣，它確實有效并通過了所有測驗，但我得到了停靠點。

def max_diagonal_match(matrix) -> int:
    max_len = 0
    pattern_match = [1, 2, 0, 2, 0, 2, 0]
    for i in range(0, len(matrix)):
        for j in range(0, len(matrix[i])):
            max_len = max(
                max_len,
                find_i_minus_j_minus(matrix, i, j, pattern_match, 7),
                find_i_minus_j_plus(matrix, i, j, pattern_match, 7),
                find_i_plus_j_minus(matrix, i, j, pattern_match, 7),
                find_i_plus_j_plus(matrix, i, j, pattern_match, 7)
            )
    return max_len


# i-, j-
def find_i_minus_j_minus(matrix, i, j, pattern, mod):
    count = 0
    while i >= 0 and j >= 0:
        if matrix[i][j] != pattern[count % mod]:
            return count
        count  = 1
        i -= 1
        j -= 1
    return count


# i-, j 
def find_i_minus_j_plus(matrix, i, j, pattern, mod):
    count = 0
    while i >= 0 and j < len(matrix[i]):
        if matrix[i][j] != pattern[count % mod]:
            return count
        count  = 1
        i -= 1
        j  = 1
    return count


# i , j-
def find_i_plus_j_minus(matrix, i, j, pattern, mod):
    count = 0
    while i < len(matrix) and j >= 0:
        if matrix[i][j] != pattern[count % mod]:
            return count
        count  = 1
        i  = 1
        j -= 1
    return count


# j , i 
def find_i_plus_j_plus(matrix, i, j, pattern, mod):
    count = 0
    while i < len(matrix) and j < len(matrix[i]):
        if matrix[i][j] != pattern[count % mod]:
            return count
        count  = 1
        i  = 1
        j  = 1
    return count

非常感謝您花時間閱讀，非常感謝您的任何意見。

uj5u.com熱心網友回復：

我們可以將問題分解為沿著矩陣的每個對角線找到可能的最長匹配。然后，演算法的效率歸結為我們能多快找到沿任何給定對角線的最長匹配。

對于長度的對角線和長度N的模式M，您的解決方案是O(N^2)：您嘗試N沿對角線的每個起點并盡可能地擴展匹配（這是O(N)比較）

這個問題的更快解決方案確實存在。可以用復雜度匹配每個對角線：

• O(NM) 通過使用動態編程，如果 M << N
• O(NlogN) 通過字典排序對角線的后綴（或相關技術：后綴樹、Burrows-Wheeler 變換、FM 索引等）
• 從技術上講，O(N)后綴陣列是可能的，但是演算法太復雜而無法實作編碼面試（例如 Ukkonen 演算法）

還有一些演算法，雖然O(N^2)在最壞的情況下，在實踐中可能比這快得多，例如，當長匹配很少時，種子和擴展演算法很快。

我確信上面提到的技術并不是一個詳盡的串列。

uj5u.com熱心網友回復：

建立在這個問題的接受答案之上。它基于幾個關鍵思想：

您可以np.diagonal在一個范圍內使用從陣列中切出每個可能的對角線。您可以翻轉陣列以確保獲得所有角度。

您可以tile制作圖案以確保它至少與最大對角線一樣長或更長。

由于 zip 的作業方式，您可以zip自動洗掉對角線和圖案以及圖案中的額外值。

然后您可以使用takewhilezipped (diag,pattern) 來檢查有多少連續匹配len(set(x))==1。

如果你對所有可能的組合都這樣做并取最大值，你應該有你的答案。

import numpy as np
from math import ceil
from itertools import takewhile

def max_sequence(arr):
    solns = []
    i = arr.shape[0]
    for x in range(-i, i 1):
        values = arr.diagonal(x)
        N = len(values)
        possibles = np.where(values == pattern[0])[0]
        for p in possibles:
            check = values[p:p N]
            m = len(list(takewhile(lambda x:len(set(x))==1, zip(pattern,check))))
            solns.append(m)
    return max(solns)

def find_longest(arr):
    if len(arr)>0:
        return max([max_sequence(x) for x in [arr, np.fliplr(arr), np.flipud(arr), arr[::-1]]])
    else:
        return 0

arr = np.array([
    [1,0,2,1,1,1,1,0,0,0,0,0,0],
    [1,2,2,1,1,1,1,0,0,0,0,0,0],
    [1,0,0,1,1,1,1,0,0,0,0,0,0],
    [1,0,0,2,1,1,1,0,0,0,0,0,0],
    [1,0,0,2,0,1,1,0,0,0,0,0,0],
    [1,0,0,1,1,2,1,0,0,0,0,0,0],
    [1,0,0,1,1,1,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,1,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,2,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0,2,0,0],
    [0,0,0,0,0,0,0,0,0,0,0,0,0],
])

arr1 = np.array([
    [1,0,2,1,1,1,1],
    [1,2,2,1,1,1,1],
    [1,0,0,1,1,1,1],
    [1,0,0,2,1,1,1],
    [1,0,0,2,0,1,1],
    [1,0,0,1,1,2,1],
    [1,0,0,1,1,1,0]
])

arr2 = np.array([])

pattern = [1, 2, 0, 2, 0, 2, 0]
# Make sure pattern repeats longer than the max diagonal
pattern = np.tile(pattern,ceil(arr.shape[1] / len(pattern)))

for a in [arr, arr1, arr2]:
    print(find_longest(a))

輸出

12
7
0

標籤：

上一篇：如何使用原型撰寫快速排序函式

下一篇：如何對動作的依賴樹進行排序和分塊，以便在每個步驟中將盡可能多的動作批處理在一起？