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

53. 最大子序和

题目描述 给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。 进阶: 如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。 https://leetcode-cn.com/problems/maximum-subarray/ 解法1 – 使用DP,O(n) 我们定义与nums同型的一维数组dp,dp[i]表示必须使用nums[i]元素,得到的连续子数组的最大和。那么有dp[i] = max(nums[i], dp[i – 1] + nums[i])。 解释一下,如果前面累积的最大和是负数,那么使用累积的和与nums[i]相加会使得和更小,我们还不如直接使用nums[i]作为新的连续子数组。 时间复杂度O(n),空间复杂度O(n)。全部代码如下: 我们观察到dp[i]只依赖于dp[i-1],因此我们可以使空间复杂度压缩到O(1)。 解法2 – 分治法,O(nlogn) 我们定义函数maxSubArray(nums, l, r),表示区间[l, r]内找到的连续子数组的最大和。那么在区间[l, r]内的连续子数组最大和有3种来源: 来源于[l, m) (m = (l + r) / 2),记为max1; 来源与(m, r],记为max2; 来源于跨中间元素m的区间,记为max3 那么[l, r]区间的连续子数组最大和有max(max1, max2, max3)。其中,第3种情况比较复杂。我们需要从m的左右两侧出发,通过扫描来求和,如图1所示。 我们递归求解区间[l, r]的连续子数组的最大值,取max1、max2、max3中三者最大的作为[l, r]的连续子数组最大和,然后返回。…

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