0553. Optimal Division ====================== 题目信息 -------- :题号: 0553 :难度: Medium :主题: 正整数数组、连续除法、括号、最大结果表达式 :原题: `LeetCode 0553 `_ :重点: 数字顺序不能改变、只能插入除号与括号、返回使结果最大的表达式字符串、避免多余括号 题目重述 -------- 给定正整数数组 ``nums``,必须保持数字原顺序,并在相邻数字之间插入除号 ``/``。可以添加括号来改变运算结合方式,目标是使整个表达式的数值最大。 返回一个达到最大值的表达式字符串。不能改变数字顺序或省略数字;返回结果不应包含无意义的冗余括号。若数组只有一个数字,直接返回该数字的十进制字符串。 自建示例 -------- 括号改变连续除法结果: .. code-block:: text 输入:nums = [8,4,2] 输出:"8/(4/2)" 解释:该表达式结果为 4,而按从左到右计算 (8/4)/2 只得到 1。 只有一个数字: .. code-block:: text 输入:nums = [5] 输出:"5" 解释:没有可插入的除号,也不需要括号。 把后续除法整体放进分母 ---------------------- 所有数字为正数时,表达式 ``a / b / c`` 的连续左结合会继续除以 ``c``,而把后缀写成 ``a / (b / c / ...)`` 等价于让 ``c`` 及其后数字乘到整体结果的分子中,从而最大化结果。因而最优结构是第一项单独放在分子,第二项到末项全部放入一对括号中。 C++ 实现 -------- .. code-block:: cpp class Solution { public: std::string optimalDivision(std::vector& nums) { if (nums.size() == 1) return std::to_string(nums[0]); if (nums.size() == 2) { return std::to_string(nums[0]) + "/" + std::to_string(nums[1]); } std::string result = std::to_string(nums[0]) + "/("; for (int i = 1; i < static_cast(nums.size()); ++i) { if (i > 1) result += "/"; result += std::to_string(nums[i]); } result += ")"; return result; } }; 代码分析 -------- 括号内保持从左到右的除法结合,整个后缀成为分母的最小可行值;正数条件保证反转后每个后续因子都只会增大结果。长度 1、2 的表达式不需要括号,构造时间复杂度为 ``O(n)``,额外空间为输出长度。