网易面试题(找啊找啊找规律)

题目

一个只包含'A'、‘B’、‘C’的字符串，如果存在某一段长度为3的连续子串中恰好‘A’、‘B’、‘C’各有一个，那么这个字符串就是纯洁的，否则这个字符串就是暗黑的。

例如：

1. BAACAACCBAAA 连续子串'CBA'中包含了‘A’、‘B’、‘C’各一个，所以为纯洁字符串

2. AABBCCAABB 不存在一个长度为3的连续子串包含‘A’、‘B’、‘C’，所以为暗黑字符串

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

输入描述：
输入一整数n，表示字符串长度为(1<=n<=30)

解析草稿

n=1:         3
n=2:        3*2（AC）+3（AA）  =9  
n=3         3*2（AAB）+3*2（ABA ）        +     3（AAA）+3*2*1（ABB）
               3+9+9=21                                                                                    
n=4         9+21+21=51   s
n=5         21+51+51=123

n=2   n=3时其实只要判断屁股后面的情况是2还是3

Code

import java.util.Scanner;

public class CheckString {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        String s = "";
        Scanner scan = new Scanner(System.in);
        int n = 0;
        long b = 0;
        while (n < 1 || n > 30) {
            System.out.println("请输入字符串长度n（1<=n<=30）");
            n = scan.nextInt();

        }
        if (n == 1) {
            b = 3;
        }
        if (n == 2) {
            b = 9;
        }else if(n>=3){ 
            b=digui(n);
        }
        System.out.println(b);
    }

    public static long digui(int n) {
        if(n==1) return 3;
        if(n==2) return 9;
        return digui(n-2)+digui(n-1)+digui(n-1);
    }