复杂度的oj练习:
1.消失的数字
2.轮转数组
这篇文章是关于消失的数字和轮转数组的做题方法讲解。
一.消失的数字
思路:
从原题的示例2入手, [9,6,4,2,3,5,7,0,1] ，加上0就是9个数,但是0是什么都没有,所以说0这个位置就是缺的数字。那么原题是说:数组nums包含从0到n的所有整数，说明这个数组的元素的值是连续递增的,而且每次递增1。又因为原数组最大的元素为9，那么从1数过去,缺失的数字就是8。
方法一:异或全部元素
思路：
具体做法是将0到n（示例二的9）和nums（示例二的数组）中的所有数都异或起来，缺失的整数会在异或的过程中被找出来。异或满足结合律和交换律，因此最终的结果就是缺失的整数。
异或运算的规则如下：
0异或规则：
对于任意一个数a，a异或0的结果都是a本身，即a ^ 0 = a。
a ^ a规则：
对于任意一个数a，a异或a的结果是0，即a ^ a = 0。
画图:
所以说缺失的数字为8。
代码实现:
int missingNumber(int* nums, int numsSize) { int x = 0; for (int i = 0; i < numsSize; i++) { x ^= nums[i]; } for (int i = 0; i < numsSize+1; i++) { x ^= i; } return x; } int main() { int num[9] = { 9,6,4,2,3,5,7,0,1 }; int numsSize = sizeof(num)/sizeof(num[0]); int ret=missingNumber(num, numsSize); printf("消失的数字为:%d", ret); return 0; }
执行:
方法二:利用等差数列求和-该数组全部元素之和。
等差数列的前n项和公式为：
Sn = n/2 * (a1 + an)
其中，Sn表示等差数列的前n项和，a1表示等差数列中第一项的值，an表示等差数列中第n项的值，n表示等差数列的项数。根据等差数列的前n项和公式，可以快速求得等差数列前n项的和。
缺失的数字=Sn - 数组nums的每一个值
代码实现:
int missingNumber(int* nums, int numsSize) { int x = (1+numsSize)*numsSize/2; for (size_t i = 0; i < numsSize ; i++) { x -= nums[i]; } return x; } int main() { int num[9] = { 9,6,4,2,3,5,7,0,1 }; int numsSize = sizeof(num)/sizeof(num[0]); int ret=missingNumber(num, numsSize); printf("消失的数字为:%d", ret); return 0; }
执行:
二.轮转数组
题型1:实现一个函数，可以左旋字符串中的k个字符。
实现一个函数，可以左旋字符串中的k个字符。
例如：
ABCD左旋一个字符得到BCDA
ABCD左旋两个字符得到CDAB
写法1:暴力求解
思路:
取出数组第一个元素放到临时变量tmp内,接着所有元素往前挪动，挪动完毕把tmp内的元素放到数组最后一个位置。
以下是动图演示:这是左旋1个字符的效果
代码实现:
#include<string.h> void reverse_left(char *arr,int k) { int len = strlen(arr); //k = k % len; for (int i = 0; i < k; i++)//k是左旋几遍的意思 { int j = 0; char tmp = arr[0]; for (j = 0; j < len - 1; j++) { arr[j] = arr[j + 1];//元素往前挪动 } arr[len - 1] = tmp; } } int main() { char arr[] = "abcdef"; int k = 0; scanf("%d",&k);//左旋k个字符串 reverse_left(arr, k); printf("%s", arr); }
代码执行:
特别说明:
k = k % len 这一行代码的作用是将 k 对字符串的长度 len 取模 (求余数)，从而确保旋转的位移量始终在字符串长度内。
例如，如果字符串长度为 6，k 的值为 8，则旋转 8 个字符实际上等于旋转 2 个字符，因为每旋转 6 个字符，字符串就会回到原始状态。因此，通过对 k 取模，可以确保旋转的位移量始终在字符串长度内，从而确保旋转的正确性。
根据该题写出右旋转:
//右旋转 void right_move(char arr[], int k) { int i = 0; int len = strlen(arr); k = k % len; for (i = 0; i < k; i++) { int j = 0; char tmp = arr[len-1]; for (j = len-1; j > 0; j--) { arr[j] = arr[j -1]; } arr[0] = tmp; } } int main() { char arr[20] = "abcdef"; int k = 0; scanf("%d", &k); right_move(arr, k); printf("%s\n", arr); }
代码执行:
写法2：三步旋转法(左逆序，右逆序，整体逆序)
abcdef
b a c d e f左部分旋转
b a f e d c右部分旋转
c d e f a b整体逆序
最后一步实际上是从旋转完左子串和右子串之后整体再旋转一遍，
但为了效率地看出结果,只要按着箭头的方向输出字符就是最终的结果。
代码实现:
//左旋转 #include<stdio.h> #include<assert.h> #include<string.h> void reverse_string(char*left,char *right) { assert(left && right); while (left < right) { char tmp = *left; *left = *right; *right = tmp; left++; right--; } } void left_move(char arr[],int k) { int len = strlen(arr); k = k % len; reverse_string(arr,arr+k-1);//左部分 reverse_string(arr+k,arr+len-1);//右部分 reverse_string(arr,arr+len-1);//整体 } int main() { char arr[] = "abcdef"; int k = 0; scanf("%d",&k); left_move(arr, k); printf("%s\n", arr); return 0; }
代码执行:
根据左旋转写右旋转
代码实现:
右旋转 void reverse_string(char* left, char* right) { assert(left && right); while (left < right) { char tmp = *left; *left = *right; *right = tmp; left++; right--; } } void right_move(char arr[], int k) { int len = strlen(arr); k = k % len; reverse_string(arr+len-k, arr + len-1);//右部分 reverse_string(arr , arr + len -1-k);//左部分 reverse_string(arr, arr + len - 1);//整体 } int main() { char arr[] = "abcdef"; int k = 0; scanf("%d", &k); right_move(arr,k); printf("%s\n", arr); return 0; }
代码执行:
