---

算法原理

這兩道題都是屬于算法里一種經典題型：高精度加/減/乘/除法，需要我們模擬加/減/乘/除 列豎式運算。

二進制求和

題目鏈接

題目鏈接

題目描述

解題思路

先創建兩個指針分別指向字符串末尾，創建變量t存儲每次加法的結果。 首先一個while循環當兩個字符串都遍歷完并且變量值為0時跳出循環。
我們做加法是從后往前加，所以先創建兩個指針分別指向字符串末尾，把指向的值分別加到變量t中，注意這里我們a[end]訪問到的是字符’0’或’1’的ascll碼值，所以它還要減去’0’。
加完后不要忘記end–。
得到的值t還要模2才能把值+=到字符串中，因為二進制加法逢二進一，注意還要把得到的值加’0‘得到字符1的ASCII碼值，因為我們需要加的是字符1，再把t除二賦給t當作進位參與下一次加法運算。
因為s一直的尾插，所以最后還要把s逆置一下得到結果。

代碼

class Solution {
public:string addBinary(string a, string b) {string s;int end1 = a.size() - 1;int end2 = b.size() - 1;int t = 0;while (end1 >= 0 || end2 >= 0 || t){if(end1 >= 0)t += a[end1--] - '0';if(end2 >= 0)t += b[end2--] - '0';s += t % 2 + '0';t = t / 2;}reverse(s.begin(), s.end());return s;}
};

字符串相乘

題目鏈接

題目鏈接

題目描述

解題思路

這道題解法是我們依次相乘后的結果先不進位，乘完后一起相加得到結果后再進位，在加之前進位和加之后進位最后得到的結果是一樣的，無進位相乘再相加代碼編寫會更便捷。
步驟一：
先將原始字符字符串逆序，因為我們要將字符串數據相乘得到的數據存放到整型數組
vector中，逆序兩個字符串下標相加正好就和要存放位置的vector的下標對應。
步驟二：
兩層for循環搞定無進位相加，我們要開一個動態數組vector來存放無進位相加的結果，動態數組大小為m + n -1,這里我們考慮極限情況，下面999*999得到的結果也只是五個數，所以用m + n - 1來存是完全足夠的，下標的對應關系和我們之前分析的一樣。
這里還要特別注意因為題目的num1和num2是string對象，所以里面存的數據類型的char，也就是數字對應的ASCII碼值，所以[]取到的值還要減去字符0對應的 ASCII碼值。

步驟三：
這里就需要處理無進位相加的結果，這里思路和我們上一題二進制相加很類似，定義一個cur記錄vector下標，定義一個t記錄處理進位后的結果，這里也要注意把t尾插到string里要先加’0’。
步驟四：
這里是乘法，所以要比上一題多一個步驟，處理前導零。如果兩個乘數有其中一個為0那么結果就為單獨一個0，處理前導零之前有可能有多個0，具體幾個0取決于m+n-1的結果，那么就需要將多余的0刪除。
最后再將string逆置，就得到結果啦。

代碼

class Solution {
public:string multiply(string n1, string n2) {//1、準備工作reverse(n1.begin(),n1.end());reverse(n2.begin(),n2.end());size_t m = n1.size();size_t n = n2.size();//2、無進位相加vector<int> v(m + n - 1);for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){//字符ASCII碼轉換成數字v[i + j] += (n1[i] - '0') * (n2[j] - '0');}}//3、處理進位size_t cur = 0, t = 0;string ret;while(cur < m + n - 1 || t != 0){//避免越界if(cur < m + n - 1)t += v[cur++];//數字轉換成ASCII碼ret += (t % 10) + '0';t = t / 10;}//4、處理前導零while(ret.size() > 1 && ret.back() == '0')ret.pop_back();reverse(ret.begin(), ret.end());return ret;}
};

以上就是小編分享的全部內容了，如果覺得不錯還請留下免費的關注和收藏
如果有建議歡迎通過評論區或私信留言，感謝您的大力支持。
一鍵三連好運連連哦~~