题目描述
这是 LeetCode 上的 553. 最优除法 ,难度为 中等。
Tag : 「贪心」、「数学」
给定一组正整数,相邻的整数之间将会进行浮点除法操作。例如, [2,3,4] -> 2 / 3 / 4 。
但是,你可以在任意位置添加任意数目的括号,来改变算数的优先级。你需要找出怎么添加括号,才能得到最大的结果,并且返回相应的字符串格式的表达式。你的表达式不应该含有冗余的括号。
示例:
输入: [1000,100,10,2] 输出: "1000/(100/10/2)" 解释: 1000/(100/10/2) = 1000/((100/10)/2) = 200 但是,以下加粗的括号 "1000/((100/10)/2)" 是冗余的, 因为他们并不影响操作的优先级,所以你需要返回 "1000/(100/10/2)"。 其他用例: 1000/(100/10)/2 = 50 1000/(100/(10/2)) = 50 1000/100/10/2 = 0.5 1000/100/(10/2) = 2 复制代码
说明:
- 输入数组的长度在 [1, 10][1,10] 之间。
- 数组中每个元素的大小都在 [2, 1000][2,1000] 之间。
- 每个测试用例只有一个最优除法解。
数学 + 贪心
我们假定取得最优解的表示为 \frac{a}{b}ba,可以留意到任意的 nums[i]nums[i] 的范围为 [2, 1000][2,1000],因此我们应当让尽可能多的 nums[i]nums[i] 参与 aa(分子)的构建中。
因此一种可以构成最优表示的方式为「将除第一位以外的所有数作为一组,进行连除(转乘法),从而将所有 可以 变成分子的数都参与到 aa 的构建中」。
即有:
\frac{nums[0]}{nums[1] / nums[2] / ... / nums[n - 1]} = \frac{nums[0]}{nums[1] * \frac{1}{nums[2]} * ... * \frac{1}{nums[n - 1]}} = \frac{nums[0] * nums[2] * ... * nums[n - 1]}{nums[1]}nums[1]/nums[2]/.../nums[n−1]nums[0]=nums[1]∗nums[2]1∗...∗nums[n−1]1nums[0]=nums[1]nums[0]∗nums[2]∗...∗nums[n−1]
综上,我们只需要从前往后进行构建出连除的答案,如果 numsnums 的长度大于 22,再追加一对大括号即可。
[a_0, a_1, ... , a_n][a0,a1,...,an] => a_0/a_1/.../a_na0/a1/.../an => a_0/(a_1/.../a_n)a0/(a1/.../an)
代码:
class Solution { public String optimalDivision(int[] nums) { int n = nums.length; StringBuilder sb = new StringBuilder(); for (int i = 0; i < n; i++) { sb.append(nums[i]); if (i + 1 < n) sb.append("/"); } if (n > 2) { sb.insert(sb.indexOf("/") + 1, "("); sb.append(")"); } return sb.toString(); } } 复制代码
- 时间复杂度:O(n)O(n)
- 空间复杂度:O(n * C)O(n∗C),其中 CC 为 nums[i]nums[i] 的最大长度,对于本题 C = 4C=4
最后
这是我们「刷穿 LeetCode」系列文章的第 No.553
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour… 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。