553 最优除法（脑筋急转弯）

心已赠人 2022-08-29 12:49 138阅读 0赞

**1. 问题描述：**

给定一组正整数，相邻的整数之间将会进行浮点除法操作。例如， \[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\] 之间。  
数组中每个元素的大小都在 \[2, 1000\] 之间。  
每个测试用例只有一个最优除法解。  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/optimal-division

**2. 思路分析：**

对于这种题目我们可以先找一下其中的规律，可以发现t = a1 / a2 / a3 ... / an，要想使得结果最大那么我们在加括号的时候需要尽可能使得越多的数字由除法变成乘法，例如：a1/ a2 / a3 = a1 / (a2 / a3) = a1 / a2 \* a3，可以发现a2无论如何也无法变成乘法的，所以我们只需要在a2与an外面加上括号即可使得a2后面的数字都变成乘法，这样的结果肯定是最大的，我们需要在一开始特判一下nums中0，1，2个数字的情况即可。

**3. 代码如下：**

from typing import List
    
    
    class Solution:
        def optimalDivision(self, nums: List[int]) -> str:
            # 特判一下n = 0, 1, 2的情况
            n = len(nums)
            if n == 0:
                return ""
            elif n == 1:
                return str(nums[0])
            elif n == 2:
                return str(nums[0]) + "/" + str(nums[1])
            res = str(nums[0]) + "/("
            for i in range(1, n):
                res += str(nums[i]) + "/"
            res = res[:-1] + ")"
            return res