【小白用python刷Leetcode】718. 最长重复子数组

    技术2022-07-10  163

    718. 最长重复子数组

    题目描述

    给两个整数数组 A 和 B ,返回两个数组中公共的、长度最长的子数组的长度。

    示例:

    输入: A: [1,2,3,2,1]          B: [3,2,1,4,7] 输出: 3

    解释: 长度最长的公共子数组是 [3, 2, 1]。

    说明:

    1 <= len(A), len(B) <= 10000 <= A[i], B[i] < 100

    解题思路

    遇到熟悉题目的第四天,开心。本来是想截图题目描述的,但是发现会加水印,但是这道题又不是我原创的,而且因为这个鬼机制,主页地址是qq加一堆数字,好丑。所以没办法,还是老老实实复制题目描述并排格式。这道应该也是面试必会的一道了,自己秋招时虽然没被问到,但是小伙伴被问到的次数还蛮多的。而且这道题有很多版本,进阶一点点的要把公共子数组输出,还有最长公共子串(子串不像子数组是连续的)什么的,今天这篇都会简单说说,把代码贴上,但不会细说,等到时候碰上再说,懒。。。而且写给自己看,也没必要。

    首先这题比较大众的思路肯定是用动态规划,其实我第一次做也想不到动态规划,算是训练后的大众思路吧。创建个二维数组来记录最长公共子数组的长度,注意二维数组的size是要比两个数组的长度大一号的,即(m+1)*(n+1)大小,因为第一行和第一列要用来记录初状态。具体思路是判断两个数组的当前位置元素是否有相同,如果相同则在dp内上一状态的基础上+1,即状态转移方程是dp[i][j] = dp[i-1][j-1] + 1,其中dp[i][j]是当前状态,dp[i-1][j-1] 是上一状态;如果不相同则dp的相应位置置0。初条件全为0,因为在一开始未对比的时候,是没有相同元素的。截止条件当然就是两个数组内的所有元素都被遍历过了即截止。不过用动态规划似乎时间和空间复杂度都不怎么样,都是O(N×M)。

    细节的部分在代码部分都加了注释,应该很详细。

    题解代码:

    def findLength(self, A: List[int], B: List[int]) -> int: if not A or not B: return 0 m = len(B) + 1 # 创建dp的size,+1是为了留有初条件的空间 n = len(A) + 1 # 创建时尽量不要用[[0]*n]*m 这样子,因为这样子创建出来的二维数组似乎不是独立的,某一个元素变化,好像整行或者列都会变 dp = [[0 for i in range(n)] for i in range(m)] # 初条件为0,所以不如就全部置0处理 key = 0 # 记录最长的公共子数组 # 这里似乎有思路是倒着走的,我也不知道为啥要倒着走,反正我觉得不如这种正着走顺当 for i in range(1,m): for j in range(1,n): if A[j-1] == B[i-1]: # 判断对应位置上元素是否相同 dp[i][j] = dp[i-1][j-1] + 1 # 状态转移 key = max(key, dp[i][j]) # 取最长 # 这里没有状态转移方程的另外一半,因为我们之前就已经对整个dp都置0了。没必要额外再有改0的操作 return key

    那如果进阶一点,要输出这个公共子数组(或者子串),就是额外再增加一个p,来标定最长公共子串结束的位置。是技术处时候,由这个位置向前推key的长度然后输出就好。代码是针对的是最长公共子串,即是两个字符串而不是两个数组,其实最长公共子数组也基本一模一样。

    # 最长公共子串 def substr(s1,s2): maxl = 0 A = [[0 for i in range(len(s1)+1)] for i in range(len(s2)+1)] for i in range(1,len(s2)+1): for j in range(1,len(s1)+1): if s1[j-1] == s2[i-1]: A[i][j] = A[i-1][j-1]+1 if maxl < A[i][j]: maxl = A[i][j] p = i # 就是这里,记录末位置 return maxl, s2[p-maxl:p]

    还有更进阶,最长公共子序列(不连续)。思路差不多,都是动态规划,不过在输出子序列的时候麻烦一点,因为要一步步回溯哪些元素是公共的。

    # 最长公共子序列 def subseq(s1,s2): # dp矩阵 A=[[0 for i in range(len(s1)+1)] for i in range(len(s2)+1)] # 记录路径的矩阵 B = [[' ' for i in range(len(s1)+1)] for i in range(len(s2)+1)] for i in range(1,len(s2)+1): for j in range(1,len(s1)+1): if s2[i-1] == s1[j-1]: A[i][j] = A[i-1][j-1]+1 B[i][j] = '+1' else: A[i][j] = max(A[i-1][j],A[i][j-1]) if A[i][j-1] == A[i][j]: B[i][j] = 'left' else: B[i][j] = 'up' return B,A[-1][-1] def findseq(B,s1,s2): # 回溯的函数,需要上个函数记录路径的矩阵 j = len(s1) i = len(s2) res = [] while i >0 and j>0: if B[i][j] == 'left': j -= 1 elif B[i][j] == 'up': i -= 1 else: i -= 1 j -= 1 res.append(s1[j]) return ''.join(res[::-1]) s1='helloworld' s2='loop' B, n = subseq(s1, s2) print(n) print(findseq(B,s1,s2))

    官方思路

    在看了官方题解之后了解到这道题也能用滑窗做,神奇。时间复杂度给出的是O((N+M)×min(N,M)),然而我并不知道是怎么算出来这个时间复杂度的。小白嘛,没办法。空间复杂度是O(1)

    具体思路就是取较短数组的子数组和较长的数组去比,看这个子数组是否在较长的数组内部。在滑窗内的是这个子数组,如果子数组在长数组的内部,就继续向滑窗内加元素(右边界向右拓展);如果不在,则左边界向左收缩。需要注意的是对于数组来说,只能判断某个元素是否在数组内,而没法判断某个数组是不是其连续子数组(也可能是有现成函数的,只是我不知道)。所以这里我的做法是将数组都转成字符串,这样就可以通过判断是否为子串来判断是否为连续子数组了。细节注释在了代码里,应该还算详细。

    def findLength(self, A: List[int], B: List[int]) -> int: if not A or not B: return 0 m = len(A) n = len(B) # 保证取短的数组 if m > n: m, n, B, A = n, m, A, B # 将数组转化为字符串 ''' 前后加逗号的原因是保证为单一的元素,比如子串是‘7’,那么在长数组中 只要含‘7’都会被判找到,这样像‘27’、‘79’、‘371’这种其实并不是‘7’的 数字都会误判。 ''' strB = ',' + ','.join(str(x) for x in B) + ',' tmp = [] # 滑窗 key = 0 for x in A: tmp.append(x) # 相当于右边界拓展 str_tmp = ',' + ','.join(str(y) for y in tmp) + ',' if str_tmp in strB: key = max(len(tmp), key) else: tmp = tmp[1:] # 左边界收缩 return key

    以上就是我,一个正儿八经的小白(大神们通过看代码应该也感觉出来了),对这道题的理解,欢迎诸位指正讨论,感谢阅读。

    原题链接:

    https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/

    Processed: 0.010, SQL: 9