程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> [C++]LeetCode: 69 Multiply Strings

[C++]LeetCode: 69 Multiply Strings

編輯:關於C++
題目:

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative.

Answer 1: 基礎法

大整數乘法

\

根據小學手算乘法的規則,我們把每一位相乘,得到一個沒有進位的臨時結果,如圖中間的一行紅色數字就是臨時結果,然後把臨時結果從低位起一次進位。對於一個m位整數乘以一個n位整數的結果,存儲空間,最多m+n位(加上一位進位)。

Attention:

1. 如果結果中最高位為0,需要去掉前導0.

 int i = k+1;
 while(tmpres[i] == 0)i--;//去掉乘積的前導0
2. 如果結果為0,需要處理。

 if(i < 0)return "0"; //注意乘積為0的特殊情況

3. string對象的下標從0開始,最後一個字符的下標為size() - 1,下標超出范圍會引起溢出錯誤;

即”254“ => s[0] = '2', s[1] = '5' , s[2] = '4'

4. 注意存儲空間的確定,位數等。

由於用tmp[k-i-j]存儲每一個臨時求和結果,max(i) = len1-1; max(j) = len2-1; k取 len1+ len2 -2即可,k是下標,下標從零開始。

實際tmp存儲空間應該是(k+1) + 1, 其中k+1代表臨時結果的數量,1代表乘法可能產生最高位的一位進位。所以

對於一個m位整數乘以一個n位整數的結果,存儲空間,最多m+n位。注意這個最高位對應下標為k+1.

復雜度:O(N^2)

AC Code:

class Solution {
public:
    string multiply(string num1, string num2) {
        int len1 = num1.size();
        int len2 = num2.size();
        vector tmp(len1 + len2, 0);
        int k = len1 + len2 - 2; //最低位即 (len1-1) * (len2-1),存儲到tmp[0]
        
        for(int i = 0; i < len1; i++)
        {
            for(int j = 0; j < len2; j++)
            {
                tmp[k-i-j] += (num1[i]-'0') * (num2[j]-'0');
            }
        }
        
        //處理進位
        int carryBit = 0;
        for(int i = 0; i < len1 + len2; i++)
        {
            tmp[i] += carryBit;
            carryBit = tmp[i]/10;
            tmp[i] %= 10;
        }
        
        int i = k + 1;
        while(tmp[i] == 0) i--;  //去除乘積前導0
        if(i < 0) return "0";    //處理特殊情況乘積為0
        
        string ret;
        for(;i >= 0; i--)
        {
            ret.push_back(tmp[i] + '0');
        }
        
        return ret;
    }
};

Answer 2: FFT方法(待仔細研究)

這道題其實還有更加優的做法,就是用十大最牛的算法之一--Fast Fourier transform(FFT)。使用FFT可以在O(nlogn)時間內求出多項式的乘法,在這裡只需要把變量x帶入10,然後按照求多項式的方法就可以求出兩個大整數的成績了。不過FFT實現不是很簡單,所以在面試中一般不需要寫代碼,只需要知道這個思路和基本工作原理就可以了哈。

查閱資料,有篇博文寫的比較詳細:使用快速傅裡葉變換計算大整數乘法

向量 {ck} 是向量 {ai} 和向量 {bj} 的卷積。根據卷積定理,向量卷積的離散傅裡葉變換是向量離散傅裡葉變換的乘積。於是,我們可以按照以下步驟來計算大整數乘法:

  1. 分別求出向量 {ai} 和向量 {bj} 的離散傅裡葉變換 {Ai} 和 {Bj}。
  2. 將 {Ai} 和 {Bj} 逐項相乘得到向量 {Ck}。
  3. 對 {Ck} 求離散傅裡葉逆變換,得到的向量 {ck} 就是向量 {ai} 和向量 {bj} 的卷積。
  4. 對的向量 {ck} 進行適當的進位就得到了大整數 a 和 b 的乘積 c。
我們根據以上思路去計算,直接進行離散傅裡葉變換的計算復雜度是 O(N2)。快速傅裡葉變換可以計算出與直接計算相同的結果,但只需要 O(N logN) 的計算復雜度。

快速傅裡葉變換的要點如下:一個界長為 N 的離散傅裡葉變換可以重新寫成兩個界長各為 N/2 的離散傅裡葉變換之和。其中一個變換由原來 N 個點中的偶數點構成,另一個變換由奇數點構成。這個過程可以遞歸地進行下去,直到我們將全部數據細分為界長為 1 的變換。什麼是界長為 1 的傅裡葉變換呢?它正是把一個輸入值復制成它的一個輸出值的恆等運算。要實現以上算法,最容易的情況是原始的 N 為 2 的整冪次項,如果數據集的界長不是 2 的冪次時,則可添上一些零值,直到 2 的下一冪次。在這個算法中,每遞歸一次需 N 階運算,共需要 log N 次遞歸,所以快速傅裡葉變換算法的時間復雜度是 O(N logN)。




  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved