所谓外观数列,就是后一个数列是对前一个数列的描述。打个比方:
序列号1: 1
序列号2: 11 这是对上一个数据1的描述,上一个数据为1个1,记做:11.
序列号3: 21 这是对上一个数据11的描述,上一个数据为2个1,记做:21.
序列号4: 1211 这是对上一个数据21的描述,上一个数据为1个2,1个1,记做:1211.
...
题目是,给出相应的序列号,算出对应的外观数列。
要找序列号为n
的外观数列,那么就得知道序列号为n-1
的外观数列的值,要想知道序列号为n-1
的外观数列的值,就得知道序列号为n-2
的外观数列的值...
以此类推,很容易联想到用递归,而递归的终止条件可以是以下两个:
if (n == 1) return "1";
if (n == 2) return "11";
这样做就能保证preString
的长度至少大于等于2,不用做额外的判断。preString
代表上一个外观数列的值,在下面的代码中会提到。
然后,两指针最初分别指向外观数列中第0位和第1位,当指向的元素相同时,right
指针向前移动一位,否则添加对应元素。
left
和right
指针的差值就是某个数字的出现的次数。
// 递归算法
private String getStringByCount(int n) {
if (n == 1) return "1";
if (n == 2) return "11";
// 递归计算前一个元素的值
char[] preString = getStringByCount(n - 1).toCharArray();
int left = 0;
StringBuilder result = new StringBuilder();
for (int right = 1; right < preString.length; ) {
// 不同位上的元素不一样
if (preString[left] != preString[right]) {
// 开始构建描述数列,此时right - left代表着中间隔了多少个相同的元素
result.append((right - left)).append(preString[left]);
left = right;
}
// 每个遍历,right右移一位
right++;
// 当达到元素的末尾时
if (right == preString.length) {
result.append((right - left)).append(preString[left]);
}
}
return result.toString();
}