Received SR reply TSC - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>EB23 - 劳工卡

Received SR reply TSC

Received SR reply TSC# EB23 - 劳工卡

H*l2016-03-03 08:03

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);
}

e*12016-03-03 08:03

2 楼

I did a Service Request in Feb. and got a reply today. Is the reply a normal
message? My PD is 12/2011.
The status of this service request is:
We have received your service request and researched the status of your case
. We have had to perform additional review and this has caused a delay in
processing time. Your case is currently in line for processing and
adjudication. Cases are processed in the order in which they were received.
What You Can Do
Please see the "Online Services" below to check the status of your case in
the future.
We hope this information is helpful to you.

z*e2016-03-03 08:03

3 楼

增长太快了
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.

c*n2016-03-03 08:03

4 楼

看样子是按RD审批？

z*e2016-03-03 08:03

5 楼

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;iint 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;
}
}

a*a2016-03-03 08:03

6 楼

模版回复，没有什么信息。
USCIS对外号称485按照RD审批，但是由于中印EB23存在排期倒退的事实，具体怎么操作
的谁也不知道，估计就是RD和PD都要看。

l*n2016-03-03 08:03

7 楼

你这个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 (startchar prev = s.charAt(start);
while (isb.append(i-start);
sb.append(prev);

start=i;
i++;
}

return sb.toString();
}
}

G*62016-03-03 08:03

8 楼

和我上个月收到的SR一样.找议员试试.

H*l2016-03-03 08:03

9 楼

我发现我理解错误了。。
原来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*22016-03-03 08:03

10 楼

也写了一个，思路和ls的大同小异吧
public class Solution {
public String countAndSay(int n) {
if(n < 1) {
return "";
}

String result = "1";

for(int i=1; iresult = 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; idigits[i] = temp.charAt(i) - '0';
}

int count = 0;
int num = digits[0];
for(int i=0; iif(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*r2016-03-03 08:03

11 楼

跟风贴一个我自己写的，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*l2016-03-03 08:03

12 楼

这个解法的复杂度有2^n吧？
好像用DP，可以降到nlog(n)

【在 l*n 的大作中提到】

d*n2016-03-03 08:03

13 楼

也跟风贴个我的，
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;iif(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*n2016-03-03 08:03

14 楼

简单的递归而已，哪来的2^n啊

【在 H*****l 的大作中提到】

: 这个解法的复杂度有2^n吧？
: 好像用DP，可以降到nlog(n)

d*n2016-03-03 08:03

15 楼

有吧。因为是T(n)=T(n-1)+O(2^(n-1))。所以即便是简单递归，也是exponential的。
我试了，不用递归，循环也是exponential的。因为nth string长度就是exponential的
吧。还有n=100,要算很长时间。

【在 l*n 的大作中提到】

: 简单的递归而已，哪来的2^n啊

l*o2016-03-03 08:03

16 楼

#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*m2016-03-03 08:03

17 楼

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*n2016-03-03 08:03

18 楼

我真是凌乱了。不是顺序把n-1的串扫一遍吗，怎么就成了2^n了？

【在 d****n 的大作中提到】

: 有吧。因为是T(n)=T(n-1)+O(2^(n-1))。所以即便是简单递归，也是exponential的。
: 我试了，不用递归，循环也是exponential的。因为nth string长度就是exponential的
: 吧。还有n=100,要算很长时间。

d*n2016-03-03 08:03

19 楼

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了？