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.
Note: The sequence of integers will be represented as a string.
Naive Way: 很有趣的题目。第一次写就成功了,看来是一道简单的题目。通过读取上一次的String生成当前的String。
public class Solution {
public String countAndSay(int n) {
String str = "1";
for(int i = 2;i <= n;i++){
int j = 0;
String newStr = "";
while(j < str.length()){
int count = 1;
while(j+count < str.length()){
if(str.charAt(j)!=str.charAt(j+count))
break;
count++;
}
newStr += (char)(count+'0');
newStr += str.charAt(j);
j += count;
}
str = newStr;
}
return str;
}
}
Improved Way: Discuss里有用recursive写的,感觉会更舒服些。
No comments:
Post a Comment