leetcode 553. Optimal Division

比眉伴天荒 2022-06-13 00:25 153阅读 0赞

# 1.题目 #

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.  
给一个正整数列表，相邻数之间做浮点数除法，例如\[2,3,4\] 表示 2/3/4  
假设可以加上任意数量的括号，求怎样加括号得到最大的结果。返回加括号后字符串形式的除法。

Example:

> Input: \[1000,100,10,2\]  
> Output: “1000/(100/10/2)”

Explanation:  
1000/(100/10/2) = 1000/((100/10)/2) = 200  
去掉”1000/((100/10)/2)”中冗余的括号，返回结果 “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

# 2.分析 #

自己想不出来，看了solution

假设列表为\[x1,x2,x3…,xn\]  
除法表达式为 x1/x2/x3/x4…/xn  
x1始终是分子，x2始终是分母，把x3/../xn看做一个整体y  
y\*x1/x2 y最大为x3\*x4…\*xn  
所以这个题目有一个通用的答案  
x1/(x2/x3/…/xn)

# 3.代码 #

string optimalDivision(vector<int>& nums) {
        if (nums.size() == 1)
            return to_string(nums[0]);
        if (nums.size() == 2)
            return to_string(nums[0]) + "/" + to_string(nums[1]);
        string res = to_string(nums[0]) + "/(" + to_string(nums[1]);
        for (int i = 2; i < nums.size(); i++)
            res += "/" + to_string(nums[i]);
        res += ")";
        return res;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，153人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode:399.Evaluate Division 除法求值（C语言）

题目描述：给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations\[i\] = \[Ai, Bi\] 和 valu

川长思鸟来/ 2023年01月02日 13:29/ 0 赞/ 156 阅读

相关 leetcode:399. Evaluate Division

Equations are given in the format A / B = k, where A and B are variables represented as

分手后的思念是犯贱/ 2022年09月26日 02:13/ 0 赞/ 167 阅读

相关【codeforces】Divisibility

![这里写图片描述][20160723114657129] ![这里写图片描述][20160723114705957] 只要知道n/k为n一下能被k整除的数的总和就行了

红太狼/ 2022年09月24日 02:28/ 0 赞/ 181 阅读

相关 leetcode 553. Optimal Division | 553. 最优除法（暴力递归-＞傻缓存）

题目 [https://leetcode-cn.com/problems/optimal-division/description/][https_leetcode-cn

拼搏现实的明天。/ 2022年08月28日 10:59/ 0 赞/ 150 阅读

相关 Square division

[Problem - E1 - Codeforces][] ![在这里插入图片描述][fabfb0eacd514406a6859f6729b7e77c.png] 思路

爱被打了一巴掌/ 2022年08月28日 08:52/ 0 赞/ 171 阅读

相关 Integer Division

Integer Division Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述判

我就是我/ 2022年08月14日 05:49/ 0 赞/ 177 阅读

相关 Division

[Division][] <table> <tbody> <tr> <td><strong>Time Limit:</strong> 3000MS

布满荆棘的人生/ 2022年08月03日 15:59/ 0 赞/ 161 阅读

相关 leetcode 553. Optimal Division

1.题目 Given a list of positive integers, the adjacent integers will perform the float

比眉伴天荒/ 2022年06月13日 00:25/ 0 赞/ 154 阅读

相关 leetcode 553. Optimal Division 添加括号 + 最优除法

Given a list of positive integers, the adjacent integers will perform the float division

青旅半醒/ 2022年06月03日 04:08/ 0 赞/ 162 阅读

相关【LeetCode】368. Largest Divisible Subset

Given a set of distinct positive integers, find the largest subset such that every pair

﹏ヽ暗。殇╰゛Y/ 2022年04月18日 03:35/ 0 赞/ 173 阅读