189. 轮转数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

力扣https://leetcode.cn/problems/rotate-array/description/

void rotate(int* nums, int numsSize, int k){if(k > numsSize){k %= numsSize;}if(k==0){for(int i=0;i<numsSize;++i){nums[i]=nums[i];  }}int newArr[numsSize+k];int n=0;for(int i=0;i<numsSize;++i){if(i+k<numsSize){newArr[i+k]=nums[i];}else{newArr[n]=nums[i];n++;}}for(int i=0;i<numsSize;++i){nums[i]=newArr[i];}}

虽然这段代码可以解决在k等于0时的问题，但是依然存在新创建数组和使用额外变量n的问题，可能会影响程序的性能和效率。在旋转次数不为0的情况下，仍需要创建新的数组，并且进行两次循环操作，比较耗费时间和空间。

因此，可以考虑使用其他的算法或优化方法来改进代码的实现方式，例如直接在原数组上进行旋转操作，不需要创建新数组，并且可以避免以上问题。

void reverse(int*nums,int begin,int end)
{while(begin<end){int tmp=nums[begin];nums[begin]=nums[end];nums[end]=tmp;begin++;--end;}
}void rotate(int* nums, int numsSize, int k){//采用三趟倒置的做法if(k<numsSize){k%=numsSize;}reverse(nums,0,numsSize-1);reverse(nums,0,k-1);reverse(nums,k,numsSize-1);
}

上述代码实现了数组元素的旋转操作，采用的是三次反转操作的方法。具体来说，对于给定的数组 nums，将其整个数组进行反转，然后将前 k 个元素进行反转，最后将剩余的元素进行反转，即可得到将数组旋转 k 步后的新数组。

---

面试题 17.04. 消失的数字

数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？

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

上述代码同样实现了在给定的数组 nums 中查找缺失的数字，并返回该数字。这个算法采用了数学方法计算序列中所有数字的和，然后减去数组 nums 中所有元素的和，差值就是缺失的数字。

具体来说，由于 nums 数组中缺失一个数字，因此整个序列的长度应该是 numsSize+1。假设整个序列包含从 0 到 numsSize 的所有整数，那么序列元素的总和为 (numsSize+1)*numsSize/2。因此，只需要遍历数组 nums，将 nums[i] 的值累加起来，然后用总和减去这个累加和，最终得到的就是缺失的数字。

int Num(int a)
{if (a <= 0){return 0;}else{return a + Num(a - 1);}
}int missingNumber(int* nums, int numsSize) {int b = Num(numsSize);int c = 0;for (int i = 0; i < numsSize; i++){c =c + nums[i];}int d = b - c;return d;
}

上述代码同样实现了在给定的数组 nums 中查找缺失的数字，并返回该数字。与上一个算法不同的是，这个算法采用递归函数 Num 求出整数从 1 到 numsSize 的所有和 b，然后将数组 nums 中所有元素的值累加起来得到 c，最后用 b 减去 c 得到缺失的数字。

具体来说，递归函数 Num 的实现与第一段代码片段相同，但由于它的时间复杂度为 O(n)，因此可能会在计算较大的 numsSize 时导致栈溢出或超时等问题。因此，这种算法的使用范围受到一定限制，仅适用于 numsSize 较小的情况。

总的时间复杂度为 O(n)，空间复杂度为 O(1)。需要注意的是，在递归函数中调用自身时，每次调用都会创建新的函数栈帧，因此递归调用会占用一定的内存空间，可能会导致栈溢出等问题。

---

 3. 整数反转

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231,  231 − 1] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。

int reverse(int x){int rev=0;while(x!=0){if(rev<INT_MIN/10||rev>INT_MAX/10){return 0;}int turn=x%10;x/=10;rev=rev*10+turn;}return rev;
}

该函数的目标是对给定的整数 x 进行反转，并将反转后的结果作为函数的返回值。在进行反转操作时，我们需要依次取出整数的每一位数字，然后将它们按照相反的顺序组成一个新的整数。例如，对于整数 123456，其反转结果应该为 654321。

具体来说，该函数的实现主要包含以下几个步骤：

初始化反转结果 rev 为 0，准备开始反转操作

int rev = 0;

进入一个 while 循环，循环条件为整数 x 不为 0。在每一次循环中，我们需要取出当前整数的最后一位数字，并将其追加到反转结果 rev 的末尾。

while (x != 0) {int turn = x % 10;          // 取出最后一位数字x /= 10;                    // 去掉最后一位数字rev = rev * 10 + turn;      // 将最后一位数字添加到反转结果 rev 的末尾
}

在更新反转结果 rev 前，需要判断当前的值是否超出了 int 类型的取值范围。如果超出，则直接返回 0，表示无法得到正确的反转结果。

if (rev < INT_MIN / 10 || rev > INT_MAX / 10) {return 0;
}

这里的 INT_MIN 和 INT_MAX 分别表示 int 类型的最小值和最大值。如果反转结果 rev 除以 10 的结果小于 INT_MIN 或大于 INT_MAX，则说明反转结果已经超出了 int 类型的取值范围，无法得到正确的结果。

需要注意的是，在进行整数反转时，由于整数反转涉及数值溢出问题，因此需要特判反转结果的取值范围，以确保程序能够处理所有可能的情况。

循环结束后，返回反转结果 rev。

return rev;

如果输入整数为负数，则在反转前需要先去掉符号位，并在最后将反转结果添加上负号以得到正确的结果。

这一步可以通过在循环开始前增加以下代码实现：

bool negative = false;     // 标记整数是否为负数
if (x < 0) {negative = true;x = -x;                // 去掉符号位
}

在返回结果时，我们需要根据输入整数的符号，判断是否需要将反转结果添加上负号：

if (negative) {return -rev;
} else {return rev;
}

以上就是该函数的详细解释。总体来说，该函数的实现还是比较简单的，主要难点在于如何处理数字的反转和数值溢出问题。

---