LeetCode 241 Different Ways to Add Parentheses

标签: 分治算法 LeetCode 发布于:2022-03-01 16:14:26 编辑于:2022-03-01 16:19:01 浏览量:527

概述

https://leetcode.com/problems/different-ways-to-add-parentheses/

分治法

遍历每一个运算符作为最终的运算符,左右两端分治。

(离谱,换了下内层的写法没想到运行时间和内存消耗差别这么大,按理说根本不影响逻辑才对)

class Solution {
public:
    vector<string> e;
    vector<int> diffWaysToCompute(string expression) {
        string t;
        for (auto c : expression) {
            if (!isdigit(c)) {
                e.push_back(t);
                e.push_back(string(1, c));
                t = "";
            } else {
                t += c;
            }
        }
        e.push_back(t);
        return helper(0, e.size() - 1);
    }
    
    vector<int> helper(int l, int r) {
        if (l == r) return {stoi(e[l])};
        vector<int> ans;
        for (int i = l; i <= r; i ++) {
            if (e[i] == "*" || e[i] == "+" || e[i] == "-") {
                vector<int> ln = helper(l, i-1);
                vector<int> rn = helper(i+1, r);
                for (auto a : ln) {
                    for (auto b : rn) {
                        if (e[i] == "*") {
                            ans.push_back(a * b);
                        } else if (e[i] == "+") {
                            ans.push_back(a + b);
                        } else {
                            ans.push_back(a - b);
                        }
                    }
                }
            }
        }
        return ans;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/