数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中最接近 K 的子数组的按位与
在这个问题中，我们给定一个大小为 n 的数组 arr[] 和一个整数 k。我们的任务是从索引 i 到 j 找到子数组，并计算其所有元素的按位与。然后打印 |K-（子数组的按位与）| 的最小值。
让我们来看一个例子来理解这个问题：
输入 − arr[] = {5, 1}, k = 2
输出 −
解决这个问题，可以有几种方法。
一个简单的解决方案是使用直接方法。通过找到所有子数组的按位与，然后找到 |K-X|。
步骤 1 − 查找所有子数组的按位与。
步骤 2 − 对于从步骤 1 中找到的每个值（例如 X）。找到 |k - X| 的值。
步骤 3 − 将上面在 min 变量中找到的最小值存储起来。
步骤 4 − 最后，打印 min。
示例
程序说明了我们解决方案的工作原理：
#include <iostream>
using namespace std;
int CalcBitwiseANDClosestK(int arr[], int n, int k){
int minimum = 1000;
for (int i = 0; i < n; i++) {
int X = arr[i];
for (int j = i; j < n; j++) {
X &= arr[j];
minimum = min(minimum, abs(k - X));
}
}
return minimum;
}
int main() {
int arr[] = { 1, 6 , 4, 9, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 5;
cout<<"Minimum value difference between Bitwise AND of sub-array and K is "<<CalcBitwiseANDClosestK(arr, n, k);
return 0;
}输出
Minimum value difference between Bitwise AND of sub-array and K is 1
另一个解决方案可能是观察子数组中的 AND 运算。按位与有一个特性，它永远不会增加。所以，我们必须检查最小差值，当 X ≤ K 时，最小差值会增加。
示例
#include <iostream>
using namespace std;
int CalcBitwiseANDClosestK(int arr[], int n, int k){
int minimum = 1000000;
for (int i = 0; i < n; i++) {
int BitwiseAND = arr[i];
for (int j = i; j < n; j++) {
BitwiseAND &= arr[j];
minimum = min(minimum, abs(k - BitwiseAND));
if (BitwiseAND <= k)
break;
}
}
return minimum;
}
int main() {
int arr[] = {1, 6 , 4, 9, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 5;
cout<<"Minimum value difference between Bitwise AND of sub-array and K is "<<CalcBitwiseANDClosestK(arr, n, k);
return 0;
}输出
Minimum value difference between Bitwise AND of sub-array and K is 1
更新于：2020年8月5日
1K+ 浏览量
广告