题目1——轮转数组
题目来源. - 力扣（LeetCode）
轮转（或称为旋转）数组是一种常见的算法问题，通常指的是将数组中的元素向右或向左移动一定位置，使得数组的元素重新排列。
以下是一个简单的思路，用于解决将数组向右轮转k个位置的问题（其中k小于或等于数组长度）：
思路一：三次翻转法
- 翻转整个数组：首先，将整个数组翻转。
- 翻转前k个元素：然后，翻转数组的前k个元素。
- 翻转剩余元素：最后，翻转数组中从第k个元素到末尾的部分。
通过这三次翻转，你可以得到向右轮转k个位置的数组。
// 翻转数组从start到end的部分
void reverse(int* nums, int start, int end) {
while (start < end) {
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}
// 原地向右轮转数组k个位置
void rotate(int* nums, int numsSize, int k) {
k %= numsSize; // 确保k不超过数组长度
reverse(nums, 0, numsSize - 1); // 翻转整个数组
reverse(nums, 0, k - 1); // 翻转前k个元素
reverse(nums, k, numsSize - 1); // 翻转剩余元素
}
思路二：额外空间法
以下是额外空间法的步骤：
-
创建新数组：首先，根据原数组的大小，创建一个新的数组。这个新数组将用于存储轮转后的结果。
-
计算新位置：遍历原数组中的每个元素，根据轮转规则计算出该元素在新数组中的位置。对于向右轮转k个位置的情况，元素
nums[i]在新数组中的位置将是(i + k) % numsSize，其中numsSize是原数组的大小。 -
复制元素：将原数组中的每个元素复制到新数组中计算出的位置上。
-
（可选）替换原数组：如果题目要求原地修改数组，则可以在复制完所有元素后，将新数组中的元素复制回原数组。但如果题目只是要求返回轮转后的数组，那么可以直接返回新数组。
这种方法使用了额外的空间，但代码可能更直观和易于理解。
// 使用额外空间轮转数组
void rotate(int* nums, int numsSize, int k) {
k %= numsSize; // 确保k不超过数组长度
int* rotated = (int*)malloc(numsSize * sizeof(int));
if(roated==NULL)
{assert(roated);
perror("malloc failed");
exit(-1)
}
// 将元素放到新数组的正确位置
for (int i = 0; i < numsSize; i++) {
rotated[(i + k) % numsSize] = nums[i];
}
// 将新数组的元素复制回原数组
for (int i = 0; i < numsSize; i++) {
nums[i] = rotated[i];
}
// 释放额外空间
free(rotated);
}
题目2——消失的数字
题目来源：. - 力扣（LeetCode）
思路——异或
异或运算有一个重要的性质：对于任何数x，都有x^x = 0和x^0 = x。
我们可以先对从0到n的所有整数进行异或操作，得到一个结果xor_total。
然后，遍历给定的数组，对数组中的每个数字进行异或操作，将结果与xor_total进行异或。
由于异或运算的性质，所有在数组中出现两次的数字都会相互抵消，最后剩下的就是缺失的那个数字。
int missingNumber(int* nums, int numsSize) {
int xor_total = 0; // 用于存储从0到n的异或结果
for (int i = 0; i <= numsSize; i++) { // 遍历从0到n的所有整数
xor_total ^= i; // 对每个整数进行异或
}
for (int i = 0; i < numsSize; i++) { // 遍历给定的数组
xor_total ^= nums[i]; // 对数组中的每个数字进行异或
}
return xor_total; // 返回异或的结果，即缺失的数字
} 
