目錄

1. 二進制求和（簡單）

2. 兩數相加（中等）

3. 兩數相除（中等）

4. 字符串相乘（中等）

---

1. 二進制求和（簡單）

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

class Solution {
public:string addBinary(string a, string b) {string ans;int i = a.size() - 1; // a的下標是從0到iint j = b.size() - 1; // b的下標是從0到jint carry = 0 ; // 進位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. 兩數相加（中等）

class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* preHead = new ListNode; // 哨兵節(jié)點ListNode* tail = preHead;int carry = 0; // 進位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. 兩數相除（中等）

假設被除數是a，除數是b。

如果a、b都是正數，且a>=b

a最多大于b的2^k倍，將a減去b的2^k倍，剩下的被除數再重復這樣的操作，直到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，余數是1

如果a、b都是負數，且a <= b

a最多小于b的2^k倍，將a減去b的2^k倍，剩下的被除數再重復這樣的操作，直到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，余數是-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;}}// 全部轉化為負數，如果全部轉化為正數，-2^31轉化為正數會溢出int negative = 2; // 表示被除數和除數有幾個是負數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. 字符串相乘（中等）

無進位相乘后相加，再處理進位。

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);// 無進位相乘后相加for (int i = 0; i < n2; i++){for (int j = 0; j < n1; j++){sums[i + j] += (num2[i] - '0') * (num1[j] - '0');}}// 處理進位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';}// 反轉reverse(ans.begin(), ans.end());return ans;}
};