algorithm - 集合的每个子集的最小和最大元素的 OR 和
问题描述
给定一个集合 S,对于它的每个非空子集,找到最小和最大元素并取它们的逻辑 OR。在所有这些子集中找到这些 OR 的总和。
例如:S = {1, 2, 3},然后是子集
{1} 最小=1 最大=1 OR=1
{2} 最小=2 最大=2 OR=2
{3} 最小=3 最大=3 OR=3
{1, 2} 最小=1 最大=2 OR=3
{2, 3} 最小=2 最大=3 OR=3
{1, 3} 最小=1 最大=3 OR=3
{1, 2, 3} 最小=1 最大=3 OR=3
答案是 18。
我已阅读如何找到数组所有可能子集的最大值和最小值的差之和,但无法在此处使用该逻辑。
解决方案
算法
- 对输入数据进行排序
- 循环
i = 0 to n
其中 n 是输入的长度,并且j = i to n
,由于输入已排序input[i]
将是最小的并且input[j]
将是范围内的最大[i,j]
- 现在我们知道它
input[i]
是最小input[j]
的和最大的,我们也知道j - i -1
数组的中间元素的组合将产生相同的最小值和最大值,因此我们OR
将低和高的值与可能的排列总数相乘用这些中间数字。 - 例如。对于
input = [1, 2, 3, 4]
andi = 0
和j = 3
ie)lowest = 1
,largest = 4
我们知道元素[2, 3]
可以出现在子集中,而不会改变最小值和最大值。[1, 2, 4], [1, 3, 4], [1, 2, 3, 4]
都是有效的。与中间元素可能的组合数是2 ^ (count of middle elements)
。 - 对所有最小和最大对重复此操作。
这是 C++ 中的代码。
#include <iostream>
int main() {
vector<int> input {3, 2, 1};
sort(input.begin(), input.end());
int answer = 0;
for(int i=0; i < input.size(); ++i)
{
for(int j=i; j < input.size(); ++j)
{
int elements = (j - i) - 1;
int multiple = elements > 0 ? pow(2, elements) : 1;
answer += ((input[i] | input[j]) * multiple);
cout << input[i] << ' ' << input[j] << ' ' << answer << endl;
}
cout << endl;
}
cout << answer <<endl;
}
推荐阅读
- excel - 如何创建具有可变条件/条件的循环?
- github-pages - 如何在呈现的 Github 页面 README.md 上生成目录 (ToC)?
- python - BeautifulSoup 没有拉动页面上的所有元素
- r - 增加ggplot上轴线和绘图线之间的距离
- php - 如何从 PHP 脚本运行 Nodejs 服务器?
- typescript - 打字稿:递增数字类型
- c# - C# 将十六进制字符串转换为十进制。为什么是负值?
- javascript - 在 JS 迭代器的 next() 方法中访问“this”?
- opencv - 自动对焦后如何关联检测到的关键点
- javascript - React JS _TypeError: _This.dropdowncounter 不是一个函数