企业高端网站建设美工,东城区网站排名seo,写文章免费的软件,腾讯云域名交易Leetcode 3008. Find Beautiful Indices in the Given Array II 1. 解题思路2. 代码实现 题目链接#xff1a;3008. Find Beautiful Indices in the Given Array II
1. 解题思路
这一题其实算是套路题了#xff0c;知道的话就挺快的#xff0c;不知道的话就会很难了…… …Leetcode 3008. Find Beautiful Indices in the Given Array II 1. 解题思路2. 代码实现 题目链接3008. Find Beautiful Indices in the Given Array II
1. 解题思路
这一题其实算是套路题了知道的话就挺快的不知道的话就会很难了……
思路上来说的话其实很直接就是首先获取原始的字符串s当中所有的子串a和子串b出现的位置数组loc_a和loc_b然后对比两个数组找到所有loc_a当中的元素使得loc_b当中存在某一元素与其距离的绝对值不大于k。
首先我们考察第二部分的问题这个的话我们对于两个有序数组使用滑动窗口就能在 O ( N ) O(N) O(N)的时间复杂度内处理了并不复杂注意一下滑动窗口的移动条件就行了这里就不过多展开了。
剩下的就是第一部分的问题如何在一个字符串s当中获取所有的子串sub出现的位置。
这个问题其实蛮难的自己想的话估计能想死人不过现在已经是个套路题了用z算法就能够直接搞定了我之前也写过一个博客经典算法Z算法z algorithm介绍过这个算法里面有个例子一模一样直接复制里面的代码来用就行了。如果觉得我写的不好的话也可以自己去wiki或者知乎搜搜挺多的……
2. 代码实现
给出python代码实现如下
def z_algorithm(s):n len(s)z [0 for _ in range(n)]l, r -1, -1for i in range(1, n):if i r:l, r i, iwhile r n and s[r-l] s[r]:r 1z[i] r-lr - 1else:k i - lif z[k] r - i 1:z[i] z[k]else:l iwhile r n and s[r-l] s[r]:r 1z[i] r-lr - 1z[0] nreturn zclass Solution:def beautifulIndices(self, s: str, a: str, b: str, k: int) - List[int]:def find_all(s, sub):z z_algorithm(subs)n, m len(s), len(sub)z z[m:]return [idx for idx, l in enumerate(z) if l m]alist find_all(s, a)blist find_all(s, b)ans []i, j, n 0, 0, len(blist)for idx in alist:while i n and blist[i] idx-k:i 1while j n and blist[j] idxk:j 1if j-i0:ans.append(idx)return ans提交代码评测得到耗时1619ms占用内存65MB。
