w****x
发帖数: 2483 | 1 两个大数相乘
char* multiply(char*,char*);
正常在15分钟写出的解法有吗, 不能转integer再乘啊 |
w****o
发帖数: 2260 | 2 能具体的讲讲这个题是什么东西吗？
是不是说给了两个字符串，每个都是代表了一个很长的10进制表示的数？
比如 char str1[] = "23456789009877666555544444"
char str2[] = "346587436598437594375943875943875"
最后求出他们的乘积？
【在 w****x 的大作中提到】
: 两个大数相乘
: char* multiply(char*,char*);
: 正常在15分钟写出的解法有吗, 不能转integer再乘啊
|
w****x
发帖数: 2483 | 3
对
【在 w****o 的大作中提到】
: 能具体的讲讲这个题是什么东西吗？
: 是不是说给了两个字符串，每个都是代表了一个很长的10进制表示的数？
: 比如 char str1[] = "23456789009877666555544444"
: char str2[] = "346587436598437594375943875943875"
: 最后求出他们的乘积？
|
c****p
发帖数: 6474 | 4 就是实现乘法的竖式实现吧。
把两个操作数按一位、两位、三位或者四位十进制数（取决于int类型的大小）分割，
存储成整弄数组，然后按照做乘法的步骤算一遍。空间复杂度O(m+n)，时间复杂度O(mn
)，mn为两操作数的长度。【 在 wwwyhx (wwwyhx) 的大作中提到: 】 |
z********c
发帖数: 72 | 5 这是Leetcode上Multiplication那道题的程序，过了数据
string multiply(string num1, string num2) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector res(num1.size () + num2.size (), 0);
for (int i = 0; i < num1.size (); i++) {
int carry = 0;
for (int j = 0; j < num2.size (); j++) {
int d1 = num1[num1.size () - 1 - i] - '0';
int d2 = num2[num2.size () - 1 - j] - '0';
carry = d1 * d2 + res[i + j] + carry;
res[i + j] = carry % 10;
carry = carry / 10;
}
res[i + num2.size ()] = carry;
}
int i = num1.size () + num2.size () - 1;
while (i > 0 && res[i] == 0) i--;
string result;
while (i >= 0) result += char (res[i --] + '0');
return result;
}
【在 w****x 的大作中提到】
: 两个大数相乘
: char* multiply(char*,char*);
: 正常在15分钟写出的解法有吗, 不能转integer再乘啊
|
t*********7
发帖数: 255 | 6 就是数组实现乘法竖式吧... 但是要考虑数组空间的上限越界么?.. |
m********1
发帖数: 31 | 7 请问你code里的
int d1 = num1[num1.size () - 1 - i] - '0';
int d2 = num2[num2.size () - 1 - j] - '0';
那个减去 '0' 是干什么用的呢？
【在 z********c 的大作中提到】
: 这是Leetcode上Multiplication那道题的程序，过了数据
: string multiply(string num1, string num2) {
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
: vector res(num1.size () + num2.size (), 0);
: for (int i = 0; i < num1.size (); i++) {
: int carry = 0;
: for (int j = 0; j < num2.size (); j++) {
: int d1 = num1[num1.size () - 1 - i] - '0';
: int d2 = num2[num2.size () - 1 - j] - '0';
|
e***l
发帖数: 710 | 8 字符数字转换为整数数字，'0'代表0的ascii码 |
m********1
发帖数: 31 | 9 嗯，谢谢啦
【在 e***l 的大作中提到】
: 字符数字转换为整数数字，'0'代表0的ascii码
|
n**e
发帖数: 116 | |
|
|
l***i
发帖数: 1309 | 11 面世问这个比较变态把，没有任何技术含量，就是别错。string倒过来放，负号先拿掉
，返回pointer先malloc/new。还有什么注意事项么。
uva上有一道题要算满足一定条件的加()种数，recursion很快就写出来了，然后就要用
这个arbitrary precision integer arithmetic。写了个char*的结果TLE无数次。最后
有个大牛hint用vector，然后每个int可以一次算9位数字，结果轻松过。
去年还是前年的google codejam qual有一道题是用这个的，neal_wu的code可以用来学
习。 |
w****x
发帖数: 2483 | 12
靠, 太扯了, 15分钟电面谁TMD 15分钟想的出这个解法, 而且只会c语言的根本很难做, 电面出
这个题的人脑袋没问题吧!!!
没想出这个解法的就是我下面的这种烂code:
string Multiple(string str1, string str2)
{
assert(str1.size() > 0 && str2.size() > 0);
string strRes;
for (int i = str2.size() - 1; i >= 0; i--)
{
int nAdd = 0;
string strCur;
for (int j = str1.size() - 1; j >= 0; j--)
{
int nTmpI = str2[i] - '0';
int nTmpJ = str1[j] - '0';
int nRes = nTmpJ * nTmpI + nAdd;
nAdd = nRes / 10;
strCur.insert(strCur.begin(), nRes%10 + '0');
}
if (nAdd > 0) //missing
strCur.insert(strCur.end(), nAdd + '0');
if (strRes.empty())
{
strRes = strCur;
continue;
}
strCur.insert(strCur.end(), '0');
nAdd = 0;
int nRes = strRes.size() - 1;
int nCur = strCur.size() - 1;
string strTmpRes;
while (nCur >= 0 && nRes >= 0)
{
int nTmpCur = strCur[nCur] - '0';
int nTmpRes = strRes[nRes] - '0';
int nDigit = nTmpCur + nTmpRes + nAdd;
nAdd = nDigit / 10;
strTmpRes.insert(strTmpRes.begin(), nDigit%10 + '0');
nRes--, nCur--;
}
if (nRes >= 0)
{
while (nRes >= 0)
{
int nTmpRes = strRes[nRes] - '0';
int nDigit = nTmpRes + nAdd;
nAdd = nDigit / 10;
strTmpRes.insert(strTmpRes.begin(), nDigit%10 + '0');
nRes--;
}
if (nAdd > 0) strTmpRes.insert(strTmpRes.begin(),
'1');//missing
}
if (nCur >= 0)
{
while (nCur >= 0)
{
int nTmpRes = strCur[nCur] - '0';
int nDigit = nTmpRes + nAdd;
nAdd = nDigit / 10;
strTmpRes.insert(strTmpRes.begin(), nDigit%10 + '0');
nCur--;
}
if (nAdd > 0) strTmpRes.insert(strTmpRes.begin(),
'1');//missing
}
strRes = strTmpRes;
}
return strRes;
}
【在 z********c 的大作中提到】
: 这是Leetcode上Multiplication那道题的程序，过了数据
: string multiply(string num1, string num2) {
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
: vector res(num1.size () + num2.size (), 0);
: for (int i = 0; i < num1.size (); i++) {
: int carry = 0;
: for (int j = 0; j < num2.size (); j++) {
: int d1 = num1[num1.size () - 1 - i] - '0';
: int d2 = num2[num2.size () - 1 - j] - '0';
|
m***n
发帖数: 2154 | 13 呵呵，这个其实比较容易。先写一个字符串相加的方法，
然后用小学学过的办法，一位一位来。。
不过15分钟有点夸张。 |
a***g
发帖数: 234 | 14 这题很难写完一次通过编译
15分钟有点扯。。。 |
c****p
发帖数: 6474 | 15 这个用C写也不难吧。
做, 电面出
【在 w****x 的大作中提到】
:
: 靠, 太扯了, 15分钟电面谁TMD 15分钟想的出这个解法, 而且只会c语言的根本很难做, 电面出
: 这个题的人脑袋没问题吧!!!
: 没想出这个解法的就是我下面的这种烂code:
: string Multiple(string str1, string str2)
: {
: assert(str1.size() > 0 && str2.size() > 0);
: string strRes;
: for (int i = str2.size() - 1; i >= 0; i--)
: {
|
p*****2
发帖数: 21240 | 16
C麻烦就在分配内存的时候不知道分多少。如果用char[], 进位的时候就不够空间了。
【在 c****p 的大作中提到】
: 这个用C写也不难吧。
:
: 做, 电面出
|
c****p
发帖数: 6474 | 17 这样空间和时间效率都不好。
考虑到现在int一般是32位（4e9），
每个int元素可以存多位十进制数。
这样的话，单次int乘法的复杂度没有变化，
但是总的乘法次数下降了，使用空间也相应下降了。【 在 zhangchitc (zhangchitc)
的大作中提到: 】 |
c****p
发帖数: 6474 | 18 m*n位，结果长度不会超过m+n-1位啊。
【在 p*****2 的大作中提到】
:
: C麻烦就在分配内存的时候不知道分多少。如果用char[], 进位的时候就不够空间了。
|
w****x
发帖数: 2483 | 19
)
15分钟....
【在 c****p 的大作中提到】
: 这样空间和时间效率都不好。
: 考虑到现在int一般是32位（4e9），
: 每个int元素可以存多位十进制数。
: 这样的话，单次int乘法的复杂度没有变化，
: 但是总的乘法次数下降了，使用空间也相应下降了。【 在 zhangchitc (zhangchitc)
: 的大作中提到: 】
|
p*****2
发帖数: 21240 | 20
应该不会超过m+n吧？比如9*9＝81, 占两位。
是这样子的。不过写的时候要考虑很多小细节，真的不容易bug free。至少跟java比要
麻烦不少。
【在 c****p 的大作中提到】
: m*n位，结果长度不会超过m+n-1位啊。
|
|
|
c****p
发帖数: 6474 | 21 这题是POJ 1001的一个子算法。
【在 w****x 的大作中提到】
:
: )
: 15分钟....
|
c****p
发帖数: 6474 | 22 而且这题基本没有什么tricky的地方吧。。
时间紧的话可以先说你知道有哪些corner case，但是时间比较紧，这里假设两个字符串
符合XX的通用格式。
然后开始照着思路写。。。【 在 wwwyhx (wwwyhx) 的大作中提到: 】 |
p*****2
发帖数: 21240 | 23
练过当然要好多了。如果做过几遍是可以15分钟完成。但是如果没做过的话，难度还是
蛮高吧？
【在 c****p 的大作中提到】
: 这题是POJ 1001的一个子算法。
|
c****p
发帖数: 6474 | 24 写bug free的可能是用点难。
不过核心代码并不长。
【在 p*****2 的大作中提到】
:
: 练过当然要好多了。如果做过几遍是可以15分钟完成。但是如果没做过的话，难度还是
: 蛮高吧？
|
p*****2
发帖数: 21240 | 25
这个有时间还得练练。
【在 c****p 的大作中提到】
: 写bug free的可能是用点难。
: 不过核心代码并不长。
|
w****x
发帖数: 2483 | 26
说实话, 我不大信没做过几遍原题能15分钟写完, 大家也不是搞ACM竞赛的
【在 c****p 的大作中提到】
: 写bug free的可能是用点难。
: 不过核心代码并不长。
|
s**u
发帖数: 2294 | |
s*******f
发帖数: 1114 | 28 //码遍本版
//i cannot get this should-be-right version within 15 minutes
//use reversed storage. say 1345 store as "5431"
char* MultiplyString(char *a,char *b){
if (!a || !b)
return NULL;
int la = strlen(a);
int lb = strlen(b);
int lc = la + lb + 1;
char *ret = new char[lc];
char *r = ret;
memset(ret, '\0', lc);
while (*a){
char *p = b;
char *q = r++;
int inc = 0;
int mul = *a - '0';
while (*p){
int qq = *q?(*q - '0'):0;
int m0 = mul * (*p - '0') + qq + inc;
*q++ = (char)(m0 % 10 + '0');
inc = m0 / 10;
++p;
}
while (inc != 0){
int qq = *q?(*q - '0'):0;
int m1 = qq + inc;
*q++ = (char)(m1 % 10 + '0');
inc = m1 / 10;
}
++a;
}
//test
printf("%s\n", ret);
return ret;
}
void TestMultiplyString(){
char *a = MultiplyString("12", "10");
char *b = MultiplyString("12", "0");
char *c = MultiplyString("2", "10");
char *d = MultiplyString("1216494413148", "17673735345330");
char *e = MultiplyString("2803", "456");
}
【在 w****x 的大作中提到】
: 两个大数相乘
: char* multiply(char*,char*);
: 正常在15分钟写出的解法有吗, 不能转integer再乘啊
|
h****e
发帖数: 928 | 29 这道题目如果真是FB的高频题，那就硬背一个最简洁的解法吧。 |
r*****e
发帖数: 792 | 30 背哪个呢？
弄个大数加法考考字符串操作也就罢了，乘法真没什么意思。
【在 h****e 的大作中提到】
: 这道题目如果真是FB的高频题，那就硬背一个最简洁的解法吧。
|
