异或问题

作者: 培根好吃 | 来源:发表于2018-08-31 11:20 被阅读0次

异或问题
Tensorflow 实现异或（XOR）问题
异或
异或
异或
异或
异或
异或
存或所异，异或所存…
与，或，异或

异或的作用：0+1=1 ，0+0=0或者1+1=0
输入描述：
第一行一个数字n
第二行n个数字

输出描述：
输出最多的区间的个数

示例：
输入
3 0 2 2

输出
2
思路：因为每两个数之间异或的值我们无法判断，所以采用一个思想：我先给定一个值（’存入set集合。其他集合都行）然后将它与后一个数异或（’存入set集合），再将值与后一位数异或（’存入set集合），以此类推，直到某一个结果与之前的值相等，那么此时count加一。只要中间有值异或为0，那么就肯定会有后来的值等于之前的值。

public class Solution4 {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int res=0;
        int i=0;
        int count=0;
        Set<Integer> mSet=new HashSet<>();
        mSet.add(res);
        while(i<n) {
            res=res^(sc.nextInt());
            if(mSet.contains(res)) {
                count++;
                mSet.clear();
            }
            mSet.add(res);
            i++;
        }
        System.out.println(count);
    }
}

题目描述:给定整数m以及n个数字A1, A2, …, An，将数列A中所有元素两两异或，共能得到n(n-1)/2个结果。
请求出这些结果中大于m的有多少个。
输入:第一行包含两个整数n, m。
第二行给出n个整数A1, A2, …, An。
样例输入:3 10
6 5 10
输出:输出仅包括一行，即所求的答案。
样例输出:2

异或那道题可以把每个数的二进制位求出来，用一个字典树维护，然后遍历每一个数按位贪心，比如这一位m是1，遍历的这个数这一位是0，那么和他异或的数就必须是1，如果这一位m是0，要大于m的话异或和的这一位可以是1也可以是零，ans加上之前维护的二进制位加上使这一位为1的数在字典树中查询有多少个数满足这个前缀的条件，然后在令这一位的异或和为0，继续向下遍历，最后的答案除以2。

image.png

import java.util.Scanner;
 
public class Q2_异或 {
    public static void main(String[] args) {
        trieNode root = new trieNode(-1);//根节点不存有效值
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] items = new int[n];
        for(int i=0; i<n; i++){
            items[i] = sc.nextInt();
            insert(root, items[i]);
        }
        long result = 0;
        for(int num : items){
            result  += query(root, num, m, 31);//31到0是整数能表示的范围
        }
        System.out.println(result/2);
    }
 
    /**
     * 将number加入到root中
     * @param root
     * @param number
     */
    public static void insert(trieNode root, int number){
        trieNode current = root;
        for(int i=31; i>=0; i--){//先存放高位数字比如数字5，二进制为0101，则存放顺序是0,1,0,1
            //求解对应第i位置处二进制数字是0还是1
            int digit = (number>>i)&1;
            if(current.next[digit]==null){
                current.next[digit] = new trieNode(digit);
            }
            current = current.next[digit];
            current.count++;
        }
    }
    
    /**
     * @param root//trieTree树
     * @param a//a是做异或运算的其中的一个值
     * @param m//和异或结果进行比较的数字，大于m记录值加1
     * @param k//number转换为二进制后对应的第k位置上的数字
     * @return
     */
    public static int query(trieNode root, int a, int m, int k){
        if(root == null){
            return 0;
        }
        trieNode current = root;
        for(int i=k; i>=0; i--){
            int aDigit = (a>>i)&1;
            int mDigit = (m>>i)&1;
            if(aDigit == 1 && mDigit == 1){
                if(current.next[0] == null){//对应k位置处的数字若为空，则返回0
                    return 0;
                }else{
                    current = current.next[0];//返回第k位置为0的数字的个数
                }
            }else if(aDigit == 0 && mDigit ==1){
                if(current.next[1] == null){
                    return 0;
                }else {
                    current = current.next[1];
                }
            }else if(aDigit == 0 && mDigit == 0){
                int p = query(current.next[0], a, m, i-1);
                int q = (current.next[1]==null?0:current.next[1].count);
                return p+q;
            }else if(aDigit == 1 && mDigit == 0){
                int p = query(current.next[1], a, m, i-1);
                int q = (current.next[0]==null?0:current.next[0].count);
                return p+q;
            }
        }       
        return 0;
    }   
}
 
//存放所有数字的二进制的形式的trie树
class trieNode{
    trieNode[] next = new trieNode[2];//存放孩子结点，只有0和1两种数字
    int count = 0;//此处包含的数字0或1的个数
    int digit = 0;
    public trieNode(int digit) {
        this.digit = digit;
    }
}