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

题目描述 给定一个含有数字和运算符的字符串,为表达式添加括号,改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, – 以及 * 。 示例 1: 输入: “2-1-1” 输出: [0, 2] 解释: ((2-1)-1) = 0 (2-(1-1)) = 2 示例 2: 输入: “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 来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/different-ways-to-add-parentheses著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 解法1 这道题目采用分治法来解决,题目要求实现函数diffWaysToCompute,输入算数表达式input,输出不同的括号组合产生的计算结果列表ans。首先,我们扫描input寻找操作符即+、-和*。如果在input中找不到任何一个运算符,那么它就是操作数,我们将它转化为数字类型,加入到ans中返回即可。否则,input是包含运算符的表达式,情况变得复杂。 如果遇到了操作符,则将input分割成左右两部分,左右两部分可能还是一个计算表达式,我们继续将它送给函数diffWaysToCompute递归的处理,得到左右两部分返回值leftOpnds与rightOpnds。我们将leftOpnds和rightOpnds按照操作符optr做笛卡尔积,将运算结果加入到ans中就完成了对运算符的处理,我们编写了函数calculate(char optr, List leftOpnds, List rightOpnds)来实现这个功能。 举一个例子,对于表达式input = “2*3-4*5″,先处理第一个运算符*,将input分割成左右两个表达式”2″和”3-4*5″。假设我们已经知道了”3-4*5″能产生结果列表[-5, -17](后面会说怎么算出来的)。那么将2与[-5, -17]做乘法就能得到[-10,…

Read more

321. 拼接最大数

题目描述 给定长度分别为 m 和 n 的两个数组,其元素由 0-9 构成,表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数,要求从同一个数组中取出的数字保持其在原数组中的相对顺序。 求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。 说明: 请尽可能地优化你算法的时间和空间复杂度。 示例 1: 输入: nums1 = [3, 4, 6, 5] nums2 = [9, 1, 2, 5, 8, 3] k = 5 输出: [9, 8, 6, 5, 3] 示例 2: 输入: nums1 = [6, 7] nums2 = [6, 0, 4] k = 5 输出: [6, 7, 6, 0, 4]…

Read more