首页 > 其他分享 >LeetCode 241 为运算表达式设计优先级

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

时间:2023-04-28 13:46:21浏览次数:47  
标签:ch 优先级 241 result str expression LeetCode 表达式 mp

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

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

  生成的测试用例满足其对应输出值符合 32 位整数范围,不同结果的数量不超过 104

示例 1:

输入:expression = "2-1-1"
输出:[0,2]
解释:
((2-1)-1) = 0 
(2-(1-1)) = 2

示例 2:

输入: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

提示:

  • 1 <= expression.length <= 20
  • expression 由数字和算符 '+'、'-' 和 '*' 组成。
  • 输入表达式中的所有整数值在范围 [0, 99]

思路:
  带备忘录的动态规划,用小问题的解去计算大问题。一开始还没想到怎么写,陷入的表达式的分解,一看到表达式是字符串,就去想怎么解析表达式,用什么保存数字,用什么保存操作符了。

  其实不需要关心这些,只需要遍历字符串,对每个操作符两边的表达式可能的结果做组合就行。

vector<int> diffWaysToCompute(string expression) {
    unordered_map<string, vector<int>> mp;
    return helper(mp, expression);
}

vector<int> helper(unordered_map<string, vector<int>> &mp, string str) {
    vector<int> result;
    for (int i = 0; i < str.size(); ++i) {
        char ch = str[i];
        if (ch == '+' || ch == '-' || ch == '*') {
            vector<int> l, r;
            // 计算左边的表达式所有可能的结果
            string left = str.substr(0, i);
            if (mp.count(left)) 
                l = mp[left];
            else 
                l = helper(mp, left);
            // 计算右边的表达式所有可能的结果
            string right = str.substr(i + 1, str.size());
            if (mp.count(right)) 
                r = mp[right];
            else 
                r = helper(mp, right);
            // 左右两边表达式所有的结果进行合并
            for (auto & i : l) {
                for (auto &j : r) {
                    if (ch == '+')
                        result.push_back(i + j);
                    else if (ch == '-') 
                        result.push_back(i - j);
                    else
                        result.push_back(i * j);
                }
            }
        }
    }
    if (result.size() == 0)
        result.push_back(stoi(str));
    mp[str] = result;
    return result;
}

标签:ch,优先级,241,result,str,expression,LeetCode,表达式,mp
From: https://www.cnblogs.com/AngleLin/p/17361862.html

相关文章

  • 【二分查找】LeetCode 153. 寻找旋转排序数组中的最小值
    题目链接153.寻找旋转排序数组中的最小值思路首先分析一下旋转数组可能有的状态:左<中<右,此时最小值肯定在左边,应当收缩右边界左<中,中>右,此时最小值肯定在右半段,应当收缩左边界左>中,中<右,此时最小值肯定在左半段,应当收缩右边界分析这三种状态可以发现,中值小......
  • 【LeetCode动态规划#14】子序列系列题(最长递增子序列、最长连续递增序列、最长重复子
    最长递增子序列力扣题目链接(opensnewwindow)给你一个整数数组nums,找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7]是数组[0,3,1,6,2,2,7]的子序列。示例1:输入:nums=[10,9,2,5,3,7......
  • #yyds干货盘点# LeetCode程序员面试金典:外观数列
    题目:给定一个正整数n,输出外观数列的第n项。「外观数列」是一个整数序列,从数字1开始,序列中的每一项都是对前一项的描述。你可以将其视作是由递归公式定义的数字字符串序列:countAndSay(1)="1"countAndSay(n)是对countAndSay(n-1)的描述,然后转换成另一个数字字符串。前五项......
  • 调度器51—进程优先级 prio、static_prio、normal_prio、rt_priority
    一、概述structtask_struct{intprio;intstatic_prio;intnormal_prio;unsignedintrt_priority;...} 二、动态优先级——prioprio表示进程的当前优先级,是一个动态值,会在进程运行时不断变......
  • 【哈希表】LeetCode 895. 最大频率栈
    题目链接895.最大频率栈思路很容易想到使用map:valToFreq来记录每个值出现的频率,这是没问题的,但关键是如何通过频率寻找到应该返回的数。这时候我想到再加一个map:freqToVal来记录每个频率中出现的数字,为了符合题目返回最接近栈顶的元素的要求,freqToVal的键值对类型选择<......
  • 代码随想录Day38-Leetcode509. 斐波那契数,70. 爬楼梯,746. 使用最小花费爬楼梯
    咳咳,因为找实习+摆导致时间被浪费大半;先从动态规划学起吧,之前的慢慢补。理论基础动态规划的解题步骤1.确定dp数组及对应下标的含义2.确定dp的状态转移方程(递推公式)3.确定dp数组如何初始化4.确定dp遍历顺序5.距离推导dp数组验证509.斐波那契数题目链接:https://le......
  • Python中的运算符与优先级
    算术运算符这里仅列出与c++语法不一致的内容。指数a**b取模a%%b整除a//b比较运算符与c++语法完全相同,用于判断两个变量、常量或者表达式之间的大小,比较运算的结果是布尔类型。逻辑运算符与c++语法完全相同,对布尔型的常量、变量或表达式进行运算,逻辑运算的......
  • [leetcode]复制带随机指针的链表
    力扣链接思路一:遍历链表,将链表结点复制下来,控制随机指针,去找对应的第几个(相对位置)进行链接.思路二:以时间换空间,创建两个指针数组,分别存放两个链表中结点的地址,直接可以在指针数组中找到结点该方法比上面的方法更优,但是时间复杂度依旧很高,但是还是达不到O(N)思路三:1.拷......
  • leetcode-350-两个数组的交集 II 题解
    题目给定两个数组,编写一个函数来计算它们的交集。示例1:输入:nums1=[1,2,2,1],nums2=[2,2]输出:[2,2]示例2:输入:nums1=[4,9,5],nums2=[9,4,9,8,4]输出:[4,9]说明:输出结果中每个元素出现的次数,应与元素在两个数组中出现次数的最小值一致。我们可以不考虑输出结果......
  • 1351. 统计有序矩阵中的负数(leetcode)
    https://leetcode.cn/problems/count-negative-numbers-in-a-sorted-matrix/1351.统计有序矩阵中的负数1.二分法:把每一行进行一遍二分,找到正数与负数的边界,且此时grid[i][mid]也为负数,即边界下标的对应值是负数的左半边界那么一行中的个数即为size()-lclassSolution{pu......