一、字符串相加

點(diǎn)我直達(dá)~

思路：模擬豎式加法

• 1.將兩個(gè)字符串從右往左開(kāi)始進(jìn)行相加，使用一個(gè)變量ans表示進(jìn)位，如果兩個(gè)字符串的個(gè)位加法和大于10，那么讓進(jìn)位+1，個(gè)位和再%10，然后將結(jié)果存入到新的字符串strRet中
• 2.兩個(gè)字符串的十位和十位繼續(xù)相加，并且需要加上個(gè)位的進(jìn)位ans，步驟同1
• 3.這樣不斷相加，假如任意一個(gè)字符串的位數(shù)加完了，另一個(gè)字符串的位數(shù)未加完，比如：123+11，那就將該字符串連同上一位的進(jìn)位ans加上并復(fù)制到新的字符串strRet中，注意，在代碼的計(jì)算時(shí)，應(yīng)該是123+011，11前面的’0’是需要補(bǔ)位的
• 4.最后將strRet逆置即可得到我們想要的結(jié)果。

具體代碼如下：

寫(xiě)法1：

class Solution {
public:

    string addStrings(string num1, string num2)
    {
        int end1 = num1.size() - 1;
        int end2 = num2.size() - 1;
        string strRet;
        int ans = 0;

        while (end1 >= 0 && end2 >= 0)
        {
            int sum = (num1[end1]-'0')+(num2[end2]-'0') + ans;
            strRet += (sum % 10 + '0');
            ans = sum / 10;
            --end1;
            --end2;
        }

        while(end1 >= 0)
        {
            int sum = ((num1[end1] - '0' + ans));
            strRet += ( (sum%10) + '0');
            ans = sum/10;
            --end1;
        }

        while(end2 >= 0)
        {
            int sum = ((num2[end2] - '0' + ans));
            strRet += ( (sum%10) + '0');
            ans = sum/10;
            --end2;
        }

        if(ans!=0)
        {
            strRet +=( ans + '0');
        }

        reverse(strRet.begin(), strRet.end());
        return strRet;
    }
};

寫(xiě)法2：

class Solution {
public:
    string addStrings(string num1, string num2) 
    {
        int i = num1.length() - 1, j = num2.length() - 1, add = 0;
        string ans = "";
        while (i >= 0 || j >= 0 || add != 0) 
        {
            int x = i >= 0 ? num1[i] - '0' : 0;
            int y = j >= 0 ? num2[j] - '0' : 0;
            int result = x + y + add;
            ans.push_back('0' + result % 10);
            add = result / 10;
            i -= 1;
            j -= 1;
        }
        // 計(jì)算完以后的答案需要翻轉(zhuǎn)過(guò)來(lái)
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

二、字符串相乘

點(diǎn)我直達(dá)~

思路：模擬豎式乘法

字符串相乘的思路與字符串相加的思路類(lèi)似

• 1.任意取一個(gè)字符串作為被乘數(shù)，如果該字符串的長(zhǎng)度比另一個(gè)字符串短，則需要在不足的位數(shù)上補(bǔ)’0’
• 2.兩個(gè)字符串從個(gè)位開(kāi)始相乘，所得結(jié)果如果大于10，則使用變量ans來(lái)保存進(jìn)位，然后將個(gè)位的乘積%10，結(jié)果保存到新的字符串strRet中。
• 3.繼續(xù)重復(fù)2.的過(guò)程，在此期間如果任意一個(gè)字符串的長(zhǎng)度遍歷完了， 那么就將另一個(gè)字符串的剩余的位數(shù)+進(jìn)位ans復(fù)制保存到strRet新的字符串中。這個(gè)相加的過(guò)程可以調(diào)用字符串想加的函數(shù)完成。
• 4.最后逆置strRet字符串即可得到我們想要的結(jié)果。

具體代碼如下:

class Solution {
public:
    //將其中一個(gè)作為被乘數(shù)，將每一位拆分出來(lái)進(jìn)行相乘，然后把結(jié)果累計(jì)起來(lái)
    //其中，被乘數(shù)的位數(shù)如果大于2位，需要先提前加上0
    string multiply(string num1, string num2) 
    {
       string strret;
       if(num2[0] == '0' || num1[0] == '0')
       {
           return strret+='0';
       }
       int end1 = num1.size() -1;
       int end2 = num2.size() -1;

       for(int i = end2;i>=0;--i)
       {
           string cur;
           int add = 0;
           //num2是被乘數(shù)，需要補(bǔ)0
           for(int j = end2;j>i;--j)
           {
               cur+='0';
           }

            //開(kāi)始計(jì)算乘積
            for(int j = end1;j>=0;--j)
            {
                int val1 = (num1[j]-'0');
                int val2 = (num2[i]-'0');
                int sum = val1*val2+add;
                cur+=(sum%10 + '0');
                add = sum/10;
            }

            //這里如果進(jìn)位不等于0，還要把進(jìn)位加上
            if(add!=0)
            {
                cur+=(add + '0');
            }
            //計(jì)算結(jié)果需要逆置
            reverse(cur.begin(),cur.end());

            //然后累加起來(lái)
            strret = addStrings(strret,cur);
       }
        return strret;
    }

        string addStrings(const string &num1, const string &num2) 
        {
            int i = num1.length() - 1, j = num2.length() - 1, add = 0;
            string ans = "";
            while (i >= 0 || j >= 0 || add != 0) {
                int x = i >= 0 ? num1[i] - '0' : 0;
                int y = j >= 0 ? num2[j] - '0' : 0;
                int result = x + y + add;
                ans.push_back('0' + result % 10);
                add = result / 10;
                i -= 1;
                j -= 1;
        }
        
        // 計(jì)算完以后的答案需要翻轉(zhuǎn)過(guò)來(lái)
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

總結(jié)

通過(guò)寫(xiě)今天的字符串相加|字符串相乘，我大致學(xué)會(huì)了如何將字符串轉(zhuǎn)化為豎式的方法進(jìn)行相加/相乘。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-483543.html

到了這里，關(guān)于【每日撓頭算法(4)】字符串相加|字符串相乘的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！