数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究从数字数组中查找 3 的最大倍数 - C++ 中的 Set 2
假设我们有一个包含不同数字的数组；我们必须找到通过以任何顺序连接该数组中某些给定数字生成的 3 的最大倍数。答案可能非常大，因此将其作为字符串。如果没有答案，则返回空字符串。
因此，如果输入类似于 [7, 2, 8]，则输出将为 87。
为了解决这个问题，我们将遵循以下步骤 -
定义一个二维数组 d，将有三行
对数组数字进行排序
sum := 0
对于初始化 i := 0，当 i < 数字大小，更新（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 的大小和 ret[0] 与 '0' 相同，则 -
返回 "0"
返回 ret
示例
让我们看看以下实现以更好地理解 -
#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
更新于: 20-Aug-2020
117 次查看
广告