class Solution {
public:
string optimalDivision(vector<int>& nums) {
}
};
553. 最优除法
给定一组正整数，相邻的整数之间将会进行浮点除法操作。例如， [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
说明:
原站题解
python3 解法, 执行用时: 36 ms, 内存消耗: 15 MB, 提交时间: 2022-11-27 12:55:34
class Solution:
def optimalDivision(self, nums: List[int]) -> str:
if len(nums) == 1:
return str(nums[0])
if len(nums) == 2:
return str(nums[0]) + "/" + str(nums[1])
return str(nums[0]) + "/(" + "/".join(map(str, nums[1:])) + ")"
javascript 解法, 执行用时: 64 ms, 内存消耗: 41.2 MB, 提交时间: 2022-11-27 12:55:07
/**
* @param {number[]} nums
* @return {string}
*/
var optimalDivision = function(nums) {
const n = nums.length;
if (n === 1) {
return '' + nums[0];
}
if (n === 2) {
return '' + nums[0] + "/" + '' + nums[1];
}
const res = [];
res.push(nums[0]);
res.push("/(");
res.push(nums[1]);
for (let i = 2; i < n; i++) {
res.push("/");
res.push(nums[i]);
}
res.push(")");
return res.join('');
};
golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2022-11-27 12:54:52
func optimalDivision(nums []int) string {
n := len(nums)
if n == 1 {
return strconv.Itoa(nums[0])
}
if n == 2 {
return fmt.Sprintf("%d/%d", nums[0], nums[1])
}
ans := &strings.Builder{}
ans.WriteString(fmt.Sprintf("%d/(%d", nums[0], nums[1]))
for _, num := range nums[2:] {
ans.WriteByte('/')
ans.WriteString(strconv.Itoa(num))
}
ans.WriteByte(')')
return ans.String()
}
golang 解法, 执行用时: 0 ms, 内存消耗: 2.2 MB, 提交时间: 2022-11-27 12:54:24
type node struct {
minVal, maxVal float64
minStr, maxStr string
}
func optimalDivision(nums []int) string {
n := len(nums)
dp := make([][]node, n)
for i := range dp {
dp[i] = make([]node, n)
for j := range dp[i] {
dp[i][j].minVal = 1e4
}
}
for i, num := range nums {
dp[i][i].minVal = float64(num)
dp[i][i].maxVal = float64(num)
dp[i][i].minStr = strconv.Itoa(num)
dp[i][i].maxStr = strconv.Itoa(num)
}
for i := 1; i < n; i++ {
for j := 0; j+i < n; j++ {
for k := j; k < j+i; k++ {
if dp[j][j+i].maxVal < dp[j][k].maxVal/dp[k+1][j+i].minVal {
dp[j][j+i].maxVal = dp[j][k].maxVal / dp[k+1][j+i].minVal
if k+1 == j+i {
dp[j][j+i].maxStr = dp[j][k].maxStr + "/" + dp[k+1][j+i].minStr
} else {
dp[j][j+i].maxStr = dp[j][k].maxStr + "/(" + dp[k+1][j+i].minStr + ")"
}
}
if dp[j][j+i].minVal > dp[j][k].minVal/dp[k+1][j+i].maxVal {
dp[j][j+i].minVal = dp[j][k].minVal / dp[k+1][j+i].maxVal
if k+1 == j+i {
dp[j][j+i].minStr = dp[j][k].minStr + "/" + dp[k+1][j+i].maxStr
} else {
dp[j][j+i].minStr = dp[j][k].minStr + "/(" + dp[k+1][j+i].maxStr + ")"
}
}
}
}
}
return dp[0][n-1].maxStr
}
javascript 解法, 执行用时: 96 ms, 内存消耗: 48 MB, 提交时间: 2022-11-27 12:54:06
/**
* @param {number[]} nums
* @return {string}
*/
var optimalDivision = function(nums) {
const n = nums.length;
const dp = new Array(n).fill(0).map(() => new Array(n).fill(0));
for (let i = 0; i < n; i++) {
for (let j = i; j < n; j++) {
dp[i][j] = new Node();
}
}
for (let i = 0; i < n; i++) {
dp[i][i].minVal = nums[i];
dp[i][i].maxVal = nums[i];
dp[i][i].minStr = '' + nums[i];
dp[i][i].maxStr = '' + nums[i];
}
for (let i = 1; i < n; i++) {
for (let j = 0; j + i < n; j++) {
for (let k = j; k < j + i; k++) {
if (dp[j][j + i].maxVal < dp[j][k].maxVal / dp[k + 1][j + i].minVal) {
dp[j][j + i].maxVal = dp[j][k].maxVal / dp[k + 1][j + i].minVal;
if (k + 1 === j + i) {
dp[j][j + i].maxStr = dp[j][k].maxStr + "/" + dp[k + 1][j + i].minStr;
} else {
dp[j][j + i].maxStr = dp[j][k].maxStr + "/(" + dp[k + 1][j + i].minStr + ")";
}
}
if (dp[j][j + i].minVal > dp[j][k].minVal / dp[k + 1][j + i].maxVal) {
dp[j][j + i].minVal = dp[j][k].minVal / dp[k + 1][j + i].maxVal;
if (k + 1 === j + i) {
dp[j][j + i].minStr = dp[j][k].minStr + "/" + dp[k + 1][j + i].maxStr;
} else {
dp[j][j + i].minStr = dp[j][k].minStr + "/(" + dp[k + 1][j + i].maxStr + ")";
}
}
}
}
}
return dp[0][n - 1].maxStr;
};
class Node {
constructor() {
this.maxStr;
this.minStr;
this.minVal = 10000.0;
this.maxVal = 0.0;
}
}
python3 解法, 执行用时: 36 ms, 内存消耗: 15 MB, 提交时间: 2022-11-27 12:53:48
class Node:
def __init__(self):
self.minVal = 1e4
self.maxVal = 0
self.minStr = ""
self.maxStr = ""
'''
设 dp[i][j] 表示数组 nums 索引区间 [i,j] 通过添加不同的符号从而可以获取的最小值与最大值为 minVal(i, j), maxVal(i, j)
'''
class Solution:
def optimalDivision(self, nums: List[int]) -> str:
n = len(nums)
dp = [[Node() for _ in range(n)] for _ in range(n)]
for i, num in enumerate(nums):
dp[i][i].minVal = num
dp[i][i].maxVal = num
dp[i][i].minStr = str(num)
dp[i][i].maxStr = str(num)
for i in range(n):
for j in range(n - i):
for k in range(j, j + i):
if dp[j][j + i].maxVal < dp[j][k].maxVal / dp[k + 1][j + i].minVal:
dp[j][j + i].maxVal = dp[j][k].maxVal / dp[k + 1][j + i].minVal
if k + 1 == j + i:
dp[j][j + i].maxStr = dp[j][k].maxStr + "/" + dp[k + 1][j + i].minStr
else:
dp[j][j + i].maxStr = dp[j][k].maxStr + "/(" + dp[k + 1][j + i].minStr + ")"
if dp[j][j + i].minVal > dp[j][k].minVal / dp[k + 1][j + i].maxVal:
dp[j][j + i].minVal = dp[j][k].minVal / dp[k + 1][j + i].maxVal
if k + 1 == j + i:
dp[j][j + i].minStr = dp[j][k].minStr + "/" + dp[k + 1][j + i].maxStr
else:
dp[j][j + i].minStr = dp[j][k].minStr + "/(" + dp[k + 1][j + i].maxStr + ")"
return dp[0][n - 1].maxStr