題目：
給定兩個(gè)字符串十進(jìn)制數(shù)字寒砖，給出字符串為他們的乘積佛嬉。要求如下：
- 禁止使用內(nèi)置大數(shù)算法。
- 字符串長度110
- 輸入無前置0
- 字符串僅含有數(shù)字
思考
在一開始沒有看到禁止使用內(nèi)置函數(shù)，我直接使用python的str和int這兩個(gè)函數(shù)，結(jié)果直接前10%了秽褒。。威兜。后來我看了下題目原來是不能用內(nèi)置函數(shù)的销斟，不知道這個(gè)python語言的特性算不算內(nèi)置大數(shù)算法。這是一個(gè)大數(shù)乘法問題椒舵，大數(shù)乘法有很多現(xiàn)成的算法蚂踊。
最開始提交的python版本，擊敗88%
class Solution(object):
def multiply(self, num1, num2):
return str(int(num1)*int(num2))
最原始的算法就是模擬手算了吧笔宿，首先你得實(shí)現(xiàn)字符串的加法計(jì)算悴势，多位乘法乘一位乘法，這樣應(yīng)該可以計(jì)算多位乘以多位了措伐。例如計(jì)算12345*67890，就是計(jì)算12345*6 + 12345*7 + 12345 *8 + 12345 * 9 + 12345 * 0军俊， 然后每一個(gè)計(jì)算結(jié)果后面補(bǔ)0侥加，再相加就會(huì)得到結(jié)果。不過這樣的速度會(huì)比較慢粪躬。
況且担败，CPU本身就可以計(jì)算一些不會(huì)溢出的加法，所以镰官，我們得好好利用這一點(diǎn)提前。首先我們得改進(jìn)一下上面的算法，計(jì)算12345*67890這個(gè)數(shù)字的結(jié)果泳唠，我們可以這樣算：12345*67890 = (12300 + 45)*(67800 + 90) 狈网，顯然可以拆解成為4個(gè)乘法計(jì)算，而且對于低位為0的，可以直接去掉拓哺，然后計(jì)算結(jié)果再補(bǔ)回來就行了勇垛，如果這四個(gè)乘法分別計(jì)算的時(shí)候不會(huì)溢出，那就沒有問題了士鸥。否則闲孤，我們可以繼續(xù)分解。
使用karatsuba乘法可以繼續(xù)改進(jìn)上面一點(diǎn)烤礁。
我們注意到加法中有12300*90+45*67800讼积，我們可以利用已經(jīng)計(jì)算過的結(jié)果，也就是12300*67800和45*90脚仔，然后只需要計(jì)算(12300+45)*(67800+90) - 12300*67800 - 45*90 就可以得到 12300*90 + 45*67800勤众。這樣，乘法的計(jì)算次數(shù)就減少了一次玻侥。
karatsuba乘法寫起來會(huì)復(fù)雜一點(diǎn)决摧，先不實(shí)現(xiàn)。首先提交一版n^2的算法也就是普通版凑兰，看看效果怎么樣掌桩，然后再改進(jìn)。（結(jié)果表明姑食，手算版的速度已經(jīng)很快了）
第一版
首先我們得寫一個(gè)字符串相加的算法波岛。我們首先觀察一下輸入的數(shù)據(jù)類型和輸出的數(shù)據(jù)類型。是string類型的音半，那么按照一位一位加起來也是可以的则拷。可以直接用兩個(gè)整形數(shù)組保存一下每一位數(shù)曹鸠，然后相加算出來第三個(gè)數(shù)組煌茬，這時(shí)第三個(gè)數(shù)組會(huì)有一些數(shù)字超出了10，我們按照從低位開始向高位進(jìn)一位彻桃。最后將這個(gè)數(shù)組轉(zhuǎn)成字符串就可以了坛善。
雖然本地測試還可以，但是提交后速度很慢邻眷，排名很后眠屎，只擊敗10%。
改進(jìn)
我覺得理論上這個(gè)算法應(yīng)該是不慢的,但是實(shí)際過程是很慢肆饶，可能是由于多余的整形和字符串互相轉(zhuǎn)換有關(guān)改衩。上面的算法里面，在計(jì)算乘法的時(shí)候?qū)⒆址D(zhuǎn)成了數(shù)字但是之后又轉(zhuǎn)換回字符串驯镊，可能是這里產(chǎn)生了多余的時(shí)間葫督。所以竭鞍，應(yīng)該直接在這里將結(jié)果加在最終結(jié)果上面。
提交后運(yùn)行時(shí)間為9ms候衍，擊敗50%笼蛛。
改進(jìn)2
算法中相同的字符串重復(fù)轉(zhuǎn)化，可能會(huì)消耗時(shí)間蛉鹿。
對字符串轉(zhuǎn)化進(jìn)行緩存滨砍，第一次轉(zhuǎn)換成功就進(jìn)行緩存，以后如果需要直接取出不需要進(jìn)行額外的計(jì)算妖异。
最終代碼惋戏，可直接編譯運(yùn)行。運(yùn)行時(shí)間6ms他膳，擊敗76%提交响逢。看來字符串轉(zhuǎn)化反而成了性能瓶頸棕孙。
#include <stdio.h>
#include <string>
#include <stdlib.h>
#include <iostream>
#include <vector>
using namespace std;
const int BINARY = 10;
class Solution
{
private:
vector<int> result;
string _num1, _num2;
long num1buff[120];
long num2buff[120];
public:
string multiply(string num1, string num2)
{
result.clear();
result.resize(num1.length() + num2.length() + 1);
memset(num1buff, -1 , sizeof(long)*120);
memset(num2buff, -1 , sizeof(long)*120);
_num1 = num1;
_num2 = num2;
for(auto &c : _num1){
c-='0';
}
for(auto &c : _num2){
c-='0';
}
//這個(gè)過程是遞歸的過程,我們先看下什么時(shí)候終止吧.
//終止的時(shí)候,是兩個(gè)數(shù)相乘不會(huì)溢出的時(shí)候
//我們假設(shè)int是二進(jìn)制30位的,相乘要30位,原來兩個(gè)數(shù)字必然是15位的, 也就是32768.
//也就是說兩個(gè)四位數(shù)相乘通常都不會(huì)溢出了吧.
//使用遞歸來計(jì)算乘積
addMultiply(0,num1.length(), 0, num2.length());
string ret;
int i = result.size() -1;
for(; i>0; i--)
{
if(result[i] != 0) break;
}
for(; i>=0; i--)
{
ret.push_back(result[i] + '0');
}
return ret;
}
void addMultiply(int a1, int a2, int b1, int b2 )
{;
//判斷是否可以直接計(jì)算
if (a1 == a2 || b1 == b2)
return;
if (a2 - a1 < 10 && b2 - b1 < 10)
{
long int_num1 = getLong1(a1, a2);
long int_num2 = getLong2(b1, b2);
long output = int_num1 * int_num2;
int pos = _num1.length() + _num2.length() - a2 - b2;
while (output != 0 || result[pos] >= BINARY)
{
long a = output % BINARY;
result[pos] += a;
result[pos + 1] += result[pos] / BINARY;
result[pos] %= BINARY;
output /= BINARY;
pos++;
}
return;
}
//否則,拆開較長的那個(gè)數(shù)字
if(a2 - a1 >= 10){
addMultiply(a1, (a2 + a1)/2, b1, b2);
addMultiply((a2 + a1)/2, a2, b1, b2);
}
else {
addMultiply(a1, a2, (b1+b2)/2, b2);
addMultiply(a1, a2, b1, (b1+b2)/2);
}
}
long getLong1(int a, int b){
long ret = 0;
if(num1buff[a] != -1) return num1buff[a];
for(int i=a; i!=b;i++){
ret *= BINARY;
ret += _num1[i] ;
}
num1buff[a] = ret;
return ret;
}
long getLong2(int a, int b){
long ret = 0;
if(num2buff[a] != -1) return num2buff[a];
for(int i=a; i!=b;i++){
ret *= BINARY;
ret += _num2[i] ;
}
num2buff[a] = ret;
return ret;
}
};
int main(void)
{
Solution s;
for(int i=0;i<10000;i++){
cout << s.multiply("12345678901", "100") << endl;
cout << s.multiply("100", "100") << endl;
}
return 0;
}
最終排名擊敗70%
