本系列博客为个人刷题思路分享，有需要借鉴即可。
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); }
完。
