iT邦幫忙

0

簡介卡特蘭數(catalan number)- leetcode 96. Unique Binary Search Trees

卡特蘭數在組合學經常用於各種計數問題,可參考維基百科-卡塔蘭數

卡特蘭數的定義為Cn = C(2n,n)/(n+1)
遞迴定義為
https://ithelp.ithome.com.tw/upload/images/20200628/20117114GPs35zWGYw.png

譬如前十項卡特蘭數為1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862

卡特蘭數Cn可以用來計算以下各種情境:

  1. 由n個不同數字所組成的BST(binary search tree)
  2. n對合法的括號數量
  3. 用對角線把(n+2)邊形切成三角形的方法數
    (例: n=4的情形)
    https://ithelp.ithome.com.tw/upload/images/20200628/20117114oypsGmWOwG.png
  4. 在n*n的格點,由左下角出發,不越過對角線到右上角的最短路徑方法數
    (例: n=4的情形)
    https://ithelp.ithome.com.tw/upload/images/20200628/201171142XncqTtQCT.png

底下這道leetcode題正好就可以用卡特蘭數:
參考題目: 96. Unique Binary Search Trees
題意: 給定數字n,由1~n組成的binary search tree有幾種?

解法: 答案即是Cn = C(2n,n)/(n+1)
可以用動態規劃的方法(參考leetcode- 119. Pascal's Triangle II)求出組合數C(2n,n)的值

C++解法

class Solution {
public:
    long long Cnk(int n, int k) {
        vector<long long> pas(n+1, 1);
        for(int i=2; i<pas.size(); i++){
            for(int j=i-1; j>0;j--){
                pas[j]+=pas[j-1];
            }
        }
        return pas[k];
    }
    int numTrees(int n) {
        return Cnk(2*n,n)/(n+1);
    }
};

補題- leetcode 22. Generate Parentheses, 95. Unique Binary Search Trees II

我們現在知道了卡特蘭數可以計算「n對合法的括號數量」及「由n個不同數字所組成的BST」,
現在我們要學習如何用程式窮舉「n對合法的括號」及「由n個不同數字所組成的BST」

參考題目:
22. Generate Parentheses
95. Unique Binary Search Trees II

想法都是用遞迴來解題

22. Generate Parentheses

class Solution {
struct parenthesis{
    string expr;
    int left;
    int right;    
};
public:
    vector<string> generateParenthesis(int n) {
        deque<parenthesis> res = {{"(",1,0}};
        while(res.front().left< n || res.front().right< n){
            parenthesis p = res.front();
            string c = p.expr;
            int left = p.left, right=p.right;
            res.pop_front();
            if(left<n){
                res.push_back({c+'(', left+1, right});
            }
            if(right<n && left>right)
                res.push_back({c+')', left, right+1});
        }
        vector<string> ans;
        for(auto r: res){
            ans.push_back(r.expr);
        }
        return ans;
    }
};

95. Unique Binary Search Trees II

定義函數DFS(int start, int end)可以窮舉由數字[1,n]所構成的所有BST,
分別讓每個數字都有機會當root

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        return n == 0? vector<TreeNode*>():DFS(1, n);
    }
    
    vector<TreeNode*> DFS(int start, int end){
        if (start > end){
            return vector<TreeNode*>{NULL};
        }
        vector<TreeNode*> res;
        for (int i = start; i <= end; i++) {
            auto left = DFS(start, i - 1), right = DFS(i + 1, end);
            for (auto a : left) {
                for (auto b : right) {
                    TreeNode *node = new TreeNode(i);
                    node->left = a;
                    node->right = b;
                    res.push_back(node);
                }
            }
        }
        return res;
        
    }
};

尚未有邦友留言

立即登入留言