class Solution {
public:
string minimizeResult(string expression) {
}
};
2232. 向表达式添加括号后的最小结果
给你一个下标从 0 开始的字符串 expression ，格式为 "<num1>+<num2>" ，其中 <num1> 和 <num2> 表示正整数。
请你向 expression 中添加一对括号，使得在添加之后， expression 仍然是一个有效的数学表达式，并且计算后可以得到 最小 可能值。左括号 必须 添加在 '+' 的左侧，而右括号必须添加在 '+' 的右侧。
返回添加一对括号后形成的表达式 expression ，且满足 expression 计算得到 最小 可能值。如果存在多个答案都能产生相同结果，返回任意一个答案。
生成的输入满足：expression 的原始值和添加满足要求的任一对括号之后 expression 的值，都符合 32-bit 带符号整数范围。
示例 1：
输入：expression = "247+38"
输出："2(47+38)"
解释：表达式计算得到 2 * (47 + 38) = 2 * 85 = 170 。
注意 "2(4)7+38" 不是有效的结果，因为右括号必须添加在 '+' 的右侧。
可以证明 170 是最小可能值。
示例 2：
输入：expression = "12+34" 输出："1(2+3)4" 解释：表达式计算得到 1 * (2 + 3) * 4 = 1 * 5 * 4 = 20 。
示例 3：
输入：expression = "999+999" 输出："(999+999)" 解释：表达式计算得到 999 + 999 = 1998 。
提示：
3 <= expression.length <= 10expression 仅由数字 '1' 到 '9' 和 '+' 组成expression 由数字开始和结束expression 恰好仅含有一个 '+'.expression 的原始值和添加满足要求的任一对括号之后 expression 的值，都符合 32-bit 带符号整数范围原站题解
cpp 解法, 执行用时: 4 ms, 内存消耗: 5.8 MB, 提交时间: 2022-12-04 11:44:02
class Solution {
public:
string minimizeResult(string expression) {
int n = expression.size();
int mid = expression.find('+');
int best = INT_MAX;
string ans;
for (int i = 0; i < mid; ++i) {
for (int j = mid + 1; j < n; ++j) {
int p = (i == 0 ? 1 : stoi(expression.substr(0, i)));
int q = stoi(expression.substr(i, mid - i));
int r = stoi(expression.substr(mid + 1, j - mid));
int s = (j == n - 1 ? 1 : stoi(expression.substr(j + 1, n - j - 1)));
int result = p * (q + r) * s;
if (result <= best) {
best = result;
ans = expression.substr(0, i) + "(" + expression.substr(i, j - i + 1) + ")" + expression.substr(j + 1, n - j - 1);
}
}
}
return ans;
}
};
golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2022-12-04 11:43:42
func minimizeResult(expression string) (ans string) {
sp := strings.Split(expression, "+")
l, r := sp[0], sp[1]
for i, min := 0, math.MaxInt64; i < len(l); i++ { // 枚举左括号插入位置
a := 1
if i > 0 {
a, _ = strconv.Atoi(l[:i]) // 左括号左边的数（不存在时为 1）
}
b, _ := strconv.Atoi(l[i:]) // 左括号右边的数
for j := 1; j <= len(r); j++ { // 枚举右括号插入位置
c, _ := strconv.Atoi(r[:j]) // 右括号左边的数
d := 1
if j < len(r) {
d, _ = strconv.Atoi(r[j:]) // 右括号右边的数（不存在时为 1）
}
res := a * (b + c) * d
if res < min {
min = res
ans = fmt.Sprintf("%s(%s+%s)%s", l[:i], l[i:], r[:j], r[j:])
}
}
}
return
}
python3 解法, 执行用时: 32 ms, 内存消耗: 14.9 MB, 提交时间: 2022-12-04 11:43:05
class Solution:
def minimizeResult(self, expression: str) -> str:
n = len(expression)
mid = expression.index("+")
best, ans = float("inf"), ""
for i in range(mid):
for j in range(mid + 1, n):
result = int(expression[:i] or 1) * (int(expression[i:mid]) + int(expression[mid+1:j+1])) * int(expression[j+1:] or 1)
if result < best:
best = result
ans = expression[:i] + "(" + expression[i:j+1] + ")" + expression[j+1:]
return ans