Нахождение двух элементов, XOR которых является максимальным
Я сталкиваюсь с проблемой, которая требует, чтобы я нашел элемент из данного массива целых чисел, XOR которого является максимальным с данным числом.
Пример :
A [] = {2,7,3,6};
Число = 4.
Теперь 2 ^ 4 = 6, 7 ^ 4 = 3, 3 ^ 4 = 7, 6 ^ 3 = 2. Следовательно, 3 должно быть ответом, так как 3 ^ 7 — максимум.
Я пытаюсь следовать структуре, подобной tree, и продолжаю находить максимально возможный результат побитно, то есть начиная с MSB, если мой бит равен 1, то я иду вниз по стороне 0, а если мой бит равен 0, то я пересекаю вниз по 1 стороне узла. Я придумал следующий код.
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
#include<list>
#include<queue>
#include<cstdlib>
#include<numeric>
#include<set>
#include<map>
#include<deque>
#include<climits>
#include<cassert>
#include<cctype>
#include<ctime>
#include<iterator>
#include<iomanip>
#include<functional>
#include<fstream>
#include<ostream>
#include<istream>
#include<sstream>
using namespace std;
#define sf(n) scanf("%d",&n)
#define pf(n) printf("%d",n)
#define pfln(n) printf("%d\n",n)
#define vi vector <int >
#define pb push_back()
#define debug(n) printf("n = %d\n",n)
#define PI 3.14159265358979
#define LL 1000000007
int ans[32];
class TrieNode{
public:
int bit;
bool end;
TrieNode *child[2];
TrieNode(int val){
this->bit = val;
this->end = false;
this->child[0] = NULL;
this->child[1] = NULL;
}
};
void addWord(TrieNode *node,int n){
int a[32];
int bin[32];
int m = n;
int j = 0;
//cout<<"in adding\n";
while(m>0){
a[j++] = m%2;
m/=2;
}
for(int i = j-1,k=0 ; i>=0 ; k++,i-- ){
bin[32-i-1] = a[i];
}
for(int i = 0 ; i < 32-j ; i++){
bin[i] = 0;
}
for(int i = 0 ; i < 32 ; i++)
cout<<bin[i];
for(int i = 0 ; i < 32 ; i++){
if(node->child[bin[i]] == NULL){
TrieNode *tmp = new TrieNode(bin[i]);
node->child[bin[i]] = tmp;
node = node->child[bin[i]];
}
else{
node = node->child[bin[i]];
}
}
node->end = true;
}
void findmax(TrieNode *node, int q){
int a[32];int j = 0;
int bin[32];
while(q>0){
a[j++] = q%2;
q/=2;
}
for(int i = j-1,k=0 ; i>=0 ; k++,i-- ){
bin[32-i] = a[i];
}
for(int i = 0 ; i < 32-j ; i++){
bin[i] = 0;
}
for(int i = 0 ; i < 32 ; i++){
if(node->child[0]->bit == bin[i] && node->child[1]!=NULL){
ans[i] = node->child[1]->bit;
node = node->child[1];
}
else if(node->child[1]->bit == bin[i] && node->child[0]!=NULL){
ans[i] = node->child[0]->bit;
node = node->child[0];
}
else{
ans[i] = node->child[0] == NULL?node->child[1]->bit:node->child[0]->bit;
node = node->child[0] == NULL?node->child[1]:node->child[0];
}
}
}
int main()
{
std::ios_base::sync_with_stdio(false);
TrieNode *root = new TrieNode(-1);
addWord(root,2);
addWord(root,7);
addWord(root,3);
addWord(root,6);
findmax(root,4);
for(int i = 0 ; i < 32 ; i++){
cout<<ans[i];
}
return 0;
}
Но я продолжаю получать ошибку сегментации и не могу запустить программу. Я испробовал каждый трюк для отладки кода, но не могу понять проблему.
Пожалуйста, помогите найти причину ошибки во время выполнения.
Спасибо
Решение
Допустим, вам нужно было найти максимум в массиве. Вы бы сделали что-то вроде этого:
int A[] = {2,7,3,6};
int maximum = std::numeric_limits<int>::min();
for(int i = 0; i < 4; ++i)
if(A[i] > maximum) maximum = A[i];
Что вам нужно сделать, это заменить условие.
for(int i = 0; i < 4; ++i)
if(func(A[i]) > maximum) maximum = A[i];
куда func() это функция, которая может выглядеть так:
int func(int x)
{
return x ^ 4;
}
Конечно, это фиктивная реализация, например, вы можете передать 4 в качестве параметра, но я надеюсь, что вы поняли идею.
С другой стороны, вы могли бы использовать std::max_element() сделать это:
int A[] = {2,7,3,6};
int maximum = std::max_element(std::begin(A), std::end(A), [](int const a, int const b){return func(a) < predicate(b)});
(где func() та же самая функция, показанная выше.)
Другие решения
Других решений пока нет …