算法解题思路

1、异或的作用

参考网站：
https://blog.csdn.net/qq_39705793/article/details/81237005

异或是一种基于二进制计算的方式，对应位上面相同取0，不相同取1；代码中使用^表示
性质：
（1）满足交换律，可以交换运算因子顺序，结果不变
（2）结合律
（3）x^x = 0; x^0 = x;

使用技巧：
（1）交换两个数字
    a = 3;
    b = 4;
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;

（2）判断奇偶数
奇数二进制的最低位一定是1，偶数二进制的最低位一定是0，
所以 a^1 == 1 ? 偶数:奇数

（3）找出那个唯一成对的数
问题：
    1-1000这1000个数放在含有1001个元素的数组中，只有唯一的一个元素值重复，其它均只出现 一次。
每个数组元素只能访问一次，设计一个算法，将它找出来；不用辅助存储空 间，能否设计一个算法实现？
答案：
    将所有的数全部异或(1^2^…^1000^k,k为重复数)，得到的结果与(1^2^3^…^1000)的结果进行异或，得到的结果就是重复数。 
即(1^2^...^1000^k)^(1^2^3^...^1000)，由于有结合律、交换律存在，
我们可以这么调整为(1^1^2^2^...^1000^1000^k)那结果当然就是k了

（4）唯一不成对的数字
直接计算 a ^ b ^ a ^ c ^ c = b 为唯一不成对的数字

（5）任何数和-1做“异或”运算相当于取反

（6）找出数组中落单的两个数
问题：
    一个整型数组里除了两个数字之外，其他的数字都出现了两次。
    请写程序找出这两个只出现一次的数字。
    要求时间复杂度是O(n)，空间复杂度是O(1)。
答案：
    6.1考虑采用分治的思想
    如果我们能将两个落单的数字分开的时候，那么我们就将问题变成了找到一个落单的数字；
    那么我们如何将两个落单的数字分开呢？
    由于两个落单的数字肯定不相同，所以肯定存在在某一个位置（二进制的01）上面不相同，其中一个落单在N位上为0，另外一个落单的数字为1；
    那么我们可以通过在N位上0、1将所有的数字分成两个部分；那么我们就将问题简化为找到一个落单的数字；（通过所有数字的异或就能解决）
    6.2如何找到N位（分治点）
    那两个落单的数字在N位上一个为1，一个为0，那么在该位置的异或为1，我们将所有的数字进行异或操作：
    假设a、b为落单的数字那么 a ^ b ^ c ^ c ^ d ^ d ... = a ^ b
    因此我们只需要找到 a ^ b（二进制）上第一个为1的位置，取该位置为N即可
    6.3代码：
// 寻找唯一落单的数字
int findOnlyNum(vector<int> nums)
{
    int num  = 0;
    for(int i = 0; i < nums.size(); ++i)
        num ^= nums[i];
    return num;
}
vector<int> findTwoOnlyNums(vector<int> nums)
{
    vector<int> re;
    int allNums = 0;
    // 计算两个落单数字的异或（相同的数字异或为0）
    for(int i = 0; i < nums.size(); ++i)
        allNums ^= nums[i];
    // 寻找首位两个落单数字不相同的位数，该位置上两者异或为1
    int N = 0;
    // 使用 00...001 到 100...000 与 allNums 进行 与操作 找到首位为1的位置
    cout<<"allNums = "<<allNums<<endl;
    // 在写这种按位的计算公式时候全部用（）隔开z保证优先级
    while((allNums & (1 << N)) != (1 << N))
        ++N;
    cout<<"在第 "<<N + 1<<" 位置不一样"<<endl;
    // 采用分治的思想将N位为0和为1的数字分开（目的是将两个落单的数字分开）
    vector<int> nums0, nums1;
    for(int i = 0; i < nums.size(); ++i)
    {
        if((nums[i] & (1 << N)) == (1 << N))
            nums0.push_back(nums[i]);
        else
            nums1.push_back(nums[i]);
    }
    re.push_back(findOnlyNum(nums0));
    re.push_back(findOnlyNum(nums1));
    return re;
}
    

寻找数组中只出现一次的三个数

（7）寻找数组中只出现一次的三个数

2. 快慢指针

1. 判断链表是否有环为什么快慢指针一定会相遇
那么为什么快慢指针一定会相遇？

首先两者要相遇，肯定是在那个环里面（比如最好情况慢的指针一踏入环就和快指针相遇）。
然后我们要明确快慢指针的速度差为1，两者每移动一下，距离减1，而这个环的最小划分单位就是1，所以显然会相遇。

3. 判断是否为2的n次幂

无论2的多少次方，在使用2进制进行表示的时候，都是100..00,因此我们可以通过 n&(n-1)是否为0来判断一个数字是否为2的n次幂
eg: 8 的二进制为 1000
    8-1=7的如今在为 0111
    二进制的(1000)&(0111)=0，这个方法可以用来断定一个整数是否为2的n次幂