553. Optimal Division

Given a list of positive integers, the adjacent integers will perform the float division. For example, [2,3,4] -> 2 / 3 / 4.

However, you can add any number of parenthesis at any position to change the priority of operations. You should find out how to add parenthesis to get the maximum result, and return the corresponding expression in string format. Your expression should NOT contain redundant parenthesis.

Example:

Input: [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

Note:

The length of the input array is [1, 10].
Elements in the given array will be in range [2, 1000].
There is only one optimal division for each test case.

思路:x1/x2/.../xn,无论在之间加多少个括号,x1总是作为被除数,x2总是作为除数,因此结果最大的做法是将x3到xn的所有除法转换为乘法,即x1/(x2/.../xn)=x1/x2*x3*...*xn.

string optimalDivision(vector<int>& nums) {
    string res;
    int n = nums.size();
    //特殊情况处理
    if (n == 1) return to_string(nums[0]);
    if (n == 2) return to_string(nums[0]) + "/" + to_string(nums[1]);
    //一般情况
    res = to_string(nums[0]) + "/(";
    for (int i = 1; i < n - 1; i++) {
        res += to_string(nums[i]) + "/"; //注意运算符优先级,+比+=要优先,这样的用法是可以的
    }
    res += to_string(nums[n - 1]) + ")";
    return res;
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • Given a list of positive integers, the adjacent integers ...
    matrxyz阅读 232评论 0 0
  • 来源: http://www.douban.com/group/topic/14820131/ 调整变量格式: f...
    MC1229阅读 6,958评论 0 5
  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,774评论 0 33
  • 今晚刷了个朋友圈,看到了高中的班主任发了一条朋友圈——“匆忙来,匆忙去,非常感谢这些年你们的帮助和支持!”外加九宫...
    载风载尘阅读 407评论 1 1
  • 有压力之时,身体就会因为过度的紧绷而出现某种病症,脑子隐隐泛晕,强行吃下两颗感冒药来震住,本打算早起模拟一套题,却...
    草木吟阅读 293评论 0 0