目錄

1. 二進(jìn)制求和（簡(jiǎn)單）

2. 兩數(shù)相加（中等）

3. 兩數(shù)相除（中等）

4. 字符串相乘（中等）

---

1. 二進(jìn)制求和（簡(jiǎn)單）

從字符串的右端出發(fā)向左做加法，逢二進(jìn)一。

class Solution {
public:string addBinary(string a, string b) {string ans;int i = a.size() - 1; // a的下標(biāo)是從0到iint j = b.size() - 1; // b的下標(biāo)是從0到j(luò)int carry = 0 ; // 進(jìn)位while (i >= 0 || j >= 0){int digitA = i >= 0 ? a[i--] - '0' : 0;int digitB = j >= 0 ? b[j--] - '0' : 0;int sum = digitA + digitB + carry;carry = sum >= 2 ? 1 : 0;sum = sum >= 2 ? sum - 2 : sum;ans += sum + '0';}if (carry){ans += '1';}reverse(ans.begin(), ans.end());return ans;}
};

2. 兩數(shù)相加（中等）

class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* preHead = new ListNode; // 哨兵節(jié)點(diǎn)ListNode* tail = preHead;int carry = 0; // 進(jìn)位while (l1 || l2){int n1 = l1 ? l1->val: 0;int n2 = l2 ? l2->val: 0;int sum = n1 + n2 + carry;tail->next = new ListNode(sum % 10);carry = sum / 10;tail = tail->next;if (l1){l1 = l1->next;}if (l2){l2 = l2->next;}}if (carry){tail->next = new ListNode(carry);}return preHead->next;}
};

3. 兩數(shù)相除（中等）

假設(shè)被除數(shù)是a，除數(shù)是b。

如果a、b都是正數(shù)，且a>=b

a最多大于b的2^k倍，將a減去b的2^k倍，剩下的被除數(shù)再重復(fù)這樣的操作，直到a < b

以22除以3為例：

22最多大于3的4倍：22 - 3 * 4 = 10

10最多大于3的2倍：10 - 3 * 2 = 4

4最多大于3的1倍： 4 - 3 * 1 = 1

商是4 + 2 + 1 = 7，余數(shù)是1

如果a、b都是負(fù)數(shù)，且a <= b

a最多小于b的2^k倍，將a減去b的2^k倍，剩下的被除數(shù)再重復(fù)這樣的操作，直到a > b

以-22除以-3為例：

-22最多小于-3的4倍：-22 - (-3) * 4 = -10

-10最多小于-3的2倍：-10 - (-3) * 2 = -4

-4最多小于-3的1倍： -4 - (-3) * 1 = -1

商是4 + 2 + 1 = 7，余數(shù)是-1

class Solution {
public:int divide(int dividend, int divisor) {// -2^31/-1=2^31 溢出if (dividend == INT_MIN){if (divisor == -1){return INT_MAX;}else if (divisor == 1){return INT_MIN;}}// 全部轉(zhuǎn)化為負(fù)數(shù)，如果全部轉(zhuǎn)化為正數(shù)，-2^31轉(zhuǎn)化為正數(shù)會(huì)溢出int negative = 2; // 表示被除數(shù)和除數(shù)有幾個(gè)是負(fù)數(shù)if (dividend > 0){dividend = -dividend;negative--;}if (divisor > 0){divisor = -divisor;negative--;}int result = divideCore(dividend, divisor);return negative == 1 ? -result : result;}private:int divideCore(int a, int b){int result = 0;while (a <= b){int k = 1;int val = b; // val表示b的2^k倍while (val >= INT_MIN / 2 && a <= val + val){k += k;val += val;}result += k;a -= val;}return result;}
};

4. 字符串相乘（中等）

無進(jìn)位相乘后相加，再處理進(jìn)位。

class Solution {
public:string multiply(string num1, string num2) {if (num1 == "0" || num2 == "0")return "0";int n1 = num1.size();int n2 = num2.size();reverse(num1.begin(), num1.end());reverse(num2.begin(), num2.end());vector<int> sums(n1 + n2 -1);// 無進(jìn)位相乘后相加for (int i = 0; i < n2; i++){for (int j = 0; j < n1; j++){sums[i + j] += (num2[i] - '0') * (num1[j] - '0');}}// 處理進(jìn)位string ans;int i = 0;int carry = 0;while (i < n1 + n2 -1){int sum = sums[i++] + carry;ans += sum % 10 + '0';carry = sum / 10;}if (carry){ans += carry + '0';}// 反轉(zhuǎn)reverse(ans.begin(), ans.end());return ans;}
};