0

我面临一个问题，需要我从给定的整数数组中找到一个元素，该数组的 XOR 与给定的数字是最大的。

例子 ：

A[] = {2,7,3,6}; 数字 = 4。

现在，2^4 = 6、7^4 = 3、3^4 = 7、6^3 = 2。因此，3 应该是答案，因为 3^7 是最大值。

我正在尝试遵循类似 trie 的结构并继续逐位查找可能的最大结果，即从 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;
 }

但是我不断遇到分段错误并且无法运行该程序。我已经尝试了所有技巧来调试代码，但我无法找出问题所在。请帮助找出运行时错误的原因。

谢谢

4

1 回答 1

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()上面显示的相同功能在哪里。）

于 2015-10-19T21:40:29.453 回答