H*****l
发帖数: 1257 | 1 我把重复的位置记下来，从第7个开始，整体的string就是6部分的string合起来。
但是每次都是
Output Limit Exceeded
不知道为什么。。。
题目是：
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.
--------------------------------------------------------------
public String countAndSay(int n) {
// Start typing your Java solution below
// DO NOT write main() function
ArrayList lis = new ArrayList();
lis.add("1");
lis.add("11");
lis.add("21");
lis.add("1211");
lis.add("111221");
lis.add("2111121211");
int [] A = {2, 1, 0, 2, 2, 0};
if (n == 0) {
String s = "";
return s;
}
if (n < lis.size()) return lis.get(n - 1);
int count = lis.size();
while (count <= n) {
String str = "";
for (int i = 0; i < A.length; i++) {
str = str + lis.get(A[i] + 1);
A[i]++;
}
lis.add(str);
count++;
}
return lis.get(n - 1);
} |
z****e
发帖数: 54598 | 2 增长太快了
list吃不消了
你把以前所有的string全部记录下来是为了什么？
我的imac可以跑到33个
另外变量名不要大写开头，大忌
follows:
【在 H*****l 的大作中提到】
: 我把重复的位置记下来，从第7个开始，整体的string就是6部分的string合起来。
: 但是每次都是
: Output Limit Exceeded
: 不知道为什么。。。
: 题目是：
: 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.
|
z****e
发帖数: 54598 | 3 public class Solution {
public String countAndSay(int n) {
// Start typing your Java solution below
// DO NOT write main() function
String input = "1";
while(n>1){
input = this.cs(input);
n--;
}
return input;
}
private String cs(String cs){
String result = "";
int count = 0;
int current = -1;
for(int i=0;i
int c = Integer.parseInt(cs.charAt(i)+"");
if(c==current) count++;
else {
if(current!=-1) result = result+count+current;
count = 1;
current = c;
}
}
result = result+count+current;
return result;
}
} |
l*n
发帖数: 529 | 4 你这个int [] A = {2, 1, 0, 2, 2, 0}; 用得匪夷所思啊。
给你个正确的。
public class Solution {
public String countAndSay(int n) {
// Start typing your Java solution below
// DO NOT write main() function
if (n<=0) return "";
if (n==1) return "1";
String s = countAndSay(n-1);
StringBuilder sb = new StringBuilder();
int i=0;
int start=0;
while (start
char prev = s.charAt(start);
while (i
sb.append(i-start);
sb.append(prev);
start=i;
i++;
}
return sb.toString();
}
} |
H*****l
发帖数: 1257 | 5 我发现我理解错误了。。
原来111要变成31， 而不是2111
【在 l*n 的大作中提到】
: 你这个int [] A = {2, 1, 0, 2, 2, 0}; 用得匪夷所思啊。
: 给你个正确的。
: public class Solution {
: public String countAndSay(int n) {
: // Start typing your Java solution below
: // DO NOT write main() function
: if (n<=0) return "";
: if (n==1) return "1";
:
: String s = countAndSay(n-1);
|
t*******2
发帖数: 182 | 6 也写了一个，思路和ls的大同小异吧
public class Solution {
public String countAndSay(int n) {
if(n < 1) {
return "";
}
String result = "1";
for(int i=1; i
result = translate(result);
}
return result;
}
public String translate (String n) {
StringBuilder sb = new StringBuilder("");
String temp = n;
int[] digits = new int[temp.length()];
for(int i=0; i
digits[i] = temp.charAt(i) - '0';
}
int count = 0;
int num = digits[0];
for(int i=0; i
if(digits[i] == num) {
count++;
continue;
}
sb.append(Integer.toString(count));
sb.append(Integer.toString(num));
num = digits[i];
count = 1;
}
sb.append(Integer.toString(count));
sb.append(Integer.toString(num));
return sb.toString();
}
} |
z**********r
发帖数: 86 | 7 跟风贴一个我自己写的，java
public String countAndSay(int n) {
// Start typing your Java solution below
// DO NOT write main() function
// we can use recursion
if (n<=0)
{
return new String("");
}
else if (n==1)
{
return new String("1");
}
else
{
String base=countAndSay(n-1);
StringBuffer result=new StringBuffer();
int i=1;
char previous=base.charAt(0);
int count=1;
while(i
{
if (base.charAt(i)==previous)
{
count++;
i++;
}
else
{
result.append(count);
result.append(previous);
count=1;
previous=base.charAt(i);
i++;
}
}
// check the end
result.append(count);
result.append(previous);
return result.toString();
}
} |
H*****l
发帖数: 1257 | 8 这个解法的复杂度有2^n吧？
好像用DP，可以降到nlog(n)
【在 l*n 的大作中提到】
: 你这个int [] A = {2, 1, 0, 2, 2, 0}; 用得匪夷所思啊。
: 给你个正确的。
: public class Solution {
: public String countAndSay(int n) {
: // Start typing your Java solution below
: // DO NOT write main() function
: if (n<=0) return "";
: if (n==1) return "1";
:
: String s = countAndSay(n-1);
|
|
d****n
发帖数: 397 | 9 也跟风贴个我的，
string countandsay(int n) {
int m,i,k;
string s1,s2;
char c;
s1+='1';
while(n>1) {
m=s1.size();
c=s1[0];
k=0;
s2.clear();
for(i=0;i
if(s1[i]==c) {
k++;
}
else {
s2+=(k+'0');
s2+=c;
c=s1[i];
k=1;
}
}
s2+=(k+'0');
s2+=c;
s1.clear();
s1+=s2;
n--;
}
return s1;
}
small和large judge都能通过。这个时间复杂度不好算吧。我怎么感觉是exponential
的。
n=100都要算好长时间。
【在 H*****l 的大作中提到】
: 这个解法的复杂度有2^n吧？
: 好像用DP，可以降到nlog(n)
|
l*n
发帖数: 529 | 10 简单的递归而已，哪来的2^n啊
【在 H*****l 的大作中提到】
: 这个解法的复杂度有2^n吧？
: 好像用DP，可以降到nlog(n)
|
|
|
d****n
发帖数: 397 | 11 有吧。因为是T(n)=T(n-1)+O(2^(n-1))。所以即便是简单递归，也是exponential的。
我试了，不用递归，循环也是exponential的。因为nth string长度就是exponential的
吧。还有n=100,要算很长时间。
【在 l*n 的大作中提到】
: 简单的递归而已，哪来的2^n啊
|
l*********o
发帖数: 3091 | 12 #include
#include
int convert(char* src, char* dst)
{
*dst = 0;
int pos;
char str[64];
while(*src)
{
if(*src < '0' || *src > '9') return 1;
pos = 1;
while(*src==*(src+pos))pos++;
sprintf(str, "%d", pos);
strcat(dst, str);
dst += strlen(str);
sprintf(str, "%c", *src);
strcat(dst, str);
dst += strlen(str);
src += pos;
}
return 0;
}
int main()
{
int n = 29;
int i;
char src[1024*1024] = {0};
char dst[1024*1024] = {0};
strcpy(src, "1");
for (i = 2; i <= n; i++)
{
if(i%2 == 0)
{
if(convert(src, dst))
{
printf("There is error at step %d", i);
break;
}
printf("step %d, str=%s", i, dst);
}
else
{
if(convert(dst, src))
{
printf("There is error at step %d", i);
break;
}
printf("step %d, str=%s", i, src);
}
}
return 0;
} |
b**m
发帖数: 1466 | 13 public class Solution {
public String countAndSay(int n) {
if(n==1){
return "1";
}
StringBuilder r = new StringBuilder();
String work = countAndSay(n-1);
int count=1;
int c=work.charAt(0)-'0';
for(int i=1;i
int num = work.charAt(i) -'0';
if(num ==c){
count ++;
}else{
r.append(count);
r.append(c);
c=num;
count=1;
}
}
r.append(count);
r.append(c);
return r.toString();
}
} |
l*n
发帖数: 529 | 14 我真是凌乱了。不是顺序把n-1的串扫一遍吗，怎么就成了2^n了？
【在 d****n 的大作中提到】
: 有吧。因为是T(n)=T(n-1)+O(2^(n-1))。所以即便是简单递归，也是exponential的。
: 我试了，不用递归，循环也是exponential的。因为nth string长度就是exponential的
: 吧。还有n=100,要算很长时间。
|
d****n
发帖数: 397 | 15 http://en.wikipedia.org/wiki/Look-and-say_sequence
因为把n-1串扫一边不是O(n),第n-1串的长度是O(lamda^n), lamda= 1.303577269。所
以不是O(n^2)。
【在 l*n 的大作中提到】
: 我真是凌乱了。不是顺序把n-1的串扫一遍吗，怎么就成了2^n了？
|
