Leetcode OJ的编译器是？ - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

Leetcode OJ的编译器是？

Leetcode OJ的编译器是？# JobHunting - 待字闺中

i*72012-09-22 07:09

1 楼

同样的题目我把leetcode oj上的sample放到我自己的IDE上跑就没问题，但是在
leetcode oj上却跑出来了奇怪的结果。。这是为啥？

i*e2012-09-22 07:09

2 楼

把你代码贴上来，我可以直接告诉你哪里出了问题。

i*72012-09-22 07:09

3 楼

哇。leetcode大神直接来回复我。。。orz...
是那题 add binary的。你的test cases里面有25%左右过不了。
但是我把那些过不了的test case放到我自己的x-code ide上，又得到和你expected一
样的答案。
string addBinary(string a, string b) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int next = 0;
int length = max(a.size(),b.size());
char *res = new char[length + 1];
memset(res,0,length);
int count1,count2;
count1 = a.size() - 1;
count2 = b.size() - 1;
while(count1 >= 0 || count2 >= 0)
{
int b1,b2;
b1 = b2 = 0;
if(count1 >= 0)
b1 = a[count1] - '0';
if(count2 >= 0)
b2 = b[count2] - '0';
int curbit = b1+b2+next;
next = curbit/2;
curbit = curbit%2;
res[length] = curbit + '0';
length--;
count1--;
count2--;
}
if(next == 1){
res[0] = '1';
string s(res);
return s;
}
else{
string s(res + 1);
return s;
}
}

【在 i**********e 的大作中提到】

: 把你代码贴上来，我可以直接告诉你哪里出了问题。

h*62012-09-22 07:09

4 楼

res没有截止符的空间，res截止符没有赋0，res没有释放内存。
char *res = new char[length + 2];
memset(res, 0, length + 2);
delete []res;
delete []res;

i*72012-09-22 07:09

5 楼

memset就已经帮所有可能的位置都赋上了截止符了。
length是max(x,y)
也就是两者取长了。两个二进制数相加的长度基本不可能超过length + 1了。
举个简单的例子
10 + 10 = 100。也就是两个长度为2的二进制数相加才刚好到达长度为3的二进制数。
所以一个二进制数长度为x，另一个为y。
最大长度不会超过max(x,y) + 1。
所以我取length + 2就是在最大可能值的max(x,y) + 1的前提下再给了最后一位截止符
的空间。

【在 h**6 的大作中提到】

: res没有截止符的空间，res截止符没有赋0，res没有释放内存。
: char *res = new char[length + 2];
: memset(res, 0, length + 2);
: delete []res;
: delete []res;

h*e2012-09-22 07:09

6 楼

小评一下：这是用C的风格写的C++程序。例如这一段：
char *res = new char[length + 1];
memset(res,0,length);
为什么不直接用
string res(length+1, '\0');

p*g2012-09-22 07:09

7 楼

同意
1. 我試了一下樓主的程序
OJ上large test裡出錯的情況都是輸出的string 最後有幾個其他字符
感覺是內存釋放問題？
2. 如果用c++ 的string，
直接用下面這樣的，
當然，其他高手可能有更好的辦法；
string rv;
int next = 0;
int length = max(a.size(),b.size());
int count1,count2;
count1 = a.size() - 1;
count2 = b.size() - 1;
while(count1 >= 0 || count2 >= 0)
{
int b1,b2;
b1 = b2 = 0;
if(count1 >= 0)
b1 = a[count1] - '0';
if(count2 >= 0)
b2 = b[count2] - '0';
int curbit = b1+b2+next;
next = curbit/2;
curbit = curbit%2;
rv.insert(rv.begin(), (char)( curbit + '0'));
length--;
count1--;
count2--;
}
if(next == 1){
rv.insert(rv.begin(), '1');
}

return rv;

【在 h****e 的大作中提到】

: 小评一下：这是用C的风格写的C++程序。例如这一段：
: char *res = new char[length + 1];
: memset(res,0,length);
: 为什么不直接用
: string res(length+1, '\0');

i*72012-09-22 07:09

8 楼

我明白你的意思。
我只是考虑到一个问题
实际上string 是 Immutable的，也就是你对它做任何改动，都不是inplace的，只是产
生一个新的改动过的复制品。
这样比能实际inplace操作的char数组要慢的多和浪费空间的多。
所以我先从char array操作，最后直接通过操作得来的char array直接创造一个string
。这样应该会效率很多。

【在 h****e 的大作中提到】

: 小评一下：这是用C的风格写的C++程序。例如这一段：
: char *res = new char[length + 1];
: memset(res,0,length);
: 为什么不直接用
: string res(length+1, '\0');

y*g2012-09-22 07:09

9 楼

java string是immutable的
我没看错的话，你用的是c++ string？

string

【在 i*********7 的大作中提到】

: 我明白你的意思。
: 我只是考虑到一个问题
: 实际上string 是 Immutable的，也就是你对它做任何改动，都不是inplace的，只是产
: 生一个新的改动过的复制品。
: 这样比能实际inplace操作的char数组要慢的多和浪费空间的多。
: 所以我先从char array操作，最后直接通过操作得来的char array直接创造一个string
: 。这样应该会效率很多。

i*72012-09-22 07:09

10 楼

我怎么记得programming interview exposed上写的c++的string同样也是Immutable的
。。。

【在 y*******g 的大作中提到】

: java string是immutable的
: 我没看错的话，你用的是c++ string？
:
: string

y*g2012-09-22 07:09

11 楼

你试一下不就知道了。

【在 i*********7 的大作中提到】

: 我怎么记得programming interview exposed上写的c++的string同样也是Immutable的
: 。。。

h*62012-09-22 07:09

12 楼

你只分配了length+1的空间，没有预留截止符的位置。
你没有对res最后一个字节赋0，这才是截止符的位置。

【在 i*********7 的大作中提到】

: memset就已经帮所有可能的位置都赋上了截止符了。
: length是max(x,y)
: 也就是两者取长了。两个二进制数相加的长度基本不可能超过length + 1了。
: 举个简单的例子
: 10 + 10 = 100。也就是两个长度为2的二进制数相加才刚好到达长度为3的二进制数。
: 所以一个二进制数长度为x，另一个为y。
: 最大长度不会超过max(x,y) + 1。
: 所以我取length + 2就是在最大可能值的max(x,y) + 1的前提下再给了最后一位截止符
: 的空间。

i*72012-09-22 07:09

13 楼

大哥我错了，原来好像是mutable的。。
我试了一下这两段代码
string a("abc");
cout<a = a + "bsdadsadasdasdc";
cout<发现输出来的内存地址是一样的。

【在 y*******g 的大作中提到】

: 你试一下不就知道了。

i*72012-09-22 07:09

14 楼

嗯。好像的确是自己大意了。
我回头改改再试试。
谢谢啦

【在 h**6 的大作中提到】

: 你只分配了length+1的空间，没有预留截止符的位置。
: 你没有对res最后一个字节赋0，这才是截止符的位置。

i*e2012-09-22 07:09

15 楼

这是正解。
你看，只要贴代码，问题都被检测出来了。

【在 h**6 的大作中提到】

: res没有截止符的空间，res截止符没有赋0，res没有释放内存。
: char *res = new char[length + 2];
: memset(res, 0, length + 2);
: delete []res;
: delete []res;

p*g2012-09-22 07:09

16 楼

但是std::string 是不需要terminator的
這樣直接把原來生成的char array生成一個string 然後返回
這樣為啥出錯呢

【在 i**********e 的大作中提到】

: 这是正解。
: 你看，只要贴代码，问题都被检测出来了。

k*x2012-09-22 07:09

17 楼

跪了，原来这位leetcode大佬是老中。。。

【在 i**********e 的大作中提到】

: 把你代码贴上来，我可以直接告诉你哪里出了问题。

B*12012-09-22 07:09

18 楼

我跪了，你才知道啊。

【在 k***x 的大作中提到】

: 跪了，原来这位leetcode大佬是老中。。。

i*e2012-09-22 07:09

19 楼

string ( const char * s );
Content is initialized to a copy of the string formed by the null-
terminated character sequence (C string) pointed by s. The length of the
character sequence is determined by the first occurrence of a null character
(as determined by traits.length(s)). This version can be used to initialize
a string object using a string literal constant.
http://www.cplusplus.com/reference/string/string/string/

【在 p*g 的大作中提到】

: 但是std::string 是不需要terminator的
: 這樣直接把原來生成的char array生成一個string 然後返回
: 這樣為啥出錯呢

S*t2012-09-22 07:09

20 楼

我还认识这位牛人，吃过几次饭，哈哈哈

【在 B*******1 的大作中提到】

: 我跪了，你才知道啊。

y*g2012-09-22 07:09

21 楼

跪了

【在 S********t 的大作中提到】

: 我还认识这位牛人，吃过几次饭，哈哈哈

B*12012-09-22 07:09

22 楼

膜拜啊，希望有一天我也可以和大牛吃顿饭。

【在 S********t 的大作中提到】

: 我还认识这位牛人，吃过几次饭，哈哈哈

d*e2012-09-22 07:09

23 楼

re... me too...

【在 S********t 的大作中提到】

: 我还认识这位牛人，吃过几次饭，哈哈哈