华为OD机试之数列描述（Java源码）

数列描述

题目描述

有一个数列a[N] (N=60)，从a[0]开始，每一项都是一个数字。数列中a[n+1]都是a[n]的描述。其中a[0]=1。规则如下：

a[0]:1
a[1]:11(含义：其前一项a[0]=1是1个1，即“11”。表示a[0]从左到右，连续出现了1次“1”）
a[2]:21(含义：其前一项a[1]=11，从左到右：是由两个1组成，即“21”。表示a[1]从左到右，连续出现了两次“1”)
a[3]:1211(含义：其前一项a[2]=21，从左到右：是由一个2和一个1组成，即“1211”。表示a[2]从左到右，连续出现了1次“2”，然后又连续出现了1次“1”)
a[4]:111221(含义：其前一项a[3]=1211，从左到右：是由一个1、一个2、两个1组成，即“111221”。表示a[3]从左到右，连续出现了1次“1”，连续出现了1次“2”，连续出现了两次“1”)

请输出这个数列的第n项结果（a[n]，0≤n≤59）。

输入描述

数列的第n项(0≤n≤59) 例如
4

输出描述

数列的内容
111221

源码和解析
解析：

这个题重在理解即求连续字符的个数与字符组成的新数字
如第一项为1 （1个1）那么下一项是11 （2个1），下一项是21（1个2 和1个1）=>1211
（1个1，1个2，2个1）=>111221(3个1,2个2,1个1)=？312211…
这个题其实也还是偏逻辑性强一些，当然其也涉及到DP算法（动态规划算法），算法不知道无所谓，但是要有这种处理问题的思维。
注意：

如果这个题用String或者int来存储值，那么结果是打印不出来的。
因为最大字符长度(65535) ，可以通过Integer.MAX_VALUE得到。
我这里使用的List来进行存储的。因为其长度可以自动扩展
如果使用的是Eclipse软件，那么其控制台打印字符长度也不能过长，否则就是空白。不利于测试。所以需要对Eclipse进行配置。
原本打算使用一个List内部装一个List，这样可以实现将前面所有产生的过程数据都存储起来，但是这样有点耗费内存。所以用一个List存储结果即可。

示例代码：

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class T40 {public static void main(String[] args) {List<Character> first = new ArrayList<Character>();first.add('1');Scanner sc = new Scanner(System.in);int num = sc.nextInt();for (int i = 1; i < num + 1; i++) {first=next(first);}// String 超出长度就不显示了 大概37就超出了// StringBuilder是能存的 但是toString后就空白了System.out.println(first.size());for(Character c:first){System.out.print(c);}}public static List<Character> next(List<Character> number) {List<Character> numList = new ArrayList<Character>();if (number.size() == 1) {numList.add('1');numList.add(number.get(0));return numList;}int start = 0;int end = 1;while (end < number.size()) {if (number.get(end) == number.get(start)) {if (end == number.size() - 1) {// 相等且到达最后一位String num = "" + (end - start + 1);for (int i = 0; i < num.length(); i++) {numList.add(num.charAt(i));}numList.add(number.get(start));}end++;} else {String num = "" + (end - start);for (int i = 0; i < num.length(); i++) {numList.add(num.charAt(i));}numList.add(number.get(start));start = end;end++;// 有可能直接到达末尾if (end == number.size()) {String num1 = "" + (end - start);for (int i = 0; i < num1.length(); i++) {numList.add(num1.charAt(i));}numList.add(number.get(start));}}}return numList;}
}