資料結構
網路
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 次檢視
廣告