从数字数组中找到3的最大倍数-在C ++中设置2

假设我们有一个由不同数字组成的数组;我们必须找到可以通过以任意顺序连接该数组中的某些给定数字来生成的3的最大倍数。答案可能非常大,因此将其设置为字符串。如果没有答案,请返回一个空字符串。

因此,如果输入类似于[7,2,8],则输出将为87。

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

  • 定义一个2D数组d,将有三行

  • 对数组数字排序

  • 和:= 0

  • 对于初始化i:= 0,当i <数字大小时,更新(将i增加1),执行-

    • x:=数字[i]

    • 在d [x mod 3]的末尾插入digits [i]

    • 总和:=总和x

    • sum:= sum mod 3

  • 如果sum不为零,则-

    • 从d [sum]中删除最后一个元素

    • 雷姆:= 3-总和

    • 如果d [rem]的大小<2,则-

    • 两次删除d [rem]中的最后一个元素

    • 返回空字符串

    • 如果不是d [sum]的大小,则-

    • 除此以外

    • ret:=空字符串

    • 对于初始化i:= 0,当i <3时,更新(将i增加1),执行-

      • ret:= ret将d [i,j]连接为字符串

      • 对于初始化j:= 0,当j <d [i]的大小时,更新(将j增加1),执行-

    • 排序数组ret

    • 如果ret和ret [0]的大小等于“ 0”,则-

      • 返回“ 0”

    • 返回ret

    例 

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

    #include <bits/stdc++.h>
    using namespace std;
    class Solution {
    public:
       string largestMultipleOfThree(vector<int>& digits) {
          vector<vector<int>> d(3);
          sort(digits.begin(), digits.end(), greater<int>());
          int sum = 0;
          for (int i = 0; i < digits.size(); i++) {
             int x = digits[i];
             d[x % 3].push_back(digits[i]);
             sum += x;
             sum %= 3;
          }
          if (sum) {
             if (!d[sum].size()) {
                int rem = 3 - sum;
                if (d[rem].size() < 2)
                   return "";
                d[rem].pop_back();
                d[rem].pop_back();
             }
             else {
                d[sum].pop_back();
             }
          }
          string ret = "";
          for (int i = 0; i < 3; i++) {
             for (int j = 0; j < d[i].size(); j++) {
                ret += to_string(d[i][j]);
             }
          }
          sort(ret.begin(), ret.end(), greater<int>());
          if (ret.size() && ret[0] == '0')
             return "0";
          return ret;
       }
    };
    main(){
       Solution ob;
       vector<int> v = {7,2,8};
       cout << (ob.largestMultipleOfThree(v));
    }

    输入值

    {7,2,8}

    输出结果

    87
    猜你喜欢