本系列博客为个人刷题思路分享，有需要借鉴即可。
1.目录大纲：
2.题目链接：
T1：消失的数字：LINK
T2：旋转数组：LINK
3.详解思路：
T1：
思路1：先排序，再与正常的数字相比较即可。
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdlib.h>
#include<stdio.h>
int int_cmp(const void* e1,const void* e2)
{
return *(int*)e1 - *(int*)e2;
}
int missingNumber(int* nums, int numsSize)
{
//先排序
qsort(nums,numsSize,sizeof(int),int_cmp);
//生成正常的数组与之比较
int i = 0;
int lose = 0;
for (i = 0; i < numsSize+1; i++)
{
if (i != nums[i])
{
lose = i;
break;
}
}
return lose;
}
int main()
{
int arr[9] = {
9,6,4,2,3,5,7,0,1 };
int ret = missingNumber(arr, sizeof(arr)/sizeof(arr[0]));
printf("%d\n", ret);
return 0;
}
思路2：先把正常数组数字全部加起来，然后减去原数组的数字
int missingNumber(int* nums, int numsSize){
//思路二：先加起来然后减去，即可得到消失的数字
int i = 0;
int lose = 0;
int sum = 0;
//加上0到numsSize全部的数字
for(i = 0;i<numsSize+1;i++)
{
sum+=i;
}
//减去原数组0到numsSize的数字
for(i = 0;i<numsSize;i++)
{
sum-=nums[i];
}
//得到消失的数字
lose = sum;
return lose;
}
思路3：异或运算
前提知识：
0 ^ X = X;//任何数字跟0异或都是原来的数
X ^ X = 0;//两个一样的数字进行异或得到的是0
X ^ Y ^ X = Y;//异或操作满足交换律
int missingNumber(int* nums, int numsSize){
// //思路二：先加起来然后减去，即可得到消失的数字
// int i = 0;
// int lose = 0;
// int sum = 0;
// //加上0到numsSize全部的数字
// for(i = 0;i<numsSize+1;i++)
// {
// sum+=i;
// }
// //减去原数组0到numsSize的数字
// for(i = 0;i<numsSize;i++)
// {
// sum-=nums[i];
// }
// //得到消失的数字
// lose = sum;
// return lose;
//思路三：异或操作
int i = 0;
int lose = 0;
//异或正常的数组
for(i = 0;i<numsSize+1;i++)
{
lose^=i;
}
//异或原来的数组
for(i = 0;i<numsSize;i++)
{
lose^=nums[i];
}
//返回
return lose;
}
T2：
思路1：借助一个变量一个一个挪动
void rotate(int* nums, int numsSize, int k) {
int temp = 0;
int i = 0;
//旋转几次
while (k--)
{
//开始第一组挪动
temp = nums[numsSize - 1];//先把最后一个数字放到临时变量中
for (i = numsSize - 2; i >= 0; i--)
{
nums[i+1] = nums[i];
}//挪动数组往前一位
nums[0] = temp;//把临时变量中的值放到数组第一个
}
}
int main()
{
int arr[7] = {
1,2,3,4,5,6,7 };
rotate(arr,7,3);
int i = 0;
for (i = 0; i < 7; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
思路2：一步到位，拷贝法
void rotate(int* nums, int numsSize, int k) {
if(k>numsSize)
k%=numsSize;
//新数组，拷贝
int arr[numsSize];
int i = 0;
for(i = 0;i<numsSize;i++)
{
arr[i] = nums[i];
}
//覆盖原数组内容
for(i = 0;i<k;i++)
{
nums[k-1-i] = arr[numsSize-1-i];
}
for(i = 0;i<numsSize-k;i++)
{
nums[k+i] = arr[i];
}
}
思路3：逆置
void Reverse(int* nums,int left,int right)
{
while(left<right)
{
nums[left] = nums[left]^nums[right];
nums[right] = nums[left]^nums[right];
nums[left] = nums[left]^nums[right];
left++;
right--;
}
}
void rotate(int* nums, int numsSize, int k) {
if(k>numsSize)
k%=numsSize;
//逆置前半部分
Reverse(nums,0,numsSize-k-1);
//逆置后半部分 4 6
Reverse(nums,numsSize-k,numsSize-1);
//逆置整体
Reverse(nums,0,numsSize-1);
}
完。
