原贴地址：http://blog.leanote.com/post/dawnmagnet/c8deab0f58d7
题目
思路分析
这个题目就算我们暴力做，也只是O(n)的复杂度，而且题目的数据给的也不是很大，暴力一定非常快。（窃喜
于是我们暴力做了一下，很快啊，就出来了，直接就AC了，还只用了0ms。
impl Solution {pub fn xor_operation(n: i32, mut start: i32) -> i32 {let mut res = 0;for i in 0..n {res ^= (start + 2 * i);}res}
}
那么请问我们还有继续往下优化的必要吗？
当然有。
往下优化，复杂度可能是O(1)或者O(lgn)，一般来说，我们要有基本的概念。
怎么样才能让复杂度到达O(1)呢？一般来说是答案是有规律的，套个公式什么的直接就能出答案。
怎么样才能让复杂度到达O(lgn)呢？一般来说是通过除2来构造的，除2之前之后获取一些信息，再组合组合。这样才能得到O(lgn)的答案。
给大家一些做题目时候的小tips，遇到这种数列找规律的题目，先打印出来看看，是否符合规律（基本上都能肉眼观察出来）
以下是初始值为0的时候前20项
0 2 6 0 8 2 14 0 16 2 22 0 24 2 30 0 32 2 38
以下是初始值为1的时候前20项
1 2 7 0 9 2 15 0 17 2 23 0 25 2 31 0 33 2 39
以下是初始值为2的时候前20项
2 6 0 8 2 14 0 16 2 22 0 24 2 30 0 32 2 38 0
以下是初始值为3的时候前20项
3 6 1 8 3 14 1 16 3 22 1 24 3 30 1 32 3 38 1
不难看出，以任何数字为初始值开始都是有规律可循的。而且每一个都是4项为一组。
| 初始值 | 规律 |
|---|---|
| 0 | * 2 * 0 |
| 1 | * 2 * 0 |
| 2 | 2 * 0 * |
| 3 | 3 * 1 * |
不难看出都是有规律可循的，而只要定位了这些规律点，就非常好求每一项了，比如求起始为0的第五项，我们只需要在里面找到第五项的位置，就是2左边的位置，再用2去异或2 * n 也就是2 ^ 10 = 8，按照这个方法，只要我们确定了特征点，在去反推任何位置的数字，只需要O(1)的时间，最多不会超过三步
- 对4取余，在特征数组中定位
- 如果是定值，则返回定值
- 如果不是定值，则拿定值反推
OK，就好了。
而对于数组的预处理，我们只需要定一个长度为4的特征数组，从第一项循环到第八项，就可以确定这个数组里哪些数字是不变的常量，我们就用常量表示，哪些数字是不确定的，我们就将其标注为-1（与表格中的*等价）。
整个算法的复杂度是O(1)级别的，非常快速也非常简单易懂。
Rust代码
impl Solution {pub fn xor_operation(mut n: i32, mut start: i32) -> i32 {let mut sto = [-1; 4];let mut tmp = 0;for i in 0..4 {tmp ^= (start + 2 * i);sto[i as usize] = tmp;}for i in 0..4 {tmp ^= (start + 2 * (i + 4));if sto[i as usize] != tmp {sto[i as usize] = -1;}}let n = n as usize;match sto[(n - 1) % 4] {-1 => sto[n % 4] ^ (start + 2 * n as i32),_ => sto[(n - 1) % 4]}}
}
C++代码
class Solution {
public:int xorOperation(int n, int start) {
vector<int> sto = {
0, 0, 0, 0};int tmp = 0;for (int i = 0; i < 4; ++i) {
tmp ^= (start + 2 * i);sto[i] = tmp;}for (int i = 0; i < 4; ++i) {
tmp ^= (start + 2 * (i + 4));if (sto[i] != tmp)sto[i] = -1;}if (sto[(n - 1) % 4] == -1) return sto[n % 4] ^ (start + 2 * n);else return sto[(n - 1) % 4];}
};