a********3
发帖数: 228 | 1 除了之前问我project的一些东西，code我就做了一题，是不是有点悲剧？
code是x^y，x和y都是正整数。
我开始以为是大家都练过的pow，然后说了一下思路，准备写。
面试官说先写最简单的，我就快速写了个O(n)的。
然后他问这个work吗？我想了下，说有可能overflow，就把result从int改为long。
他又问这个work吗？我想了下，long还有可能overflow，就说可以用多个long来表示结
果。
他遂提示用BigInteger，然后让我实现BigInteger类。
我的脑子这时有点卡壳，过了一阵才明白需要实现BigInteger的相乘。
中间还有点误解他的意思，经过提示才写出来。
最近rp不灵，面试时总是碰见没见过的题，不过也是因为自己实力不强，碰见不熟悉的
题就容易露怯。 |
l*****a
发帖数: 559 | 2 就一题BigInteger相乘不算悲剧。
一开始面试官用^表示有误导之嫌。 |
j******2
发帖数: 362 | 3 你用的什么语言？biginteger要自己写？
【在 a********3 的大作中提到】
: 除了之前问我project的一些东西，code我就做了一题，是不是有点悲剧？
: code是x^y，x和y都是正整数。
: 我开始以为是大家都练过的pow，然后说了一下思路，准备写。
: 面试官说先写最简单的，我就快速写了个O(n)的。
: 然后他问这个work吗？我想了下，说有可能overflow，就把result从int改为long。
: 他又问这个work吗？我想了下，long还有可能overflow，就说可以用多个long来表示结
: 果。
: 他遂提示用BigInteger，然后让我实现BigInteger类。
: 我的脑子这时有点卡壳，过了一阵才明白需要实现BigInteger的相乘。
: 中间还有点误解他的意思，经过提示才写出来。
|
w****a
发帖数: 710 | 4 怎么G店面都喜欢考big int? 我今天的也考了，不过我是加法。 |
j******2
发帖数: 362 | 5 我记得幂函数只要平方就行了，大数平方能不能比大数乘法简单点？还是还是必须写个
general的乘法啊？ |
w****a
发帖数: 710 | 6 那相当于这道题就是大数乘法和pow的结合题咯，那你一次店面做了两题还描述了
project，不算悲剧，BLESS |
h*********o
发帖数: 230 | 7 这个是求x的y次幂吗？
biginteger 从来没用过啊。。。
你是用什么语言啊？
java也有这个吗？
【在 a********3 的大作中提到】
: 除了之前问我project的一些东西，code我就做了一题，是不是有点悲剧？
: code是x^y，x和y都是正整数。
: 我开始以为是大家都练过的pow，然后说了一下思路，准备写。
: 面试官说先写最简单的，我就快速写了个O(n)的。
: 然后他问这个work吗？我想了下，说有可能overflow，就把result从int改为long。
: 他又问这个work吗？我想了下，long还有可能overflow，就说可以用多个long来表示结
: 果。
: 他遂提示用BigInteger，然后让我实现BigInteger类。
: 我的脑子这时有点卡壳，过了一阵才明白需要实现BigInteger的相乘。
: 中间还有点误解他的意思，经过提示才写出来。
|
f*****e
发帖数: 2992 | 8 每个int存范围在10^8的10进制数，相乘超过这个范围的补到下一个int。
【在 h*********o 的大作中提到】
: 这个是求x的y次幂吗？
: biginteger 从来没用过啊。。。
: 你是用什么语言啊？
: java也有这个吗？
|
a********3
发帖数: 228 | 9 我用的java，要求自己实现BigInteger，虽然我记得java也有个类叫BigInteger |
a********3
发帖数: 228 | 10 不是实现整个BigInteger，他说只用实现能完成pow函数的function就行，我写了
constructor和multiply function。 |
|
|
t*********h
发帖数: 941 | 11 是string吗？还是数组
【在 a********3 的大作中提到】
: 除了之前问我project的一些东西，code我就做了一题，是不是有点悲剧？
: code是x^y，x和y都是正整数。
: 我开始以为是大家都练过的pow，然后说了一下思路，准备写。
: 面试官说先写最简单的，我就快速写了个O(n)的。
: 然后他问这个work吗？我想了下，说有可能overflow，就把result从int改为long。
: 他又问这个work吗？我想了下，long还有可能overflow，就说可以用多个long来表示结
: 果。
: 他遂提示用BigInteger，然后让我实现BigInteger类。
: 我的脑子这时有点卡壳，过了一阵才明白需要实现BigInteger的相乘。
: 中间还有点误解他的意思，经过提示才写出来。
|
j*****y
发帖数: 1071 | 12 这题目还要考 big integer的相乘, 其实感觉挺难的
vector power(vector &a, vector & b)
{
int m = a.size() - 1;
int n = b.size() - 1;
vector result(m + n + 1, 0);
for(int i = 0; i < result.size(); ++i)
{
int power = m + n - i;
for(int k = 0; k <= power; ++k)
{
if(power - k > n)
{
continue;
}
if(k > m)
{
break;
}
result[i] += a[m - k] * b[n -(power - k)];
}
}
int remainder = 0;
for(int i = result.size() - 1; i > -1 ; --i)
{
int x = a[i] + remainder;
a[i] = x % 10;
remainder = x / 10;
}
while(remainder > 0)
{
result.insert(result.begin(), remainder % 10);
remainder = remainder / 10;
}
return result;
}
vector power(vector x, int y)
{
if(y == 1)
{
return x;
}
if(y & 0x1 == 0)
{
vector tmp = power(x, y >> 2);
return power(tmp, tmp);
}
else
{
return power(x, power(x, y - 1));
}
}
vector power(int x, int y)
{
vector vx;
while(x > 0)
{
vx.insert(vx.begin(), x % 10);
x = x / 10;
}
return power(vx, y);
}
【在 a********3 的大作中提到】
: 除了之前问我project的一些东西，code我就做了一题，是不是有点悲剧？
: code是x^y，x和y都是正整数。
: 我开始以为是大家都练过的pow，然后说了一下思路，准备写。
: 面试官说先写最简单的，我就快速写了个O(n)的。
: 然后他问这个work吗？我想了下，说有可能overflow，就把result从int改为long。
: 他又问这个work吗？我想了下，long还有可能overflow，就说可以用多个long来表示结
: 果。
: 他遂提示用BigInteger，然后让我实现BigInteger类。
: 我的脑子这时有点卡壳，过了一阵才明白需要实现BigInteger的相乘。
: 中间还有点误解他的意思，经过提示才写出来。
|
j******2
发帖数: 362 | 13 大数乘法在leetcode里是被我归为大题类得。。。
【在 j*****y 的大作中提到】
: 这题目还要考 big integer的相乘, 其实感觉挺难的
: vector power(vector &a, vector & b)
: {
: int m = a.size() - 1;
: int n = b.size() - 1;
: vector result(m + n + 1, 0);
: for(int i = 0; i < result.size(); ++i)
: {
: int power = m + n - i;
: for(int k = 0; k <= power; ++k)
|
l*****a
发帖数: 14598 | 14 用字符串也可以吧？
【在 a********3 的大作中提到】
: 不是实现整个BigInteger，他说只用实现能完成pow函数的function就行，我写了
: constructor和multiply function。
|
B********t
发帖数: 147 | 15 power(vector, int)里return的两个power都应该是mult吧。。。
【在 j*****y 的大作中提到】
: 这题目还要考 big integer的相乘, 其实感觉挺难的
: vector power(vector &a, vector & b)
: {
: int m = a.size() - 1;
: int n = b.size() - 1;
: vector result(m + n + 1, 0);
: for(int i = 0; i < result.size(); ++i)
: {
: int power = m + n - i;
: for(int k = 0; k <= power; ++k)
|
j*****y
发帖数: 1071 | 16 是的，多谢，改过来了 :)
【在 B********t 的大作中提到】
: power(vector, int)里return的两个power都应该是mult吧。。。
|
a********3
发帖数: 228 | 17 我没写这么完整，之前也没做过大数相乘的题目。。。
刚看到leetcode上有string版本的大数相乘。。。
【在 j*****y 的大作中提到】
: 这题目还要考 big integer的相乘, 其实感觉挺难的
: vector power(vector &a, vector & b)
: {
: int m = a.size() - 1;
: int n = b.size() - 1;
: vector result(m + n + 1, 0);
: for(int i = 0; i < result.size(); ++i)
: {
: int power = m + n - i;
: for(int k = 0; k <= power; ++k)
|
g*********n
发帖数: 43 | 18 如果从低位开始存取的话，下面这段代码好像可以简单一点?
for(int i = 0; i < result.size(); ++i)
{
int power = m + n - i;
for(int k = 0; k <= power; ++k)
{
if(power - k > n)
{
continue;
}
if(k > m)
{
break;
}
result[i] += a[m - k] * b[n -(power - k)];
}
}
==〉
for (i=0; i< result.size(); i++)
{
result[i] = 0;
for (j=0; j< a.size(); j+=)
{
if (i-j >= 0)
{
result [i] += a[j] *b[i-j];
}
else break;
}
}
【在 j*****y 的大作中提到】
: 这题目还要考 big integer的相乘, 其实感觉挺难的
: vector power(vector &a, vector & b)
: {
: int m = a.size() - 1;
: int n = b.size() - 1;
: vector result(m + n + 1, 0);
: for(int i = 0; i < result.size(); ++i)
: {
: int power = m + n - i;
: for(int k = 0; k <= power; ++k)
|
j*****y
发帖数: 1071 | 19 thanks，你的 idea 也可以简化我的 code
for(int i = 0; i < result.size(); ++i)
{
int power = m + n - i;
for(int k = max(0, power - n); k <= min(m, power); ++k)
{
result[i] += a[m - k] * b[n -(power - k)];
}
}
如果从低位开始存取的话，下面这段代码好像可以简单一点?
for(int i = 0; i < result.size(); ++i)
{
int power = m + n - i;
for(int k = 0; k <= power; ++k)
{
if(power - k > n)
{
continue;
}
if(k > m)
{
break;
}
result[i] += a[m - k] * b[n -(power - k)];
}
}
==〉
for (i=0; i< result.size(); i++)
{
result[i] = 0;
for (j=0; j< a.size(); j+=)
{
if (i-j >= 0)
{
result [i] += a[j] *b[i-j];
}
else break;
}
}
【在 g*********n 的大作中提到】
: 如果从低位开始存取的话，下面这段代码好像可以简单一点?
: for(int i = 0; i < result.size(); ++i)
: {
: int power = m + n - i;
: for(int k = 0; k <= power; ++k)
: {
:
: if(power - k > n)
: {
: continue;
|
