暗黑字符串个数

admin管理员组

文章数量:1516870

暗黑字符串个数

 某公司在线笔试题：一个字符串仅由'A','B','C'三个字符组成，若字符串中不存在'A','B','C'三个字符相邻的子串(比如ABC，BAC等)，则该字符串称为暗黑字符串，否则称为单纯字符串。

例子：字符串 AABBACCA，由于存在BAC子串，所以该字符串为单纯字符串。

字符串 AABBCC，由于不存在A,B,C相邻构成的子串，所以该字符串为暗黑字符串。

求长度为L的此种字符串中有多少种是暗黑字符串？

比如长度为1的字符串中，暗黑字符串总共有3种(即"A","B","C")，

长度为2的字符串中，暗黑字符串总共有9种(两个位置，每个位置有三张可能，3*3=9)，

长度为3的字符串中，暗黑字符串总共有21种(三个位置，每个位置有三种可能，总共有3*3*3=27种，去除纯净字符串3!=6，结果为27-6=21种)。

输入：

2

3

输出：

9

21

主要思想是将长度为L的暗黑字符串根据最后两个字符是否一样分成两类y和x(比如*AA记为y和*AB记为x等)，最后两个字符不一样的暗黑字符串个数为x(L)，一样的总个数为y(L)，长度为L的暗黑字符串总个数为A(L)=x(L)+y(L)。接下来考虑从长度为L的暗黑字符串如何生成长度为L+1的暗黑字符串。对于最后两个字符一样的长度为L的暗黑字符串(总个数为y(L))，在后面添加A, B, C任意一个字符都可以生成长度为L+1的暗黑字符串，比如*AA可以生成*AAA，*AAB，*AAC，生成的总数量为3y(L)(每个长度为L的y都可以生成三个新的长度为L+1的暗黑字符串，其中有一个为y，两个为x)，其中y(L)个属于y，2y(L)个属于x。对于最后两个字符不一样的长度为L的暗黑字符串(总个数为x(L))，在后面添加那两个不一样的字符中任意一个也可以生成长度为L+1的暗黑字符串，比如*AB可以生成*ABA和*ABB，生成的总数量为2x(L)(每个长度为L的x都可以生成两个长度为L+1的暗黑字符串，其中一个为x，一个为y)，其中x(L)个属于x，x(L)个属于y。

通过以上分析可知：

A(L)=x(L)+y(L)，x(L)为长度为L的暗黑字符串中最后两个字符不一样的总个数，y(L)为最后两个字符一样的总个数。

x(L+1)=x(L)+2y(L)，长度为L+1且最后两个字符不一样的暗黑字符串是由长度为L的x和y演变而来，且数量分别为x(L)和2y(L)。

y(L+1)=x(L)+y(L)，长度为L+1且最后两个字符一样的暗黑字符串是由长度为L的x和y演变而来，且数量分别为x(L)和y(L)。

A(L+1)=x(L+1)+y(L+1)

具体代码如下：

 1 package com.test1;
 2 
 3 import java.util.Scanner;
 4 
 5 public class DarkString {
 6     /*
 7      * 主要想法：长度为L的暗黑字符串可以根据最后两个字符分成两类，最后两个字符是一样的和最后两个不一样的情况。
 8      * 长度为L+1的暗黑字符串可以由长度为L的暗黑字符串生成。
 9      */
10     public static long totalCount(long length){
11         if(length < 1)
12             return 0;
13         if(length == 1)
14             return 3;
15         /*
16          * x1表示长度为L的字符串最后两个字符不一样的暗黑字符串个数（比如*AB,*AC等），
17          * 对于长度为2的暗黑字符串，总个数为6
18          */
19         long x1 = 6;
20         /*
21          * y1表示一个字符串最后连个字符一样的暗黑字符串个数（比如*AA,*BB等），
22          * 对于长度为2的暗黑字符串，总个数为3
23          */
24         long y1 = 3;
25         //start from string with length 2
26         length = length - 2;
27         while(length-- > 0){
28             long x2 = x1 + 2*y1;
29             long y2 = x1 + y1;
30             x1 = x2;
31             y1 = y2;
32         }
33         //长度为length的字符串中，暗黑字符串总个数
34         return x1+y1;
35     }
36     
37     public static void main(String[] args){
38         Scanner scanner = new Scanner(System.in);
39         while(scanner.hasNext()){
40             int len = scanner.nextInt();
41             System.out.println(totalCount((long)len));
42         }
43         scanner.close();
44     }
45 }

转载于:.html

本文标签： 暗黑字符串个数