首页 > 代码库 > 求解暗黑字符串(网易2017秋招)

求解暗黑字符串(网易2017秋招)

问题描述:一个只包含‘A‘、‘B‘和‘C‘的字符串,如果存在某一段长度为3的连续子串中恰好‘A‘、‘B‘和‘C‘各有一个,那么这个字符串就是纯净的,否则这个字符串就是暗黑的。

例如:
BAACAACCBAAA 连续子串"CBA"中包含了‘A‘,‘B‘,‘C‘各一个,所以是纯净的字符串
AABBCCAABB 不存在一个长度为3的连续子串包含‘A‘,‘B‘,‘C‘,所以是暗黑的字符串

你的任务就是计算出长度为n的字符串(只包含‘A‘、‘B‘和‘C‘),有多少个是暗黑的字符串 (1 ≤ n ≤ 30)。

首先如果题目是如何判断一个字符串是暗黑(纯净)字符串,你会怎么解?

这个问题很简单,直接遍历判断连续的三个字符是否分别为ABC。额,而我想说的是有一个比较好的想法是

令A=2,B=3,C=5,如果某三个字母乘积为30,即这个字符串为纯净的字符串。尽管操作起来比直接判断连续3个字符串是否为ABC便利不了多少,但是我觉得这是一个比较好的想法。

 

讲回正题,现在是计算出长度为n的字符串,有多少个暗黑的字符串。

下面提供2种思路

思路1

当n=1时,3种情况,暗黑,

当n=2时,9种情况,暗黑。

当n=3时,第一个位置3种情况,第二个位置3种情况,而第三个位置则要考虑前2个位置,

如果前2个位置相同则第三个位置有三种选择,否则有2种选择。

所有有 3*(3*1+2*2)=21是暗黑的。

当n=4时,按照n=3的情况继续类推下去,假若第二个位置和第三个位置相同,第四个位置有3种选择,否则有2种选择。

所以有3*(3*(1+2)+2*(1*2+2))) = 51(如果看不明白可留言再解答)

如此类推可得出下列规律

当n>3,sum(n) = 3*(3*num3(n) + 2*num2(n))

num2(n) = 2*num3(n-1) + num2(n-1)

num3(n) = num3(n-1) + num2(n-1)

观察上面第一个式子3*(3*1+2*2)=21 ,num2(1)=2  num3(1)=1

这个思路主要是从式子里推出来的,也是比较常规的一个方法。

def dark1():
    dark = [3,9]
    num2 = 2 
    num3 = 1
    for i in range(28):
        dark.append(3*(3*num3+2*num2))
        num3,num2 = num2+num3,2*num3+num2
    print(dark)

运行结果:

[3, 9, 21, 51, 123, 297, 717, 1731, 4179, 10089, 24357, 58803, 141963, 342729, 827421, 1997571, 4822563,

11642697, 28107957, 67858611, 163825179, 395508969, 954843117, 2305195203, 5565233523, 13435662249,

32436558021, 78308778291, 189054114603, 456417007497]

 

思路2

正如上面的思路1,我们可以分析出,每增加一个位置的字符,要使其保持暗黑的性质,只需要考虑前2个字符。

当前2个字符相同,那么第n个位置的取法有3种,否则有2种。

不妨设前2个字符相同的情况为s(n),前2个字符不同为d(n),那么我们可得出

sum(n) = 3*s(n-1) + 2*d(n-1) = 2*(s(n-1)+d(n-1)) + s(n-1) = 2*sum(n-1) + s(n-1)

因为前个字符要不就是d(n)要不就是s(n),所以d(n)+s(n)就等于sum(n),剩下的问题就是求解s(n-1)。

我们知道,对于s(n-1) AA 第三个字母只能跟之前一样AAA才能得到s(n),对于d(n-1) AB 第三个字符只有跟最后一个一样ABB才能得到s(n)

所以得出结论 s(n) = s(n-1) + d(n-1) = sum(n-1), s(n-1) = sum(n-2)

sum(n) = 2*sum(n-1) + s(n-1) = 2*sum(n-1) + sum(n-2)

def dark2():
    dark = [3,9]
    for i in range(28):
        dark.append(dark[-2]+2*dark[-1])
    print(dark)

运行结果:

[3, 9, 21, 51, 123, 297, 717, 1731, 4179, 10089, 24357, 58803, 141963, 342729, 827421, 1997571, 4822563,

11642697, 28107957, 67858611, 163825179, 395508969, 954843117, 2305195203, 5565233523, 13435662249,

32436558021, 78308778291, 189054114603, 456417007497]

 

求解暗黑字符串(网易2017秋招)