C ++中最大的三倍数

假设我们有一个数字数组，我们必须找到三个整数的最大倍数，这些数字可以通过将任意给定数字以任意顺序串联而形成。答案可能非常大，因此将其设置为字符串。如果没有答案，请返回一个空字符串。

因此，如果输入类似于[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”

• 返回“ 0”

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

示例

#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