数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究在 C++ 中查找 k 个 2 的幂，其和为 N
假设我们有两个数字 N 和 K。任务是打印 K 个数字，这些数字是 2 的幂，并且它们的和为 N。如果不可能，则返回 -1。假设 N = 9 且 K = 4，则输出将为 4 2 2 1，其和为 9，元素数量为 4，并且每个元素都是 2 的幂。
我们必须遵循以下步骤来解决此问题：
如果 k 小于 N 中设置位的数量或大于 N，则返回 -1
将设置位处的 2 的幂添加到优先级队列中
初始化优先级队列，直到我们获得 K 个元素，然后从优先级队列中删除元素
将删除的元素/2 再次插入优先级队列两次
如果达到 k 个元素，则打印它们。
示例
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
void displayKnumbers(int n, int k) {
int set_bit_count = __builtin_popcount(n);
if (k < set_bit_count || k > n) {
cout << "-1";
return;
}
priority_queue<int> queue;
int two = 1;
while (n) {
if (n & 1) {
queue.push(two);
}
two = two * 2;
n = n >> 1;
}
while (queue.size() < k) {
int element = queue.top();
queue.pop();
queue.push(element / 2);
queue.push(element / 2);
}
int ind = 0;
while (ind < k) {
cout << queue.top() << " ";
queue.pop();
ind++;
}
}
int main() {
int n = 30, k = 5;
cout << "Numbers are: ";
displayKnumbers(n, k);
}输出
Numbers are: 8 8 8 4 2
更新于： 2019年12月19日
139 次浏览
广告