蓝桥算法，每天一道

一、位运算的奇巧淫技

先来学习一下位运算

&（与），|（或），^(异或)，~(非/取反)

>>和<<运算符将二进制进行右移或者左移操作

>>>运算符将用0填充高位；>>运算符用符号位填充高位，没有<<<运算符

对于int型，1<<35与1<<3是相同的(int型只有32位)，而左变的操作数是long型时需对右侧操作数模64

一些技巧：
（1）、与：都为1结果为1， 或：有一个为1结果为1， 异或：相同为0、不同为1
（2）、x&1=1 x为奇 ；x&1=0 x为偶 （二进制最低位）

1、唯一成对的数

题目：找出唯一成对的数，1-1000这1000个数放在含有1001个元素的数组中，只有唯一的一个元素值重复，其他均只出现一次。每个数组元素只能访问一次，设计一个算法，将其找出。要求：不用辅助存储空间。

如：int[] ={1,2,3,4,5,3} ---->3

我的思路：我也是第一次开始练算法，拿到题还是一脸懵逼，于是如上面所示，先想着是就6个数吧，也别多了，不然绕不清楚。题目显示不让用辅助存储空间，意思就是我不可以在开辟另一个数组，于是就更陷入沉思了。怎么想怎么和位运算没啥子联系，只是想到最暴力的方法，（以上面那个小数组为例子）2与1比较，不等，把1扔到外面放入单独一个盒子；3与2比较，不等，把2扔到外面放入单独一个盒子；以此类推，直到3和5比较，也不等，扔出去时候发现之前有个3与之相等，便匹配在一起。再深入想了一下，我头尾相比，来个69比较法（独创秘方，直通幼儿园）？好像变得快了一些，尾部不变，从头开始，1与3比较，不等out；2与3比较，不等out，三下出来了答案。但是题目1000个数字，不可能如此侥幸吧，该怎么处理呢，于是乎还是看了视频讲解。

讲解思路：我们想的是把不重复的数消掉，but--->A^A=0,B^0=B --->A^A^B^C^C=B--->消除重复，我们该如何处理呢？看个式子（1^2^k^.....^k^1000）^（1^2^...^1000），卧槽顿时恍然大悟，在（1^2^...^1000）取不重复的排法，那么其中必有一个k值，那么根据异或属性，相同为0、不同为1，3个k异或最后只剩下一个k，输出即可。

public class Solution{

public static void main(String[] args) {
    //首先创建数组，遍历
    int n = 1001;
    int[] arr = new int[n];
    for(int i=0;i<arr.length;i++) {
        arr[i] = i+1;
    }
    //在这里，最后一个数字我们给它随机数k，因为这里只有唯一一个重复
    arr[arr.length-1] = new Random().nextInt(n-1)+1;
    //随机下标
    int index = new Random().nextInt(n);
    //涉及两个方法，需自定义
    swap(arr,index,arr.length-1);
    print(arr);
    int x = 0;
    for(int i=1;i<n-1;i++){
        x = x^i;
    }
    for(int i=0;i<n;i++) {
        x= x^arr[i];
    }
    System.out.println(x)
}

public static void swap(int[] arr,int i,int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
 
public static void print(int[] arr) {
    System.out.println(Arrays.toString(arr))
}    
    
}

蓝桥算法，每天一道

原文：https://www.cnblogs.com/wangzheming35/p/11892558.html