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#京东##京东笔试##笔试#
这么用心写文章，我能连着看一天
