数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中两个二进制数组的最小翻转次数，使其异或结果等于另一个数组。
问题陈述
给定三个大小为 n 的包含 0 和 1 的数组，任务是找到第一个和第二个数组中比特的最小翻转次数，使得第一个和第二个数组第 i 个索引处的比特的异或结果等于第三个数组第 i 个索引处的比特。
请注意，我们最多只能翻转数组 1 的 p 个比特，最多只能翻转数组 2 的 q 个比特。此外，不允许重新排列数组元素。
假设 p = 2 且 q = 5
arr1[] = {1, 0, 1, 1, 0, 1, 0}
arr2[] = {0, 1, 0, 1, 0, 0, 1}
arr3[] = {0, 1, 1, 0, 0, 0, 0}- (arr1[0] ^ arr2[0]) 即 (1 ^ 0) = 1，这与 arr3[0] 不相等。因此需要翻转。
(arr1[1] ^ arr2[1]) 即 (0 ^ 1) = 1，这与 arr3[1] 相等。因此不需要翻转。
(arr1[2] ^ arr2[2]) 即 (1 ^ 0) = 1，这与 arr3[2] 相等。因此不需要翻转。
(arr1[3] ^ arr2[3]) 即 (1 ^ 1) = 0，这与 arr3[3] 相等。因此不需要翻转。
(arr1[4] ^ arr2[4]) 即 (0 ^ 0) = 0，这与 arr3[4] 相等。因此不需要翻转。
(arr1[5] ^ arr2[5]) 即 (1 ^ 0) = 1，这与 arr3[5] 不相等。因此需要翻转。
(arr1[6] ^ arr2[6]) 即 (0 ^ 1) = 1，这与 arr3[6] 不相等。因此需要翻转。
算法
1. If (arr1[i] ^ arr2[i]) == arr3[i] then continue as flip is not required. 2. If (arr1[i] ^ arr2[i]) != arr3[i] then flip is required. a. If arr3[i] == 0 then one of the following condition is true: i. (arr1[i] == 0) and (arr2[i] == 0) OR ii. (arr1[i] == 1) and (arr2[i] == 1) b. If arr3[i] == 1 then one of the following condition is true: i. (arr1[i] == 0) and (arr2[0] == 1) OR ii. (arr1[i] == 1) and (arr2[i] == 0) 3. If flip is required then we can either flip arr1[i] or arr2[i]. Hence we can conclude that number of flips required to make XOR of arr1 and arr2 equal to arr3 should be less than or equal to p + q.
示例
#include <iostream>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
int getRequiredFlips(int *arr1, int *arr2, int *arr3, int n, int p, int q){
int flips = 0;
for (int i = 0; i < n; ++i) {
if ((arr1[i] ^ arr2[i]) != arr3[i]) {
++flips;
}
}
return flips <= (p + q) ? flips : -1;
}
int main(){
int arr1[] = {1, 0, 1, 1, 0, 1, 0};
int arr2[] = {0, 1, 0, 1, 0, 0, 1};
int arr3[] = {0, 1, 1, 0, 0, 0, 0};
int size = SIZE(arr1);
cout << "Flips required: " << getRequiredFlips(arr1, arr2, arr3, size, 2, 5) << "\n";
return 0;
}输出
编译并执行上述程序时，它会生成以下输出：
Flips required: 3
更新于: 2019年9月23日
143 次查看
广告