轮转数组

OJ链接
题目要求：

方法一：使用额外的数组

在C99标准中，允许我们使用变长数组，在这标准下，我们可以通过使用额外的数组来解决这道题，只需要先将每个元素轮转后的正确位置放到新数组内，numsSize是数组长度，再遍历原数组，将原数组下标为 i 的元素放至新数组下标为 （i+k）% numsSize 的位置，最后拷贝到原来的数组就行了。

void rotate(int* nums, int numsSize, int k){int NewArr[numsSize];for(int i = 0;i < numsSize;++i){NewArr[(i + k) % numsSize] = nums[i];}   //这个%的意思是，万一K值过大，超过了numSize，对其mod取余for(int i = 0;i < numsSize;++i){nums[i] = NewArr[i];}
}

方法二：数组翻转

通过观察数组多次的轮转，我们可以发现一个规律：
将数组元素向右移动k次，则尾部k%numSize个元素会移动到数组的头部，其他的元素向后移动k%numSize个位置。
该方法就是基于这个规律，先将所有元素翻转，然后再翻转区间[0,k%(numSize-1)]内的元素，最后翻转[k%numSize,numSize-1]内的元素，就可以了。

用实例1的数据作示范：

//交换
void swap(int* a, int* b) 
{int t = *a;*a = *b；*b = t;
}
//翻转
void reverse(int* nums, int start, int end) 
{while (start < end) {swap(&nums[start], &nums[end]);start += 1;end -= 1;}
}void rotate(int* nums, int numsSize, int k) {k %= numsSize;reverse(nums, 0, numsSize - 1);reverse(nums, 0, k - 1);reverse(nums, k, numsSize - 1);
}

消失的数字

OJ链接

题目要求：

方法一：等差数列和公式

已知数组包括0到n的所有整数，那我们可以利用等差数列的和公式(Sn = n(a1+an)/2)来解决，先求出0到n所有整数的和，然后减去数组内所有元素，最后的答案就是消失的那个数字

int missingNumber(int* nums, int numsSize){int x = numsSize*(1 + numsSize)/2;for(int i = 0;i<numsSize;++i){x -= nums[i];}return x;
}

方法二：异或^

和找单身狗的方法类似，需要利用异或的性质

因为异或运算，相同为0，不同为1
举个栗子： x = 10，将其转化为二进制，x = 1010 。
将x与x异或一下
x ^ x = 0
将x与0异或一下，可以得到
x ^ 0 = x（因为转化为二进制后得到的为一个二进制的数据流，0 ^ 0 = 0, 1 ^ 0 = 1）

所以只要数组中只要有出现两次元素，它们就会两两异或变成0，而只出现一次的相当于和0异或，还是它本身。

所以这题我们需要将数组异或两次，第一次将数组内所有元素与x=0异或，得到的还是数组内的元素，第二次将x与0到numSize逐个异或，就能找到消失的数字了。

int missingNumber(int* nums, int numsSize){int x = 0;for(int i = 0;i<numsSize;i++){x ^= nums[i];}for(int j = 0;j<numsSize+1;j++){x ^= j;}return x;
}

你学会了吗？