脚撕LeetCode(1486)Easy

题目地址：https://leetcode-cn.com/problems/xor-operation-in-an-array/

给你两个整数，n 和 start 。 数组 nums 定义为：nums[i] = start + 2i（下标从 0 开始）且 n == nums.length 。 请返回 nums 中所有元素按位异或（XOR）后得到的结果。 示例 1： 输入：n = 5, start = 0 输出：8 解释：数组 nums 为 [0, 2, 4, 6, 8]，其中 (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8 。 "^" 为按位异或 XOR 运算符。 示例 2： 输入：n = 4, start = 3 输出：8 解释：数组 nums 为 [3, 5, 7, 9]，其中 (3 ^ 5 ^ 7 ^ 9) = 8. 示例 3： 输入：n = 1, start = 7 输出：7 示例 4： 输入：n = 10, start = 5 输出：2

提示： 1 <= n <= 1000 0 <= start <= 1000 n == nums.length

这道题的题意是，给你一个n，遍历 0 ～ n-1 这n个数，然后返回每个数的2 倍 + start 抑或的结果（也就是i = [0,n-1],ans = 每个2*i + start 的抑或

一、爆破法

这道题如果直接用数组肯定内存会特别大，所以我们不用数组直接计算，反正最后一起抑或和一个个抑或结果一样。

执行结果如下：

54 / 54 个通过测试用例

状态：通过

执行用时: 0 ms

内存消耗: 34.8 MB

public int xorOperationMe(int n, int start) {
    int ans = start;
    for (int i = 1; i < n; i++) {
        ans ^= (2 * i + start);
    }
    return ans;
}

时间是100%，但是内存只有30-50（不稳定）

当然了，我们还是要看一下官方答案，官方答案用到了一些数学思维

二、官方高中数学法

抑或的原则如下：

1.x^x = 0

2.x^y = y^x

3.(x^y)^z = x^(y^z)

4.x^y^y = x

5.任何 i 属于Z 有 4i ^ (4i+1) ^ (4i+2) ^ (4i+3) = 0

我们要计算：start^(start+2i)^(start+4i)^⋯^(start+2(n−1))。

我们可以看到他们的奇偶都是相同的，start为奇数大家都为奇数，start为偶数大家都为偶数，所以我们可以把公式转换成

2 * (s ^ (s + 1) ^ (s + 2) ^ (s + 3) ^ ……^(s + n-1)) + e

这个s = start/2 ，e = 我们要求的最低位

我们可以简单的表示为 0 ^ 1 ^ 2 ……^ x

根据定律5可知

当x = 4k的时候，结果 = x

当x = 4k + 1 的时候，结果 = (x - 1) ^ x

当x = 4k + 2 的时候，结果 = (x - 2) ^ (x - 1) ^ x

当x = 4k + 3 的时候，结果 = (x - 3) ^ (x - 2) ^ (x - 1) ^ x

运用位抑或运算的基本知识简化后可知：

当x = 4k的时候，结果 = x

当x = 4k + 1 的时候，结果 = 1

当x = 4k + 2 的时候，结果 = x + 1

当x = 4k + 3 的时候，结果 = 0

于是只需要将结果跟4做模即可

执行结果如下：

54 / 54 个通过测试用例

状态：通过

执行用时: 0 ms

内存消耗: 35.2 MB

public int xorOperation(int n, int start) {
    int s = start >> 1, e = n & start & 1;
    int ret = sumXor(s - 1) ^ sumXor(s + n - 1);
    return ret << 1 | e;
}

public int sumXor(int x) {
    if (x % 4 == 0) {
        return x;
    }
    if (x % 4 == 1) {
        return 1;
    }
    if (x % 4 == 2) {
        return x + 1;
    }
    return 0;
}

这两天做题目有点消极，有点质量不行了，明天周五给自己放一天假吧，好好休息一天。明天可以看点别的书，或者找点别的乐趣。