加法的變形題 – 陪你刷題

Leetcode 邁向千題的關卡，想要把所有題目刷過一遍，對於一位上班族來說就跟寫出來的程式沒有 bug 一樣困難，因此想要將刷題常用的觀念技巧與其對應題目整理出來，一方面可以整理自己思緒，也可以做為未來複習用。
這系列文章會一直持續下去，算是作為工程師職涯的隨身裝備。

在 leetcode 上有許多加法運算題目，差別在於 input 為各種資料結構，根據 leetcode 上的說法，這類型題目是 facebook 面試官愛考的題目，下面整理出四大類題目。

  • String 加法
  • Integer 加法
  • Array 加法
  • Linked list 加法

String 加法

這類題目基本上透過 digit-by-digit 的加法即可。

Leetcode #67 Add Binary

Input: a = "11", b = "1"
Output: "100"

方法 1 Bit-By-Bit computation

最直覺的作法。
如果 a_bit, b_bit 和 carry 加起來為 1 或 3，代表該 bit 為 1，另外一個方法為將三個數做 XOR ，這樣的方法更為簡潔。

class Solution {
public:
    string addBinary(string a, string b) {
        string result = "";
        int a_pos = a.size() -1;
        int b_pos = b.size() -1;
        int a_bit, b_bit, carry = 0;

        while (a_pos >= 0 || b_pos >= 0 || carry == 1)
        {
            a_bit = b_bit = 0;

            if (a_pos >= 0) a_bit =
                    (a[a_pos--] == '1');
            if (b_pos >= 0) b_bit =
                    (b[b_pos--] == '1');

            result = static_cast<char>
                (a_bit ^ b_bit ^ carry + '0')
                + result;
            carry = a_bit + b_bit + carry >= 2;
        }
        return result;
    }
};

方法 2 方法1加上 bit manipulation

如果進一步要求不能使用加法，該如何做到呢？

1 + 1 = 0b10 可以透過 XOR, AND 和 left shift 來完成：

  1. 透過 XOR 運算，可以得到 LSB 的答案
    1 xor 1 = 0
  2. 透過 AND 運算，可以得到加法後進位的答案
    (1 & 1) = 1

如果還需要考慮 carry ，處理起來會更複雜一點，可見下面完整程式碼。

class Solution {
public:
    string addBinary(string a, string b) {
        string result = "";
        int a_pos = a.size() -1;
        int b_pos = b.size() -1;
        int a_bit, b_bit, carry = 0;

        while (a_pos >= 0 || b_pos >= 0 || carry == 1)
        {
            a_bit = b_bit = 0;

            if (a_pos >= 0) a_bit = a[a_pos--] == '1';
            if (b_pos >= 0) b_bit = b[b_pos--] == '1';

            int curr = a_bit ^ b_bit ^ carry;

            result = static_cast<char>(curr + '0') + result; 
            carry = ((a_bit^b_bit) & carry) | (a_bit & b_bit);
        }
        return result;
    }
};

Leetcode #415 Add Strings

直覺作法為 digit-by-digit 的處理，由兩個字串的最右邊 digit 開始，轉為 integer 進行加法，持續向左處理。

  • 延伸練習: LC #43

Integer 加法

Leetcode #371 Sum of Two Integers

這題給你兩個整數，要你不使用任何加法，算出兩數相加的結果。

透過 XOR, AND, left shift 來相加兩個整數：

  1. XOR 可以將所有會進位的 bit 抹除。
  2. 透過 AND 運算可以標記出所有相加後會發生進位的位置，再透過 left shift (<< 1) 即可以得出相加後發生進位的結果。

Leetcode_371

將這兩步驟的結果相加即為原本兩數相加後的答案，但這題要求不使用任何加法。
竟然兩步驟的結果相加即為原本兩數相加，可以將這兩個步驟的結果當做另外的兩個整數，再次執行同樣的兩步驟，又可以得到新的一組整數，不斷重複執行，直到步驟 2 得到的結果為 0 ，代表將兩數的和都放到步驟 1 的結果了。

class Solution {
public:
    int getSum(int a, int b) {
        int sum = a;

        while (b!=0)
        {
            sum = a^b;
            b = (a&b) <<1;
            a = sum;
        }
        return sum;
    }
};

要特別注意一個 test case: a = -1, b = 1 ，此時會編譯錯誤，原因為不能執行 left shift operation 在負數上，這是 undefined behavior (a 和 b 不斷運算後，最終會得到 a&b 變成負值，這個過程可以自行推導，這邊就不詳細說明）。

使用 long 型別的 bit mask 來避開這個問題，再經過好幾輪運算後，(a&b) 會變成負數中的最大值 (-2^31)，此時再進行 left shift 會是 undefined behavior ，透過與 long 型別的 bit mask 做 AND 運算，(a&b) 會轉為 long type ，其值就不再是一個負數。

接著做完 left shift 後，結果會被 assign 給變數 b ，變數 b 是 integer 型別 ，此時運算結果又會由 long type 被轉為 int type ，超過 int type 的 bit 數就會被截斷，得到的結果將會是預期的答案。

class Solution {
public:
    int getSum(int a, int b) {
        int sum = a;
        long mask = 0xFFFFFFFF;

        while (b!=0)
        {
            sum = a^b;
            b = ((a&b) & mask)<<1;
            a = sum;
        }
        return sum;
    }
};

Array 加法

Leetcode #066 Plus One

只有在 digit 為 9 的時候才需要特別處理，否則直接將 digit 加1即可。

Digit 為 9 的話，要將 digit 設為 0，並持續往後面的 digit 進行加法。

最後一種特殊狀況為每個 digit 都為 9 ，這時候需要在 array 開頭補上 1 。

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int size = digits.size ();
        for (int i=size-1; i>=0; i--)
        {
            if (digits[i] == 9)
            {
                digits[i] = 0;
            }
            else
            {
                digits[i]++;
                return digits;
            }
        }
        digits.insert (digits.begin(), 1);
        return digits;
    }
};

Leetcode #989 Add to Array-Form of Integer

由數值小的位置開始，逐個 digit 跟 K 相加，需注意有可能 K 比 Input array 還要大，處理完 input array ，還要檢查 K 是否還有數值。

Linked List 加法

Leetcode #369 Plus One Linked List

Linked list 缺點是只能依序走訪，必須想清楚可能狀況，才能夠在 O(N) 情況下完成。

解題演算法

  1. 建立一個哨兵節點
  2. 紀錄節點數值非9中最右邊的一個點，將該點加 1
  3. 若此點後面有 9 ，全部將其轉為 0
  4. 如果第二步驟找到的該點為哨兵節點，代表原始 linked list 上都是 9 ，需要回傳哨兵節點，否則回傳原始 linked list 的頭節點即可。
class Solution {
public:
    ListNode* plusOne(ListNode* head) {
        ListNode *sentinel = new ListNode(0);
        sentinel->next = head;
        ListNode *notNine = sentinel;

        while (head != nullptr)
        {
            if (head->val != 9)
                notNine = head;
            head = head->next;
        }
        notNine->val++;
        while (notNine->next != nullptr)
        {
            notNine = notNine->next;
            notNine->val = 0;
        }

        if (sentinel->val == 1) {    
            return sentinel;
        }
        else
        {
            return sentinel->next;
        }
    }
};

Leetcode #002 Add Two Numbers

這題相當簡單，就是 digit-by-digit 的加法操作，可以特別注意 edge case ，例如 input 為 :
Linked List1 = [ 9, 9 ]
Linked List2 = [ 9, 9, 9, 9, 9]

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int carry = 0;
        ListNode head(0);
        ListNode *curr = &head;

        while (l1 != nullptr || l2 != nullptr || carry != 0)
        {
            int sum = 0;
            if (l1 != nullptr)
            {
                sum += l1->val;
                l1 = l1->next;
            }
            if (l2 != nullptr)
            {
                sum += l2->val;
                l2 = l2->next;
            }
            if (carry > 0)
            {
                sum += carry;
            }
            ListNode *newNode = new ListNode (sum % 10);
            carry = sum/10;
            curr->next = newNode;
            curr = curr->next;
        }
        return head.next;
    }
};

Leetcode #445 Add Two Numbers II

方法1

  1. 走訪兩個 linked list 知道其長度。
  2. 再次走訪兩個 linked list 來製造將作為答案的 Linked list ，相加節點數值並存下來。
  3. 走訪 step 2 所完成的 Linked list ，當 node->next 的值大於 10，當前節點就加 1，接著走到 next ，將數值對 10 取餘數。

Time Complexity

  1. O (m+n)
  2. O ( max (m, n) )
  3. O ( max (m, n) )

方法2

  1. 將兩個 linked list 進行反轉操作
  2. 依序走訪 linked list 並進行加法即可，跟 #002 一樣做法。
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        l1 = reverseList (l1);
        l2 = reverseList (l2);
        int carry = 0;
        ListNode *curr = nullptr;
        while (l1 != nullptr || l2 != nullptr || carry)
        {
            int sum = 0;
            if (l1 != nullptr)
            {
                sum += l1->val;
                l1 = l1->next;
            }
            if (l2 != nullptr)
            {
                sum += l2->val;
                l2 = l2->next;
            }
            sum += carry;
            ListNode *newNode = new ListNode (sum%10);
            newNode->next = curr;
            curr = newNode;
            carry = sum/10;
        }
        return curr;
    }

private:
    ListNode* reverseList (ListNode *head)
    {
        ListNode *prev = nullptr, *nxt;
        while (head != nullptr)
        {
            nxt = head->next;
            head->next = prev;
            prev = head;
            head = nxt;
        }
        return prev;
    }
};

Time Complexity

  1. O (m+n)
  2. O ( max (m, n) )

Updated on 2021-05-29 22:26:01 星期六

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *