u*****o
发帖数: 1224 | 1 请教大家最近碰到的一道题，两个大数，存在string里，return their sum as
another string.
我当时先把两个string reverse，12345--》 54321； 6789=>9876
然后把短的那个补足0，9876=》98760
然后54321和98760相加，一个个存在string里，最后再reverse result.
面试官说不efficient，让我另外想，我又说了个用两个stack分别装string里的数，
然后一个个pop出来，pop的时候相加，按顺序存到最后的string里。
我两个solution都写了，他还是不满意。请教大家这题还有什么更有效的办法吗？
大数相加不是leetcode的题吧？我不记得哪里做过，如果在cc150里，也请大家告诉我
一声，我没怎么翻过那本书。
谢谢了先！ |
e*******s
发帖数: 1979 | 2 会不会用bit操作更快?
【在 u*****o 的大作中提到】
: 请教大家最近碰到的一道题，两个大数，存在string里，return their sum as
: another string.
: 我当时先把两个string reverse，12345--》 54321； 6789=>9876
: 然后把短的那个补足0，9876=》98760
: 然后54321和98760相加，一个个存在string里，最后再reverse result.
: 面试官说不efficient，让我另外想，我又说了个用两个stack分别装string里的数，
: 然后一个个pop出来，pop的时候相加，按顺序存到最后的string里。
: 我两个solution都写了，他还是不满意。请教大家这题还有什么更有效的办法吗？
: 大数相加不是leetcode的题吧？我不记得哪里做过，如果在cc150里，也请大家告诉我
: 一声，我没怎么翻过那本书。
|
s********u
发帖数: 1109 | 3 没太明白你为什么要reverse+补0。联想Add Binary那道题就可以知道，这题是字符串
不是链表，字符串可以从后往前访问，所以完全可以不补0，直接从后往前访问。当某
一个字符串用光时，再处理另外一个字符串剩下的（注意进位），最后再看有没有多余
的一个进位。
毕竟你string是可以一直"push_front"的
Leetcode原题：
class Solution {
public:
string addBinary(string a, string b) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
int aIndex = a.size() - 1, bIndex = b.size() - 1;
string res;
int carry = 0;
while( aIndex >= 0 && bIndex >= 0){
int local = carry + (a[aIndex] -'0') + (b[bIndex] - '0');
int sum = local%2;
carry = local/2;
char tmp = '0' + sum;
res = tmp + res;
aIndex--; bIndex--;
}
while( aIndex >= 0){
int local = carry + (a[aIndex] -'0');
int sum = local%2;
carry = local/2;
char tmp = '0' + sum;
res = tmp + res;
aIndex--;
}
while( bIndex >= 0){
int local = carry + (b[bIndex] -'0');
int sum = local%2;
carry = local/2;
char tmp = '0' + sum;
res = tmp + res;
bIndex--;
}
if( carry > 0){
char tmp = '0' + carry;
res = tmp + res;
}
return res;
}
}; |
z****e
发帖数: 54598 | 4 overdesign了
我想法跟上面一样
就是直接实现你手算加法就行了
考察点应该在string的各个方法的操作上
实现题
【在 u*****o 的大作中提到】
: 请教大家最近碰到的一道题，两个大数，存在string里，return their sum as
: another string.
: 我当时先把两个string reverse，12345--》 54321； 6789=>9876
: 然后把短的那个补足0，9876=》98760
: 然后54321和98760相加，一个个存在string里，最后再reverse result.
: 面试官说不efficient，让我另外想，我又说了个用两个stack分别装string里的数，
: 然后一个个pop出来，pop的时候相加，按顺序存到最后的string里。
: 我两个solution都写了，他还是不满意。请教大家这题还有什么更有效的办法吗？
: 大数相加不是leetcode的题吧？我不记得哪里做过，如果在cc150里，也请大家告诉我
: 一声，我没怎么翻过那本书。
|
e*******s
发帖数: 1979 | 5 好像大家都不爱用iterator嘛
【在 s********u 的大作中提到】
: 没太明白你为什么要reverse+补0。联想Add Binary那道题就可以知道，这题是字符串
: 不是链表，字符串可以从后往前访问，所以完全可以不补0，直接从后往前访问。当某
: 一个字符串用光时，再处理另外一个字符串剩下的（注意进位），最后再看有没有多余
: 的一个进位。
: 毕竟你string是可以一直"push_front"的
: Leetcode原题：
: class Solution {
: public:
: string addBinary(string a, string b) {
: // IMPORTANT: Please reset any member data you declared, as
|
j***e
发帖数: 2428 | 6 string to int
int + int
int to string
【在 u*****o 的大作中提到】
: 请教大家最近碰到的一道题，两个大数，存在string里，return their sum as
: another string.
: 我当时先把两个string reverse，12345--》 54321； 6789=>9876
: 然后把短的那个补足0，9876=》98760
: 然后54321和98760相加，一个个存在string里，最后再reverse result.
: 面试官说不efficient，让我另外想，我又说了个用两个stack分别装string里的数，
: 然后一个个pop出来，pop的时候相加，按顺序存到最后的string里。
: 我两个solution都写了，他还是不满意。请教大家这题还有什么更有效的办法吗？
: 大数相加不是leetcode的题吧？我不记得哪里做过，如果在cc150里，也请大家告诉我
: 一声，我没怎么翻过那本书。
|
h*********o
发帖数: 230 | 7 对啊，倒着跟手算一样加起来就可以了吧。
【在 u*****o 的大作中提到】
: 请教大家最近碰到的一道题，两个大数，存在string里，return their sum as
: another string.
: 我当时先把两个string reverse，12345--》 54321； 6789=>9876
: 然后把短的那个补足0，9876=》98760
: 然后54321和98760相加，一个个存在string里，最后再reverse result.
: 面试官说不efficient，让我另外想，我又说了个用两个stack分别装string里的数，
: 然后一个个pop出来，pop的时候相加，按顺序存到最后的string里。
: 我两个solution都写了，他还是不满意。请教大家这题还有什么更有效的办法吗？
: 大数相加不是leetcode的题吧？我不记得哪里做过，如果在cc150里，也请大家告诉我
: 一声，我没怎么翻过那本书。
|
l*n
发帖数: 529 | 8 是因为你存中间结果的时候用的string吗？显然需要用StringBuilder等buffer结构。
我个人也是喜欢先reverse，因为这样indexing不容易写错。效率上，感觉不差那一点。
【在 u*****o 的大作中提到】
: 请教大家最近碰到的一道题，两个大数，存在string里，return their sum as
: another string.
: 我当时先把两个string reverse，12345--》 54321； 6789=>9876
: 然后把短的那个补足0，9876=》98760
: 然后54321和98760相加，一个个存在string里，最后再reverse result.
: 面试官说不efficient，让我另外想，我又说了个用两个stack分别装string里的数，
: 然后一个个pop出来，pop的时候相加，按顺序存到最后的string里。
: 我两个solution都写了，他还是不满意。请教大家这题还有什么更有效的办法吗？
: 大数相加不是leetcode的题吧？我不记得哪里做过，如果在cc150里，也请大家告诉我
: 一声，我没怎么翻过那本书。
|
b**********i
发帖数: 51 | 9 感觉大家没考虑正负呢，还是说给的数就都是正数呢？ |
u*****o
发帖数: 1224 | 10 你们说的都对呀，直接把pointer放尾端加就行了，我在那reverse的那么欢快，真是有
够2的。add binary的题也做过，不过做了一遍早就忘了，更别提当时能联想起来了。
onsite真是考技术，考心理素质，考基础，我真是太弱了。。。 |
|
|
o*********r
发帖数: 203 | 11 You are joking, right?
How can you add two 200-digit numbers? Max of Java 32bit int has 10 digits.
64bit long has 19 digits.
【在 j***e 的大作中提到】
: string to int
: int + int
: int to string
|
d**********x
发帖数: 4083 | 12 unless he's talking about some complicated math method
1. string to intS
2. intS + intS
3. intS to string
this will be at least 10 times faster than your impl.
【在 u*****o 的大作中提到】
: 请教大家最近碰到的一道题，两个大数，存在string里，return their sum as
: another string.
: 我当时先把两个string reverse，12345--》 54321； 6789=>9876
: 然后把短的那个补足0，9876=》98760
: 然后54321和98760相加，一个个存在string里，最后再reverse result.
: 面试官说不efficient，让我另外想，我又说了个用两个stack分别装string里的数，
: 然后一个个pop出来，pop的时候相加，按顺序存到最后的string里。
: 我两个solution都写了，他还是不满意。请教大家这题还有什么更有效的办法吗？
: 大数相加不是leetcode的题吧？我不记得哪里做过，如果在cc150里，也请大家告诉我
: 一声，我没怎么翻过那本书。
|
d**********x
发帖数: 4083 | 13 maybe he's joking, maybe not.
string to ints instead of chars, is a common skill when we need to hand
write large number operations.
.
【在 o*********r 的大作中提到】
: You are joking, right?
: How can you add two 200-digit numbers? Max of Java 32bit int has 10 digits.
: 64bit long has 19 digits.
|
w**t
发帖数: 893 | 14 reverse changes the input, which is not good from API point of view.
otherwise you need extra copy to hold the reversed string.
【在 l*n 的大作中提到】
: 是因为你存中间结果的时候用的string吗？显然需要用StringBuilder等buffer结构。
: 我个人也是喜欢先reverse，因为这样indexing不容易写错。效率上，感觉不差那一点。
|
l*n
发帖数: 529 | 15 the input has to be changed, as there is always a chance the last carriage
is not zero.
from the point of complexity consideration, reversion doesn't change O(n).
if n can be small, then 2n or 3n doesn't make a difference; if n has to be
large, then 2n or 3n makes no difference either.
【在 w**t 的大作中提到】
: reverse changes the input, which is not good from API point of view.
: otherwise you need extra copy to hold the reversed string.
|
r*****e
发帖数: 792 | 16 这里的ints是java里才有的data type嘛？c++里想不出
转换成整数怎么能work。能具体解释一下怎么转换的嘛？
【在 d**********x 的大作中提到】
: maybe he's joking, maybe not.
: string to ints instead of chars, is a common skill when we need to hand
: write large number operations.
:
: .
|
