leetcode-413 等差数列划分

leetcode-467

题目描述：

把字符串 s 看作是“abcdefghijklmnopqrstuvwxyz”的无限环绕字符串，所以 s 看起来是这样的:"...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....". 现在我们有了另一个字符串 p 。你需要的是找出 s 中有多少个唯一的 p 的非空子串，尤其是当你的输入是字符串 p ，你需要输出字符串 s 中 p 的不同的非空子串的数目。 注意: p 仅由小写的英文字母组成，p 的大小可能超过 10000。

from collections import defaultdict
class Solution:
    def findSubstringInWraproundString(self, p: str) -> int:
        dp = defaultdict(int)
        n = len(p)
        mx = 0
        for i in range(n):
            if i> 0 and (ord(p[i])-ord(p[i-1])==1or (p[i-1]=="z" and p[i]=="a")):
                mx += 1
            else:
                mx = 1
            dp[p[i]] = max(mx,dp[p[i]])
        return sum(dp.values())

相似题目

leetcode-413 等差数列划分

题目描述：

如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。注：如果数字是等差数组，则必然差是连续相等的；所以先计算相邻两个数字的差，然后统计相等的连续数字；只要一次遍历就可以，感觉比较快，实际上只超过了5%。

class Solution:
    def numberOfArithmeticSlices(self, A: List[int]) -> int:
        n = len(A)
        dp = [0]*(n)
        mx = 0
        for i in range(1,n-1):
            if i>0 and A[i-1]+A[i+1]==2*A[i]:
                mx += 1
            else:
                mx = 0
            dp[i] = mx
        return sum(dp)