【数字字符串互转】【C++】LeetCode#73 553. 最优除法 Medium
You are given an integer array nums. The adjacent integers in nums will perform the float division.
For example, for nums = [2,3,4], we will evaluate the expression "2/3/4".
However, you can add any number of parenthesis at any position to change the priority of operations. You want to add these parentheses such the value of the expression after the evaluation is maximum.
Return the corresponding expression that has the maximum value in string format.
Note: your expression should not contain redundant parenthesis.
Example 1:
Input: nums = [1000,100,10,2]
Output: "1000/(100/10/2)"
Explanation:
1000/(100/10/2) = 1000/((100/10)/2) = 200
However, the bold parenthesis in "1000/((100/10)/2)" are redundant, since they don't influence the operation priority.
So you should return "1000/(100/10/2)".
Other cases:
1000/(100/10)/2 = 50
1000/(100/(10/2)) = 50
1000/100/10/2 = 0.5
1000/100/(10/2) = 2
Example 2:
Input: nums = [2,3,4]
Output: "2/(3/4)"
Example 3:
Input: nums = [2]
Output: "2"
Constraints:
-
1 <= nums.length <= 10 -
2 <= nums[i] <= 1000 -
There is only one optimal division for the given iput.
给定一组正整数，相邻的整数之间将会进行浮点除法操作。例如， [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] 之间。 -
每个测试用例只有一个最优除法解。
「题解」
贪心思维：
最大结果->被除数尽量大，除数尽量小，
所以第一个数字作为被除数，后面所有部分除下来的结果作为除数：把逗号全部改成/，在第二个数字前面加(，在最后一个数字后面加)。
「细节」
题目给定输入数组长度在[1,10]之间，当所以当数组长度为1或2时，就不需要遍历加括号。单独把这两种情况说明一下。
遍历的时候，先把第一个数字加入到res中，并加入'/('。然后从下标i=1开始遍历，遍历到倒数第二个元素，即nums.size() - 2，加上'/'。再单独加上最后一个数字和')'即可。
「AC代码」
class Solution
{
public:
string optimalDivision(vector<int> &nums)
{
string res = "";
if (nums.size() == 1)
return to_string(nums[0]);
if (nums.size() == 2)
return to_string(nums[0]) + "/" + to_string(nums[1]);
res += to_string(nums[0]);
res += "/(";
for (int i = 1; i < nums.size() - 1; ++i)
{
res += to_string(nums[i]);
res += "/";
}
res += to_string(nums[nums.size() - 1]);
res += ")";
return res;
}
};
// 一次通过
「复杂度」
-
时间复杂度O(n) -
空间复杂度O(1)，返回值不计入