leetcode演算法之分治法

• 2021 年 2 月 9 日
• AI
• C/C++/C#

今天來盤一盤 **分治法 ** 這類題目

使用python刷題分類整理的筆記,請參考: //github.com/lxztju/leetcode-algorithm/tree/v1

分治法

分而治之： 就是把一個複雜的問題分成兩個或更多的相同或相似的子問題，直到最後子問題可以簡單的直接求解，原問題的解即子問題的解的合併

• 241 為運算表達式設計優先順序 (Medium)
• 95 不同的二叉搜索樹 II (Medium)

241 為運算表達式設計優先順序 (Medium)

• 以運算符為分界將計算過程分為兩部分，左側的計算結果與右側的結果相互組合運算即可。

class Solution {
public:
    vector<int> diffWaysToCompute(string input) {
        int index = 0;
        int num = 0;
        while (index < input.size() && isdigit(input[index])){
            num = num* 10 + input[index] - '0';
            index++;
        }
        if (index == input.size())
            return {num};
        vector<int> ans;
        for(int i = index; i< input.size(); i++){
            if (input[i] == '+' || input[i] == '-' || input[i] == '*'){
                auto left = diffWaysToCompute(input.substr(0, i));
                auto right = diffWaysToCompute(input.substr(i+1));
                for (auto l : left){
                    for (auto r: right){
                        if (input[i] == '+')
                            ans.push_back(l + r);
                        else if (input[i] == '-')
                            ans.push_back(l - r);
                        else
                            ans.push_back(l * r);
                    }
                }
            }
        }
        return ans;
    }
};

95 不同的二叉搜索樹 II (Medium)

class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {    
        auto res = buildBST(1, n);
        return res; 
    }
    vector<TreeNode*> buildBST(int left, int right){
        if (left > right) return {nullptr};
        vector<TreeNode*> trees;
        for (int i = left; i <= right; i++){
            auto leftTrees = buildBST(left, i-1);
            auto rightTrees = buildBST(i+1, right);
            for (auto l : leftTrees){
                for (auto r : rightTrees){
                    TreeNode* root = new TreeNode(i);
                    root->left = l;
                    root->right = r;
                    trees.push_back(root);
                }
            }
        }
        return trees;
    }
};

更多分類刷題資料

• 微信公眾號： 小哲AI

  

• GitHub地址： //github.com/lxztju/leetcode-algorithm

• csdn部落格： //blog.csdn.net/lxztju

• 知乎專欄： //www.zhihu.com/column/c_1101089619118026752

• AI研習社專欄：//www.yanxishe.com/column/109