首页 > 代码库 > 网易真题之暗黑字符串
网易真题之暗黑字符串
题目如下：
字符串只包含‘A’,‘B‘,‘C‘，对于一个任意长度的字符串，如果存在连续的3个字符同时包含"A","B""C"，那这个字符串是纯净的，否则称为暗黑字符串。比如“BCBBACBBCA”就是纯净字符串，“ABBAACCBBA”就是暗黑字符串。
input：一个整数，表示字符串的长度
output：暗黑字符串可能的个数
分析：
这种题目使用遍历或者排列组合求解，基本不可能，运算量巨大。可以通过查找关系，列出通项公式。
以f(n)表示n位字符串存在的暗黑字符串的个数，有以下关系：f(n)=f(n-2)*3+(f(n-1)-f(n-2))*2
代码如下：
package project001;import java.util.ArrayList;import java.util.Arrays;import java.util.List;import java.util.Scanner;public class Main05 { public static void main(String[] args) { // TODO Auto-generated method stub// System.out.println(Rev(120)); Scanner in = new Scanner(System.in); while(in.hasNext()){ int a = in.nextInt(); System.out.println(getN(a)); } } public static long getN(int k){ List<Long> list = new ArrayList<Long>(); list.add((long) 3); list.add((long) 9); list.add((long) 21); for(int i=1;i<=k;i++){ if(k<=3) break; list.add(3*list.get(list.size()-2)+2*(list.get(list.size()-1)-(list.get(list.size()-2)))); } return list.get(k-1); }}
网易真题之暗黑字符串
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。