跳转至

1363.largest-multiple-of-three

Statement

Metadata

给你一个整数数组 digits，你可以通过按任意顺序连接其中某些数字来形成 3 的倍数，请你返回所能得到的最大的 3 的倍数。

由于答案可能不在整数数据类型范围内，请以字符串形式返回答案。

如果无法得到答案，请返回一个空字符串。

 

示例 1：

输入：digits = [8,1,9]
输出："981"

示例 2：

输入：digits = [8,6,7,1,0]
输出："8760"

示例 3：

输入：digits = [1]
输出：""

示例 4：

输入：digits = [0,0,0,0,0,0]
输出："0"

 

提示：

  • 1 <= digits.length <= 10^4
  • 0 <= digits[i] <= 9
  • 返回的结果不应包含不必要的前导零。

Metadata

Given an array of digits digits, return the largest multiple of three that can be formed by concatenating some of the given digits in any order. If there is no answer return an empty string.

Since the answer may not fit in an integer data type, return the answer as a string. Note that the returning answer must not contain unnecessary leading zeros.

 

Example 1:

Input: digits = [8,1,9]
Output: "981"

Example 2:

Input: digits = [8,6,7,1,0]
Output: "8760"

Example 3:

Input: digits = [1]
Output: ""

 

Constraints:

  • 1 <= digits.length <= 104
  • 0 <= digits[i] <= 9

Solution

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const ll mod = 1e9 + 7;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
    return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
    return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif
// head

class Solution {
public:
    string largestMultipleOfThree(vector<int> &digits) {
        auto f = vector<vector<int>>(3, vector<int>());
        for (auto &d : digits) {
            f[d % 3].push_back(d);
        }

        for (int i = 0; i < 3; i++) {
            sort(all(f[i]), greater<int>());
        }

        {
            int x = f[1].size();
            int y = f[2].size();
            int tot = (x + y * 2) % 3;

            if (tot == 1) {
                if (x) {
                    f[1].pop_back();

                } else {
                    f[2].pop_back();
                    f[2].pop_back();
                }
            }

            if (tot == 2) {
                if (y) {
                    f[2].pop_back();
                } else {
                    f[1].pop_back();
                    f[1].pop_back();
                }
            }
        }

        auto ff = vector<int>();
        for (int i = 0; i < 3; i++) {
            ff.insert(ff.begin(), all(f[i]));
        }

        sort(all(ff), greater<int>());

        string res = "";

        for (auto &a : ff) {
            res += to_string(a);
        }

        if (res == "") {
            return res;
        }

        int zero = 0;
        for (auto &c : res) {
            if (c == '0') {
                ++zero;
            } else {
                break;
            }
        }

        if (zero == res.size()) {
            return res.substr(zero - 1);
        }

        return res.substr(zero);
    }
};

#ifdef LOCAL

int main() {
    return 0;
}

#endif
最后更新: October 11, 2023
回到页面顶部