LeetCode 553. Optimal Division (最优除法)
题目
链接
https://leetcode-cn.com/problems/optimal-division/
问题描述
给定一组正整数,相邻的整数之间将会进行浮点除法操作。例如, [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)"。
提示
输入数组的长度在 [1, 10] 之间。
数组中每个元素的大小都在 [2, 1000] 之间。
每个测试用例只有一个最优除法解。
思路
题目应该是很难的,但是数据范围没确定好,就成了一个字符串修改的题目。
- 如果只有一个数,输出即可
- 如果两个数,第一个数除第二个数即可
- 多个数,A/(B/C/D/...)即可,只需要确定插入/位置正确即可。
复杂度分析
时间复杂度 O(n)
空间复杂度 O(n)
代码
Java
public String optimalDivision(int[] nums) {
int n = nums.length;
String ans = String.valueOf(nums[0]);
if (n == 1) {
return ans;
}
if (n == 2) {
return ans + "/" + String.valueOf(nums[1]);
}
ans += "/(";
for (int i = 1; i < n; i++) {
ans += String.valueOf(nums[i]);
if (i != n - 1) {
ans += "/";
} else {
ans += ")";
}
}
return ans.toString();
}