0

分治枚举

 2 years ago
source link: https://yuanjie-ai.github.io/2022/04/04/divide-conquer-enumerate/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

之后的日子，大概会放缓刷题的脚步进行简单的整理，因为有些题目是有规律的，需要做号总结和整理，不能刷一个忘一个。今日总结：题目要求返回所有结果，且能找到分界点分解为子问题的，都可以套用分治枚举算法。

分治算法枚举

众所周知，枚举是个技术活，如何合理的枚举所有结果、避免重复和剪枝，并没有想象的那么简单。而分治枚举就是，通过将原问题分割为多个子问题，多个子问题的解排列组合能产生多种答案，我们收集多种答案并返回。

对于此类问题，我们需要确定三个东西：分界点，递归函数，如何排列组合。这样，给定一个分界点，我们把问题分解为左侧问题和右侧问题，两者答案的组合就是当前分界点对应的所有结果。然后再移动分界点，得到其他所有结果即可。此外，再分割得到子问题并求解时，需要设置 base case 用于退出递归。

96. 不同的二叉搜索树

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。如下的示例，3 个节点能组成 5 种二叉树。

1.jpg

那我们考虑给出那三个东西：

  1. 分界节点，以不同的值作为根节点，遍历所有的情况
  2. 既然有了根节点，就需要构建左子树。定义一个函数，返回某子树对应的情况，也就能得到分界点左子树有多少情况，同理得到右子树的排列组合
  3. 而左子树和右子树的乘积就是当前根节点对应的结果

我们定义一个函数，函数有两个参数，这两个参数是子树的取值范围，因此，退出递归的 base case 就是子树的左侧值大于右侧值，此时返回 1，因为表示调用者的结果是 1，不能再划分为子问题了。函数的返回值是这种取值范围下，有多少结果。我们写出程序：

class Solution {
public:
    int res = 0;
    vector<vector<int>> memo;
    int numTrees(int n) {
        vector<vector<int>> tmp(n, vector<int>(n, 0));
        memo = tmp;
        return build(1, n);
    }

int build(int l, int r) {
        // base case
        if (l > r)
            return 1;
        if (memo[l-1][r-1] != 0)
            return memo[l-1][r-1];
        for (int i = l; i <= r; i++) {
            int a = build(l, i - 1);
            int b = build(i + 1, r);
            // 累积所有的结果
            memo[l-1][r-1] += a*b;
        }
        return memo[l-1][r-1];
    }
};

其中，memo 起到剪枝的效果。

95. 不同的二叉搜索树 II

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。如下的示例，3 个节点能组成 5 种二叉树。

1.jpg

输入：n = 3
输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

同上一题，既然要给出所有的子树结果，那么此时就不需要计数，而是需要创建子树。同样以根节点的取值为分界点，统计出所有可能的左子树，统计出所有可能的右子树，上一题为结果相加，那么这个题目需要对左右子树的结果进行排列组合。因为这题不会超时，因此没有设置剪枝。

vector<TreeNode*> build(int l, int r) {
    if (l > r) {
        return {nullptr};
    }
    vector<TreeNode*> res;
    for (int i = l; i <= r; i++) {
        auto leftTree = build(l, i - 1);
        auto rightTree = build(i + 1, r);
        // 创建子树，等价于上一题的相加
        for (auto a : leftTree) {
            for (auto b : rightTree) {
                TreeNode* node = new TreeNode(i);
                node->left = a;
                node->right = b;
                res.emplace_back(node);
            }
        }
    }
    return res;
}

241. 为运算表达式设计优先级

给你一个由数字和运算符组成的字符串 expession ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以 按任意顺序 返回答案。

输入：expression = "2*3-4*5"
输出：[-34,-14,-10,-10,10]
解释：
(2*(3-(4*5))) = -34 
((2*3)-(4*5)) = -14 
((2*(3-4))*5) = -10 
(2*((3-4)*5)) = -10 
(((2*3)-4)*5) = 10

最开始我以为这是回溯，后来发现不是，因此总结出一个规律：题目要求返回所有结果，且能找到分界点分解为子问题的，都可以套用分治枚举算法。对于这个题而言，运算符就是分界点，然后枚举左侧和右侧有几种结果即可。

vector<int> diffWaysToCompute(string expression) {
    vector<int> res;
    for (int i = 0; i < expression.size(); i++) {
        if (expression[i] == '-' || expression[i] == '*' || expression[i] == '+') {
            // 分治，左侧有几种结果
            auto res1 = diffWaysToCompute(expression.substr(0, i));
            auto res2 = diffWaysToCompute(expression.substr(i + 1));
            // 枚举所有结果，并追加，和第一题的 += 一样
            for (auto it1 : res1) {
                for (auto it2 : res2) {
                    if (expression[i] == '-')
                        res.push_back(it1 - it2);
                    if (expression[i] == '+')
                        res.push_back(it1 + it2);
                    if (expression[i] == '*')
                        res.push_back(it1 * it2);
                }
            }
        }
    }
    if (res.size() == 0) {
        return {stoi(expression)};
    }
    return res;
}

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK