首先，题意就把我搞蒙了，最后才发现下一个字符串是通过上一个字符串的某种规则生成的。所以，第一感觉是可以使用递归，还是要注意处理边界值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution {
public String cas(int n){
if(n==1){
return "1";
}else if(n==2){
return "11";
}else{
String count=cas(n-1);
Character nowNum=count.charAt(0);
String res="";
int sameTime=1;
for(int i=1;i<count.length();i++){
if(count.charAt(i)==nowNum){
sameTime++;
}else{
res+=Integer.toString(sameTime)+nowNum;
nowNum=count.charAt(i);
sameTime=1;
}
if(i==count.length()-1){
res+=Integer.toString(sameTime)+nowNum;
}
}
return res;
}
}
public String countAndSay(int n) {
return cas(n);
}
}
|
但发现时间效率不高，只超过了不到 17%的人。
把递归改成循环，发现运行效率更低
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public String countAndSay(int n) {
String res="1";
if(n>=2)
res="11";
for(int i=3;i<=n;i++){
String tempRes="";
Character nowNum=res.charAt(0);
int sameTime=1;
for(int j=1;j<res.length();j++){
if(res.charAt(j)==nowNum){
sameTime++;
}else{
tempRes+=Integer.toString(sameTime)+nowNum;
nowNum=res.charAt(j);
sameTime=1;
}
}
tempRes+=Integer.toString(sameTime)+nowNum;
res=tempRes;
}
return res;
}
}
|
看了别人的代码，才知道 Java 有 StringBuilder 和 toCharArray 两个方法，可以使运行效率加快，打败了将近 50%的提交。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public String countAndSay(int n) {
String res="1";
if(n>=2)
res="11";
for(int i=3;i<=n;i++){
StringBuffer tempRes=new StringBuffer();
char[] resChar=res.toCharArray();
Character nowNum=resChar[0];
int sameTime=1;
for(int j=1;j<resChar.length;j++){
if(resChar[j]==nowNum){
sameTime++;
}else{
tempRes.append(Integer.toString(sameTime));
tempRes.append(nowNum);
nowNum=resChar[j];
sameTime=1;
}
}
tempRes.append(Integer.toString(sameTime));
tempRes.append(nowNum);
res=tempRes.toString();
}
return res;
}
}
|