題目

給定一組正整數(shù)，相鄰的整數(shù)之間將會進(jìn)行浮點(diǎn)除法操作。例如， [2,3,4] -> 2 / 3 / 4 。
但是，你可以在任意位置添加任意數(shù)目的括號，來改變算數(shù)的優(yōu)先級。你需要找出怎么添加括號，才能得到最大的結(jié)果，并且返回相應(yīng)的字符串格式的表達(dá)式。你的表達(dá)式不應(yīng)該含有冗余的括號。
示例：
輸入: [1000,100,10,2]
輸出: “1000/(100/10/2)”
解釋:
1000/(100/10/2) = 1000/((100/10)/2) = 200
但是，以下加粗的括號 “1000/((100/10)/2)” 是冗余的，
因?yàn)樗麄儾⒉挥绊懖僮鞯膬?yōu)先級，所以你需要返回 “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
說明:
輸入數(shù)組的長度在 [1, 10] 之間。
數(shù)組中每個(gè)元素的大小都在 [2, 1000] 之間。
每個(gè)測試用例只有一個(gè)最優(yōu)除法解。
來源：力扣（LeetCode）

解題思路

??這個(gè)題顯然是一道數(shù)學(xué)題，在一系列的數(shù)字中想要獲得最大的結(jié)果，那么就需要分子盡可能地大，分母盡可能地小。現(xiàn)在嘗試簡單證明示例1的做法，假設(shè)有一個(gè)序列∈[2,1000]，sequence=[a,b,c,d,e,f,g,…]，取任意一點(diǎn)進(jìn)行分割(a/b/c)/(d/e/f/g)，則分子不是最大，分母不是最小，若從a處分割a/(b/c/d…)，則分子最大且分母最小。

class Solution:def optimalDivision(self, nums: List[int]) -> str:if len(nums)==1:return str(nums[0])elif len(nums)==2:return str(nums[0])+'/'+str(nums[1])return str(nums[0])+'/'+'('+'/'.join([str(i) for i in nums[1:]])+')'

總結(jié)

以上是生活随笔為你收集整理的LeetCode中等题之最优除法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。