??個人主頁:?? :???初階牛???
>??推薦專欄1: ??????C語言初階
??推薦專欄2: ??????C語言進階
??個人信條: ??知行合一
金句分享:
?你要狠下心來去努力,努力變成一個很厲害的人.?

前言

本題牛牛寫了很久,起初對每次相乘的結(jié)果就進位處理了,最后還需要考慮錯位相加,進行補0等,花了半天也沒搞出來.
所幸學到了一種高效且相對簡單的方法解決此題,希望對友友們有所幫助.

一、字符串相乘

題目介紹

給定兩個以字符串形式表示的非負整數(shù) num1 和 num2，返回 num1 和 num2 的乘積，它們的乘積也表示為字符串形式。

注意：不能使用任何內(nèi)置的 BigInteger 庫或直接將輸入轉(zhuǎn)換為整數(shù)。

示例1:

輸入: num1 = “2”, num2 = “3”
輸出: “6”

示例2:

輸入: num1 = “123”, num2 = “456”
輸出: “56088”

思路分析

1. 同時從兩個字符串的右邊開始往前遍歷相乘.

2. 用num2中的每一個字符依次與與num1中的每個字符想乘.

3. 將相乘的結(jié)果保存在一個arr數(shù)組中,每個相乘的結(jié)果放入正確的位置(i+J+1).
   

4. arr數(shù)組創(chuàng)建多大的空間?
   一個最小的二位數(shù) × 一個最小的三位數(shù) 結(jié)果是一個四位數(shù)
   10100=1000
   一個最大的二位數(shù) × 一個最大的三位數(shù) 結(jié)果是一個五位數(shù)
   99999=98901
   綜上呢,兩個數(shù)相乘,他們的結(jié)果的位數(shù)是[length1 + length2,length1 + length2+1],(0除外哈)
   最高位可能有數(shù)據(jù),也可能沒有數(shù)據(jù).

5. 為什么正確的位置是i+j+1?
   試著看上圖分析:注意i和j都是從右邊往左邊遍歷.
   此處是此解法的難點,通過將每次相乘后的結(jié)果放入正確的位置以實現(xiàn)錯位相加.
   牛牛的理解是:
   j是內(nèi)循環(huán),從右往左遍歷num1,i是外循環(huán),決定的是num2.
   所以用j的變化控制與num1相乘結(jié)果的位置,用i的變化,控制錯位相加(即相乘的結(jié)果要往左移動一位)即num2的位變化.

6. 對錯位相加后的數(shù)組進行進位處理:從右往左進位
   (1)先保存元素的值,tmp = arr[i]+carry;
   (2)替換為進位后的數(shù)據(jù): arr[i] = (arr[i] + carry) % 10;
   (3)保存進位數(shù): carry = tmp / 10;

7. 將進位后的數(shù)組中的數(shù)據(jù)依次尾插入amass對象中.
   注意:先判斷第一個位置有沒有有效數(shù)據(jù)(即最高位是否有效)

8. 最后,處理特殊情況,如果num1和num2中有一個是0,則直接返回0.

代碼實現(xiàn):

class Solution {
public:
    string multiply(string num1, string num2) {
    //處理特殊情況,如果有一方為0,
        if (num1[0] == '0' || num2[0] == '0') return string("0");
        int length1 = num1.size();
        int length2 = num2.size();
        int arr[length1 + length2];
        //將數(shù)組中的元素全部初始化為0
        for (auto& a : arr)
        {
            a = 0;
        }
        string amass;
        //相乘
        //內(nèi)外層循環(huán)控制num2和num1 的次序無所謂
        //版本1
        for (int i = length2 -1; i >= 0; i--){//外層循環(huán)控制num2
            int s1 = num2[i] - '0';
            for (int j = length1 - 1; j >= 0; j--){//內(nèi)存循環(huán)控制num1
                int s2 = num1[j] - '0';
                arr[i+j+1] += s1 * s2;//注意這里是+=
            }
        }
        //版本2
       /*
        for (int i = length1 - 1; i >= 0; i--)
        {
            int s1 = num1[i] - '0';
            for (int j = length2 - 1; j >= 0; j--)
            {
                int s2 = num2[j] - '0';
                arr[i + j + 1] += s1 * s2;//注意這里是+=
            }
        }
    */
        //處理進位問題:
        int carry = 0;
        for (int i = length1 + length2 - 1; i >= 0; i--)
        {
       		int tmp = arr[i]+carry;				//保存當前位置中的元素大小,因為下一句代碼會影響giabarr[j]
            arr[i] = (arr[i] + carry) % 10;       //存放個位數(shù)
            carry = tmp / 10;          			 //存放十位數(shù)(進位數(shù)
        }

        //第一個位置是否有元素,最高位是否有效
        if (arr[0] != 0)
            amass.push_back(arr[0] + '0');
        //
        for (int i = 1; i < length1 + length2; i++)
        {
            amass.push_back(arr[i] + '0');
        }
        return amass;
    }
};

最后,感謝友友們閱讀本篇解題分享，希望這篇文章對您在解決問題過程中有所幫助。在解題過程中，我們需要不斷思考、嘗試、調(diào)整，才能得出正確的解決方案。同時，我們也要記得不斷學習、積累知識和經(jīng)驗，提升自己的能力。最后，祝您在解決問題的道路上越走越遠，不斷成長和進步。
文章來源地址http://www.zghlxwxcb.cn/news/detail-653758.html

到了這里，關(guān)于如何高效解決“字符串相乘“問題?的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！