Divide and Conquer – 陪你刷題

Divide and conquer (以下簡稱 D&C) 是一種設計演算法的思維模式,將問題切割為兩個以上的子問題,使用相同的解決邏輯處理各子問題,所有小問題的解合併起來即為原始問題的解。

為何會稱為 D&C 也是因為整個處理過程可以分為以下三個階段:

  1. Divide 分解:將一個問題分解為一系列子問題 (subproblem)。
  2. Conquer 解決:使用相同邏輯解決各子問題,如果問題夠小,可以直接求解。
  3. Combine 合併:將子問題的結果合併。

在第二個階段,以相同邏輯解決子問題,很容易可以聯想到遞迴,子問題夠小時,可以直接求解,就如同定義遞迴的終止條件 (base case or bottom case) 。

何時會應用 D&C

  1. 母問題適合被分割為兩個以上子問題來解時,且母問題和子問題可以用相同邏輯來解,例如 merge sort 和 quick sort 。
  2. 用在適合以遞迴來處理的資料結構上。 適合以遞迴來處理的資料結構具有一個特性,當資料結構被切割後,資料結構仍然具有一樣的性質,例如 array, binary tree traversal 或 linked list 。

D&C Template

前面提到 D&C 適合以遞迴處理,因此就如同遞迴一樣,

  1. 找出遞迴關係式。
  2. 定義出終止條件 ,換言之,問題小到可以直接求解 。

以下以兩個 LC 題目來講解 D&C 的應用:

LC#912 Sort an Array

這一題可以用來練習 merge sort , merge sort 是應用 D&C 來設計的 sort algorithm ,merge sort 網路上相當多文章,這邊就不再討論。

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        mergeSort (nums, 0, nums.size()-1);
        return nums;
    }
    void mergeSort (vector<int> &nums, int left, int right) {
        if (left == right)
            return;
        int mid = ((right-left)>>1)+left; 
        mergeSort (nums, left, mid);
        mergeSort (nums, mid+1, right);
        merge (nums, left, mid+1, right);
    }
    void merge (vector<int> &nums, int start,
               int second_start, int end) {
        int first_len = second_start-start;
        int second_len = end - second_start+1;
        vector<int> data1 (first_len);
        vector<int> data2 (second_len);
        for (int i=0; i<first_len; i++) {
            data1[i] = nums[start+i];
        }
        for (int i=0; i< second_len; i++) {
            data2[i] = nums[second_start+i];
        }
        int first = 0;
        int second = 0;
        int current = start;
        while (first < first_len && second < second_len) {
            if (data1[first] < data2[second]){
                nums[current] = data1[first];
                first++;
            } else {
                nums[current] = data2[second];
                second++;
            }
            current++;
        }
        while (first < first_len) {
            nums[current] = data1[first];
            first++;
            current++;
        }
    }
};

LC#105 Construct Binary Tree from Preorder and Inorder Traversal

題目要你構建出這棵樹 ,構建 tree 一定要找出 root, left subtree 和 right subtree 。

根據 preorder 的特性,preorder vector 的第一個元素會是 tree 的 root node ,找到 root node 後,接著找出 left 和 right subtree 出來,找出 root node 在 inorder vector 的位置,其左邊就是 left subtree ,右邊是 right subtree 。

有了以上概念,可以分出 root, 左子樹和右子樹 ,但是左子樹和右子樹還需要繼續以相同的邏輯來建構剩餘的樹出來,這樣的作法就吻合 D&C 的使用場景,原本問題是建立一棵樹,這個問題又可以切割為兩個子問題,分別是建構左子樹和建構右子樹。

這題有個可以特別提的一點,如果題目是 BST ,可以在 inorder vector 透過 binary search 找出 root ,但因為不是,使得 vector 沒有經過排序,想要搜尋的話,時間複雜度將需要到 O(n) ,碰到這個狀況,一般都會採取以空間換取時間的作法,透過一個 hash table 預先存下每個節點對應的 index ,當要尋找節點位置的 index 時,僅需 O(1) 。

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        unordered_map<int, int> record;
        for (int i=0; i<inorder.size(); i++) {
            record[inorder[i]] = i;
        }
        return buildHelper (record, preorder, inorder, 0, preorder.size()-1, 0, preorder.size()-1);
    }
    TreeNode* buildHelper (unordered_map<int, int>& record,
                        vector<int>& preorder, vector<int>& inorder, 
                          int inarr_left, int inarr_right,
                          int prearr_left, int prearr_right) {
        if (prearr_left > prearr_right) return nullptr;
        // Take first element of preorder array as root
        int root_val = preorder[prearr_left];
        TreeNode* newNode = new TreeNode(root_val);
        if (prearr_left == prearr_right) {
            return newNode;
        }
        int root_index = record[root_val];
        int left_subtree_size = root_index - inarr_left;
        newNode->left = buildHelper (record, preorder, inorder, inarr_left, root_index-1,
                                    prearr_left+1, prearr_left+1 + left_subtree_size-1);
        newNode->right = buildHelper (record, preorder, inorder, root_index+1, inarr_right,
                                     prearr_left+1+ left_subtree_size, prearr_right);
        return newNode;
    }
};

以上做法可以進一步優化,其實並不需要 preorder vector 上的 index ,因為 preoder 上的順序恰巧就是我們建構的順序,pre-order 就是先拜訪 root 再拜訪左右子樹。

class Solution {
public:
    int preorder_index = 0;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        unordered_map<int, int> record;
        for (int i=0; i<inorder.size(); i++) {
            record[inorder[i]] = i;
        }
        return buildHelper (record, preorder, inorder, 0, inorder.size()-1);
    }
    TreeNode* buildHelper (unordered_map<int, int>& record,
                          vector<int>& preorder, vector<int>& inorder, 
                          int inarr_left, int inarr_right) {
        if (inarr_left > inarr_right) return nullptr;
        // Take first element of preorder array as root
        int root_val = preorder[preorder_index++];
        TreeNode* newNode = new TreeNode(root_val);
        if (inarr_left == inarr_right) {
            return newNode;
        }
        int root_index = record[root_val];
        int left_subtree_size = root_index - inarr_left;
        newNode->left = buildHelper (record, preorder, inorder, inarr_left, root_index-1);
        newNode->right = buildHelper (record, preorder, inorder, root_index+1, inarr_right);
        return newNode;
    }
};

以下整理 D&C 跟各個常見演算法的差別:

D&C 和 binary search 的差別

divide and conquer 通常將問題分為 two or more sub-problems ,而不是再將它縮減為一個更小的問題,後者通常稱為 decrease and conquer ,例如 binary search 就屬於此類。

D&C 和 backtracking 差別

  1. D&C 問題只會有一個解,而 backtracking 問題會有多種解。舉例: D&C 用在 merge sort 問題而 backtracking 用在 N-Queen 問題。
  2. D&C 的每一步都是不可或缺的,而 backtracking 有些步驟未必能找到正解,會有很多的處理。
  3. D&C 的每一步都是清楚且事先定義好的,但是 backtracking 的每一步都是嘗試,並不知道會不會帶你找到正解。

D&C 和 DP/Greedy/Backtracking 的差別

後面三者都可以用來找出多階段決策(multiple decision process)問題的最佳解。

D&C 比較像是將問題分為多個平行子問題,如 merge sort 將一個大問題切割兩個較小的子問題; 而其他三類會將一個問題切割為多個階段的連續子問題,形成一組決策序列 (sequence) ,問題比較難被平行化解決,例如 DP 就存在最佳子結構特性: future decisions depend on eariler decisions

Reference

  1. Leetcode Explore - Divide and Conquer
  2. 演算法課程(Algorithms) Course 5

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。