请教leetcode上的count and say - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

请教leetcode上的count and say

请教leetcode上的count and say# JobHunting - 待字闺中

m*82012-10-17 07:10

1 楼

leetcode上的count and say这题，是一个什么思路？我在另一个帖子上有看到这题的
代码，但是我水平较低，主要想请教一下这题是什么思路。
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.
我看到的帖子是在，http://www.mitbbs.com/article_t/JobHunting/32147785.html
谢谢

d*e2012-10-17 07:10

2 楼

就是连续数字的个数

follows:

【在 m******8 的大作中提到】

: leetcode上的count and say这题，是一个什么思路？我在另一个帖子上有看到这题的
: 代码，但是我水平较低，主要想请教一下这题是什么思路。
: 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.

l*c2012-10-17 07:10

3 楼

记得这是我练的第一道题，
就是从1往下做就是了吧，
lz先把题理解了，理解了做应该不难。
1
11
21
1211
111221
312211
13112221
。。。。。

I*C2012-10-17 07:10

4 楼

1 "1" 1个1=〉11 （相当于把里面的汉字‘个’去掉以后省的数串）
2 "11" 2个1=〉21
3 "21" 1个2，1个1=〉1211
4 "1211" 1个1，1个2，2个1 =〉111221
5 "111221" 3个1，2个2，1个1 =〉312211
6 "312211"
7 "13112221"
8 "1113213211"
9 "31131211131221"
10 "13211311123113112211"
11 "11131221133112132113212221"
12 "3113112221232112111312211312113211"
13 "1321132132111213122112311311222113111221131221"
14 "11131221131211131231121113112221121321132132211331222113112211"

follows:

【在 m******8 的大作中提到】

a*y2012-10-17 07:10

5 楼

private static java.util.Hashtable cache = new java.util.
Hashtable();
public String countAndSay(int n)
{
// Start typing your Java solution below
// DO NOT write main() function
Object result = cache.get(new Integer(n));
if(result != null)
{
return (String)result;
}
if(n == 1)
{
cache.put(new Integer(1), "1");
return "1";
}
else
{
String str = countAndSay(n-1);
String re = sayOneString(str);
cache.put(new Integer(n), re);
return re;
}
}
public static String sayOneString(String str)
{
int start = 0;
int end = 1;
StringBuffer sb = new StringBuffer();
while(start < str.length())
{
while(end < str.length() && str.charAt(end) == str.charAt(start
))
{
end ++;
}
sb.append(""+(end-start)+str.charAt(start));
start = end;
end = start+1;
}
return sb.toString();
}

follows:

【在 m******8 的大作中提到】