資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中透過新增具有相同設定位數的數字來獲取最大和
問題陳述
給定一個包含 N 個數字的陣列，任務是找到透過新增具有相同設定位數的數字可以獲得的最大和。
示例
如果輸入陣列為 {2, 5, 8, 9, 10, 7}，則輸出為 14 -
2 的設定位數為 1
5 的設定位數為 2
8 的設定位數為 1
9 的設定位數為 2
10 的設定位數為 2
7 的設定位數為 3
然後 (5 + 9 + 10) 的和為 24，其設定位數 = 2
演算法
遍歷陣列並計算每個元素的設定位數。
初始化一個 32 位陣列，假設數字最多有 32 個設定位。
迭代陣列並將陣列元素新增到指示設定位數的位置。
遍歷並找到最大和並返回它。
示例
#include <bits/stdc++.h>
using namespace std;
int bitCount(int n){
int count = 0;
while (n) {
count++;
n = n & (n - 1);
}
return count;
}
int maxSum(int arr[], int n){
int bits[n];
for (int i = 0; i < n; i++) {
bits[i] = bitCount(arr[i]);
}
int sum[32] = { 0 };
for (int i = 0; i < n; i++) {
sum[bits[i]] += arr[i];
}
int maximum = 0;
for (int i = 0; i < 32; i++) {
maximum = max(sum[i], maximum);
}
return maximum;
}
int main(){
int arr[] = {2, 5, 8, 9, 10, 7};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum sum = " << maxSum(arr, n) << endl;
return 0;
}輸出
編譯並執行上述程式時，它會生成以下輸出 -
Maximum sum = 24
更新於: 2020年1月30日
240 次檢視
廣告