資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
廣告