C++での3の最大の倍数

数字の配列が1つあるとすると、指定された数字の一部を任意の順序で連結することで形成できる3の最大の倍数を見つける必要があります。答えは非常に大きいかもしれないので、文字列として作成してください。答えがない場合は、空の文字列を返します。

したがって、入力が[7,2,8]の場合、出力は87

これを解決するには、次の手順に従います-

• 1つの2D配列dを定義します。3つの行があります

• 配列の数字を並べ替える

• 合計：=0

• 初期化i：=0の場合、i <桁のサイズの場合、更新（iを1増やします）、do-

  • x：=桁[i]

  • d [x mod 3]

    の最後に数字[i]を挿入します

  • 合計：=合計+ x

  • sum：=sum mod 3

• 合計がゼロ以外の場合、-

  • d [sum]のサイズでない場合、-

    • rem：=3-合計

    • d [rem] <2のサイズの場合、-

      • 空の文字列を返す

    • d[rem]から最後の要素を2回削除する

  • それ以外の場合

    • d [sum]

      から最後の要素を削除します

• ret：=空の文字列

• 初期化i：=0の場合、i <3の場合、更新（iを1増やします）、実行-

  • 初期化j：=0の場合、j

    • ret：=ret concatenate d [i、j] as string

• 配列を並べ替えます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