20220827京东研发笔试最后一题

不是自己的场，场后补的题。有一个很巧妙的反推思路参考：https://www.nowcoder.com/discuss/1030672?type=all&order=recall&pos=&page=0&ncTraceId=&channel=-1&source_id=search_all_nctrack&gio_id=7A2CF4AC0BD5B28E09B41FF267E58F73-166****080129。

因为代码没法交，没法测通过比例。我只是写了一份反推的代码，写了一份自己的思路，本地对拍通过了。如有问题欢迎随时私信。

题目

小红定义“漂亮串”为：至少有两个“red“子串。例如”redcred”为漂亮串，但”reedred“则不是漂亮串。
小红想知道，长度为n的、仅包含小写字母的字符串***有多少种不同的漂亮串？
输入描述：
一个正整数n，代表漂亮串的长度。1＜n＜1e6
输出描述：
长度为n的，漂亮串的种类数。答案对1e9+7取模。

input:
6

output:
1

首先按照上面一个反推思路写一个代码：

mod = int(1e9 + 7)


def func1(n):
    @lru_cache(None)
    def f(n):
        if n == 1: return 26
        if n == 2: return 26 * 26
        if n == 3: return 26 * 26 * 26 - 1
        return f(n - 1) * 26 - f(n - 3)

    @lru_cache(None)
    def g(n):
        if n == 1: return 0
        if n == 2: return 0
        if n == 3: return 1
        return g(n - 1) * 26 - g(n - 3) + f(n - 3)

    return (pow(26, n) - f(n) - g(n))%mod

我的思路：正向考虑。假设我们有很多很多字符串，每个字符串都至少有2个red，如何保证彼此不重复呢？考虑第一个red的出现位置和第二个red的出现位置。只要这2个red的出现位置不重复，那么整体的字符串就不一样。

假设第一个red出现下标为i，第二个red出现下标为j。那么这种情况有多少种组成方案呢？考虑3个位置：

• 第一个red之前的，必然不能出现red。那么我们设立一个函数f0(n)，表示n长度的不出现red的字符串方案数。这个时候最前方构造的方案数应当为f0(i)
• 第一个red和第二个red之间的，同样不能出现red，这部分是f0(j-i-3)
• 第二个red之后的，这部分什么字符都可以，因为第j个位置是red。那么这个red后面还有n-j-3个字符，方案数应当是26^(n-j-3)

ok，那我们遍历每个i和每个j，可以得到一个O(n^2)的思路：

def func2(n):
    @lru_cache(None)
    def f0(n):
        if n == 0: return 1
        if n == 1: return 26
        if n == 2: return 26 * 26
        if n == 3: return 26 * 26 * 26 - 1
        return f0(n - 1) * 26 - f0(n - 3)

    @lru_cache(None)
    def fa(n):
        return 26 ** n

    ans = 0
    for i in range(n):
        for j in range(i+3,n-2):
            ans+=f0(i)*f0(j-i-3)*fa(n-j-3)
            ans%=mod
    return ans

现在n^2的思路有了，我们开始思考如何转化成O(n)呢？

首先可以看到内循环的式子：f0(i)*f0(j-i-3)*fa(n-j-3)，内层循环变量是j，那么我们其实可以把f0(i)取出来。

for i in range(n):
    v=f0(i)
    for j in range(i+3,n-2):
        ans+=v*f0(j-i-3)*fa(n-j-3)

然后考虑后半部分：f0(j-i-3)*fa(n-j-3)，可以发现一个规律，这两个函数的参数和是有规律的：j-i-3+n-j-3=n-i-6。这么看可能有些抽象，我们先定死一个i。考虑如下：

假设n=10，i=0。我们人工的把下面式子展开：
for j in range(3,8): ans+=v*f0(j-3)*fa(n-j-3)
j的取值是[3,7]，我们把每个j的取值带进去：
j=3: ans+= v*f0(0)*fa(4)
j=4: ans+= v*f0(1)*fa(3)
j=5: ans+= v*f0(2)*fa(2)
j=6: ans+= v*f0(3)*fa(1)
j=7: ans+= v*f0(4)*fa(0)

很明显，两个参数是有规律的。有规律我们就可以想办法开个函数抽象一下，假设我们设置了一个函数g，g(n)=f0(0)*fa(n)+f0(1)*fa(n-1)+...+f0(n-1)*fa(1)+f0(n)*fa(0)

如果我们有了这个函数g，我们就可以把算法优化成O(n)的：

for i in range(n):
    ans+=g(n-i-6)*f0(i)

ok，我们如何求g函数呢，进行如下推导：

g(n)=f0(0)*fa(n)+f0(1)*fa(n-1)+...+f0(n-1)*fa(1)+f0(n)*fa(0)
fa(n)只是我抽象的一层，实际上fa(n)=26^n

那我们把这个式子展开
g(n)=f0(0)*(26^n)+f0(1)*(26^(n-1))+...+f0(n-1)*26+f0(n)

我们开始找g函数之间的关系，考虑：
g(n-1)=f0(0)*(26^(n-1))+f0(1)*(26^(n-2))+...+f0(n-2)*26+f0(n-1)

不难看出：
26*g(n-1)=f0(0)*(26^n)+f0(1)*(26^(n-1))+...+f0(n-2)*(26^2)+f0(n-1)*26

不难看出：
26*g(n-1)=g(n)-f0(n)

那么：
g(n)=26*g(n-1)+f0(n)

这个式子就是我们可以O(n)方式得到的

由上面推理，我们可以写出最终代码：

def func2(n):
    @lru_cache(None)
    def f0(n):
        if n == 0: return 1
        if n == 1: return 26
        if n == 2: return 26 * 26
        if n == 3: return 26 * 26 * 26 - 1
        return f0(n - 1) * 26 - f0(n - 3)

    @lru_cache(None)
    def fa(n):
        return 26 ** n

    @lru_cache(None)
    def g(n):
        if n < 0: return 0
        if n == 0: return 1
        return g(n - 1) * 26 + f0(n)

    ans = 0
    for i in range(n):
        ans += g(n - i - 6) * f0(i)
        ans %= mod
    return ans