Count and Say
The count-and-say sequence is the sequence of integers beginning as follows: 1, 11, 21, 1211, 111221, … 1 is read off as “one 1” or 11. 11 is read off as “two 1s” or 21. 21 is read off as “one 2, then one 1” or 1211. Given an integer n, generate the nth sequence.
Java实现 类似于斐波拉契数列的生成,由前一个生成后一个,我的解法也是这个,下面附上AC代码
public String countAndSay(int n) {
if(n == 0 || n == 1){
return "1";
}
String res = "11"; //第一个答案
for(int i = 2; i < n; ++i){
res = getNextSay(res);
}
return res;
}
/**
* 根据上一个答案获得下一个需要输出的Say
*/
private String getNextSay(String res) {
StringBuilder sb = new StringBuilder(); //返回答案
int num = 1; //倍数
char formerChar = res.charAt(0);
for(int i = 1; i < res.length(); ++i){
if(res.charAt(i) == formerChar){
//下一个字符与上一个相同
//倍数加一
num++;
continue;
}else{
//下一个字符与上一个字符不同
//输出倍数个formerChar
sb.append(Integer.toString(num) + formerChar);
//更新
formerChar = res.charAt(i);
num = 1;
}
}
sb.append(Integer.toString(num) + formerChar);
return sb.toString();
}