C++ 中的最佳划分


假设我们有一个正整数列表;相邻的整数将执行浮点除法。例如,[2,3,4] -> 2 / 3 / 4。现在,我们可以在任何位置添加任意数量的括号来更改这些操作的优先级。我们应该找出如何添加括号以获得最大结果,我们必须找到字符串格式的对应表达式。我们的表达式不应该包含冗余的括号。因此,如果输入类似于 [1000,100,10,2],则结果将为“1000/(100/10/2)”。

为了解决这个问题,我们将遵循以下步骤:

  • n := nums 数组的大小
  • 如果 n 为 0,则返回一个空字符串。
  • num := nums[0] 作为字符串
  • 如果 n 为 1,则返回 num
  • 如果 n 为 2,则返回 num 连接 /,连接 nums[1] 作为字符串
  • den := 一个空字符串
  • 对于 i 在范围 1 到 n – 1 内
    • den := den + nums[i] 作为字符串
    • 如果 i 不等于 n – 1,则 den := den 连接 ‘/’
  • 返回 num 连接 / 连接(连接 den ,连接)

让我们看看下面的实现以更好地理解:

示例

 实时演示

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string optimalDivision(vector<int>& nums) {
      int n = nums.size();
      if(n == 0) return "";
      string num = to_string(nums[0]);
      if(n == 1) return num;
      if(n == 2) return num + "/" + to_string(nums[1]);
      string den = "";
      for(int i = 1; i < n; i++){
         den += to_string(nums[i]);
         if(i != n - 1) den += "/";
      }
      return num + "/" + "(" + den + ")";
   }
};
main(){
   vector<int> v = {1000,100,10,2};
   Solution ob;
   cout << (ob.optimalDivision(v));
}

输入

[1000,100,10,2]

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

输出

1000/(100/10/2)

更新于: 2020年5月4日

257 次查看

启动您的 职业生涯

通过完成课程获得认证

开始
广告