问题描述
The count-and-say sequence is the sequence of integers with the first five terms as following:
- 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 where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence.
Note: Each term of the sequence of integers will be represented as a string.
Example 1:
Input: 1 Output: “1” Example 2:
Input: 4 Output: “1211”
解决思路
以1211举例（”-“是我用来占位的，因为蛋疼的markdown对空格非常不友好）
第一次：
——–1 2 1 1
count-0 1
pre—* 1
str
count置1，pre等于第一位的1
第二次：
——–1 2 1 1
count-0 1 1
pre—. 1 2
str——11
pre等于1，不等于第二位的2，,str等于11（count + pre） 。count置1，pre置第二位的2
第三次：
——–1 2 1 1
count-0 1 1 1
pre—. 1 2 1
str—–1112
pre等于2，不等于第三位的的1，str等于1112（原来的str + count + pre）。count置1，pre置第三位的1
第四次：
——–1 2 1 1
count-0 1 1 1 2
pre—. 1 2 1 1
str—–1112
pre等于1，等于第四位的1，str不变。count加1，pre等于第四位的1
循环结束：
str加上末尾的count和str变为111221
TVT好像占位之后显示还是有点问题啊，天杀的markdown就不能只能一点吗？讲究看看吧。。。
代码
class Solution {
public String countAndSay(int n) {
if(n <= 0) return "";
//initial the string
String str = "1";
//since the first str has defined before, so i start from 1 instead of 0
for(int i = 1; i < n; i++){
int count = 0;
char pre = '*';// use * to represent default vaule
StringBuilder sb = new StringBuilder();
for(int j = 0; j < str.length(); j++){
//pre == '*' represent the first step; pre =='str.charAt(j)' represent the last char is the same as the current char, so both condition the count will add 1
if(pre == '*' || pre == str.charAt(j)){
count++;
}else{//no same char exist, so both count and char will be add to sb
sb.append(count + Character.toString(pre));
count = 1;
}
//pre record char as the last one in next loop
pre = str.charAt(j);
}
//to append the last count and char in the loop
sb.append(count + Character.toString(pre));
str = sb.toString();
}
return str;
}
}
小感想
虽然是个easy题，但这种方法的确不太容易想到，还是使用两个指针。
