Bộ ba lớn nhất trong C ++

Giả sử chúng ta có một mảng các chữ số, chúng ta phải tìm bội số lớn nhất của ba chữ số có thể được tạo thành bằng cách ghép một số chữ số đã cho theo thứ tự bất kỳ như chúng ta muốn. Câu trả lời có thể rất lớn vì vậy hãy làm cho nó ở dạng chuỗi. Nếu không có câu trả lời, trả về một chuỗi trống.

Vì vậy, nếu đầu vào là [7,2,8], thì đầu ra sẽ là 87

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Xác định một mảng 2D d, sẽ có ba hàng
sắp xếp các chữ số mảng
tổng:=0
để khởi tạo i:=0, khi i
- x:=chữ số [i]
- chèn chữ số [i] vào cuối d [x mod 3]
- sum:=sum + x
- sum:=sum mod 3
nếu tổng khác 0, thì -
- nếu không phải là kích thước của d [sum], thì -
  - rem:=3 - sum
  - nếu kích thước của d [rem] <2, thì -
    - trả về chuỗi trống
  - xóa phần tử cuối cùng khỏi d [rem] hai lần
- Nếu không
  - xóa phần tử cuối cùng khỏi d [sum]
ret:=chuỗi trống
để khởi tạo i:=0, khi i <3, hãy cập nhật (tăng i lên 1), thực hiện -
- để khởi tạo j:=0, khi j
  - ret:=ret nối d [i, j] dưới dạng chuỗi
sắp xếp lại mảng
nếu kích thước của ret và ret [0] giống như '0' thì -
- trả về "0"
trả về "0"

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

{7,2,8}

Bộ ba lớn nhất trong C ++

Ví dụ

Đầu vào

Đầu ra