数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中最大的三的倍数
假设我们有一个数字数组，我们需要找到通过以任何我们想要的顺序连接一些给定数字而可以形成的最大三的倍数。答案可能非常大，所以将其作为字符串。如果没有答案，则返回空字符串。
因此，如果输入类似于 [7, 2, 8]，则输出将为 87
为了解决这个问题，我们将遵循以下步骤 -
定义一个二维数组 d，将有三行
对数组 digits 进行排序
sum := 0
初始化 i := 0，当 i < digits 的大小，更新 (i 加 1)，执行 -
x := digits[i]
将 digits[i] 插入到 d[x mod 3] 的末尾
sum := sum + x
sum := sum mod 3
如果 sum 不为零，则 -
如果 d[sum] 的大小不为 0，则 -
rem := 3 - sum
如果 d[rem] 的大小 < 2，则 -
返回空字符串
从 d[rem] 中删除最后一个元素两次
否则
从 d[sum] 中删除最后一个元素
ret := 空字符串
初始化 i := 0，当 i < 3，更新 (i 加 1)，执行 -
初始化 j := 0，当 j < d[i] 的大小，更新 (j 加 1)，执行 -
ret := ret 连接 d[i, j] 作为字符串
对数组 ret 进行排序
如果 ret 的大小不为 0 且 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
更新于: 2020-06-09
111 次查看
广告