資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中求按位或等於 k 的最大子集
問題陳述
給定一個非負整數陣列和一個整數 k，找到按位或等於 k 的最大長度子集。
示例
If given input array is = [1, 4, 2] and k = 3 then output is: [1, 2] The bitwise OR of 1 and 2 equals 3. It is not possible to obtain a subset of length greater than 2.
演算法
以下是按位或的屬性：
0 OR 0 = 0 1 OR 0 = 1 1 OR 1 = 1
對於 k 的二進位制表示中所有位等於 0 的位置，結果子集中所有元素的二進位制表示中對應的位置也必須為 0。
另一方面，對於 k 中位等於 1 的位置，必須至少有一個元素在對應位置上為 1。其餘元素在該位置可以是 0 或 1，這並不重要。
因此，為了獲得結果子集，遍歷初始陣列。在決定元素是否應該包含在結果子集中時，檢查 k 的二進位制表示中是否存在任何位置為 0 且該元素對應位置為 1 的情況。如果存在這樣的位置，則忽略該元素，否則將其包含在結果子集中。
如何確定 k 的二進位制表示中是否存在某個位置為 0 且某個元素對應位置為 1 的情況？只需取 k 和該元素的按位或。如果它不等於 k，則存在這樣的位置，並且必須忽略該元素。如果它們的按位或等於 k，則將當前元素包含在結果子集中。
最後一步是確定是否存在至少一個元素在 k 對應位置為 1 的位置上為 1。
只需計算結果子集的按位或。如果它等於 k，則這是最終答案。否則，不存在滿足條件的子集。
示例
#include <bits/stdc++.h>
using namespace std;
void getSubSet(int *arr, int n, int k){
vector<int> v;
for (int i = 0; i < n; i++) {
if ((arr[i] | k) == k)
v.push_back(arr[i]);
}
int ans = 0;
for (int i = 0; i < v.size(); i++) {
ans |= v[i];
}
if (ans != k) {
cout << "Subset does not exist" << endl;
return;
}
cout << "Result = ";
for (int i = 0; i < v.size(); i++) {
cout << v[i] << " ";
}
cout << endl;
}
int main(){
int arr[] = { 1, 4, 2 };
int k = 3;
int n = sizeof(arr) / sizeof(arr[0]);
getSubSet(arr, n, k);
return 0;
}輸出
編譯並執行上述程式時，會生成以下輸出：
Result = 1 2
更新於： 2020-02-27
386 次檢視
廣告