分类目录归档:算法与数据结构

leetcode 718. 最长重复子数组 python3

最长重复子数组
会超出时间限制,但是很直观的一个解法,用到了numpy来生成一个共现矩阵

思路就是生成一个共现矩阵(参考下图),然后遍历查找,这个解法是可以得到所有不同长度的重复子数组的,产生了冗余信息。但是比较直观,所以把它记录下来。
LCS

from typing import List

import numpy as np

class Solution:
    def findLength(self, A: List[int], B: List[int]) -> int:
        common = np.asarray(A).reshape((len(A), 1)) == np.asarray(B).reshape((1, len(B)))
        used = np.zeros_like(common)

        L = len(common)

        def get_seq_len(i, j):
            cnt = 0
            while i < L and j < L and common[i][j] and not used[i][j]:
                used[i][j] = True
                i += 1
                j += 1
                cnt += 1
            return cnt

        max_len = 0
        for i in range(L):
            for j in range(L):
                if common[i][j] and not used[i][j]:
                    cur_len = get_seq_len(i, j)
                    if cur_len > max_len:
                        max_len = cur_len

        return max_len