You are given a 0-indexed string expression of the form “+” where and represent positive integers.
Add a pair of parentheses to expression such that after the addition of parentheses, expression is a valid mathematical expression and evaluates to the smallest possible value. The left parenthesis must be added to the left of ‘+’ and the right parenthesis must be added to the right of ‘+’.
Return expression after adding a pair of parentheses such that expression evaluates to the smallest possible value. If there are multiple answers that yield the same result, return any of them.
The input has been generated such that the original value of expression, and the value of expression after adding any pair of parentheses that meets the requirements fits within a signed 32-bit integer.
Example 1:
Input: expression = “247+38”Explanation: The expression evaluates to 2 _ (47 + 38) = 2 _ 85 = 170.
Output: “2(47+38)”
Note that “2(4)7+38” is invalid because the right parenthesis must be to the right of the ‘+’.
It can be shown that 170 is the smallest possible value.
Example 2:
Input: expression = “12+34”Explanation: The expression evaluates to 1 _ (2 + 3) _ 4 = 1 _ 5 _ 4 = 20.
Output: “1(2+3)4”
Example 3:
【数据结构|LeetCode每日一题(2232. Minimize Result by Adding Parentheses to Expression)】Input: expression = “999+999”Explanation: The expression evaluates to 999 + 999 = 1998.
Output: “(999+999)”
Constraints:
- 3 <= expression.length <= 10
- expression consists of digits from ‘1’ to ‘9’ and ‘+’.
- expression starts and ends with digits.
- expression contains exactly one ‘+’.
- The original value of expression, and the value of expression after adding any pair of parentheses that meets the requirements fits within a signed 32-bit integer.
impl Solution {
pub fn minimize_result(expression: String) -> String {
let tokens: Vec<&str> = expression.split("+").collect();
let left = tokens[0].parse::().unwrap();
let right = tokens[1].parse::().unwrap();
let mut ans = left + right;
let mut ans_str = expression.clone();
let mut left_exp = 0;
let mut right_exp = 0;
while left / 10i32.pow(left_exp) > 0 {
let mut a = left / 10i32.pow(left_exp);
let mut b = left % 10i32.pow(left_exp);
if a == left {
a = 1;
b = left;
}
while right / 10i32.pow(right_exp) > 0 {
let c = right / 10i32.pow(right_exp);
let mut d = right % 10i32.pow(right_exp);
if c == right {
d = 1;
}
let v = a * (b + c) * d;
if v < ans {
let mut s = String::new();
if left_exp == 0 {
s.push_str(&format!("({}", left));
} else {
s.push_str(&format!("{}({}", a, b));
}
s.push('+');
if right_exp == 0 {
s.push_str(&format!("{})", right));
} else {
s.push_str(&format!("{}){}", c, d))
}
ans_str = s;
ans = v;
}
right_exp += 1;
}
left_exp += 1;
right_exp = 0;
}
if ans_str == expression {
ans_str.insert(0, '(');
ans_str.push(')');
}
ans_str
}
}
推荐阅读
- 算法|【英雄哥六月集训】第 17天: 广度优先搜索
- 智能优化算法|智能优化算法(蜻蜓优化算法-附代码)
- 机器翻译|机器翻译评测----BLEU算法
- 多目标优化算法|多目标优化算法(多目标袋獾优化算法MOTDO(提供MATLAB代码))
- 机器人学习|【机器人】Car-Like小车移动机器人控制实验(word报告+matlab程序代码)
- 数据库|redis(redis的底层数据结构)
- Redis|redis底层数据结构
- c语言|问题 D: 马走日
- java基础 - 数据结构