本篇主要是讲解一些OJ题目。
1.字符串左旋
字符串左旋
实现一个函数，可以左旋字符串中的k个字符
例如：
ABCD左旋一个字符得到BCDA
ABCD左旋两个字符得到CDAB
方法1【暴力求解】
- 翻转1个字符
- 创建一个中间变量tmp，用于存储翻转的字符
- 把后面的字符向前覆盖移动
- 把tmp存储的字符放到结尾
- 翻转k个字符，循环k次即可
- 注意如果旋转超出数组的元素个数范围，需要现处理一下。k=%len
#include<stdio.h> void left_move(char* arr, int sz,int k) { int i = 0; for (i = 0; i < k; i++)//k次 { //一次翻转 char tmp = 0;//1. tmp = *arr; int j = 0;//2. for (j = 0; j < sz - 2; j++) { arr[j] = arr[j + 1]; } arr[sz - 2] = tmp;//3. } } int main() { char arr[] = "ABCDEF"; int sz = sizeof(arr) / sizeof(arr[0]);//计算了\0 int k = 0; scanf_s("%d", &k); k = k % (sz - 1); left_move(arr, sz,k); printf("%s", arr); return 0; }
方法2【三步翻转】
- 左边逆序
- 右边逆序
- 整体逆序
- 封装一个逆序字符串的函数，传不同的起尾位置，调用三次函数即可
- 注意如果旋转超出数组的元素个数范围，会造成数组越界的问题，需要现处理一下。k=%len
#include<stdio.h> //逆序字符串函数 void reverse(char* begin, char* end) { while (begin < end) { char tmp = 0; tmp = *begin; *begin = *end; *end = tmp; begin++; end--; } } int main() { char arr[] = "ABCDEF"; int sz = sizeof(arr)/sizeof(arr[0]); int k = 0; scanf_s("%d", &k); k = k % (sz - 1);//必须有不然会数组越界 reverse(arr, arr + k-1); reverse(arr + k, arr + sz - 2); reverse(arr, arr + sz - 2); printf("%s", arr); return 0; }
2.字符串旋转结果
字符串旋转结果
写一个函数，判断一个字符串是否为另外一个字符串旋转之后的字符串。
例如：
给定s1= AABCD和s2 = BCDAA，返回1
给定s1=abcd和s2=ABCD，返回0
方法1【暴力求解】
- 旋转1次比较1次
- 把所有结果都列出来一一比较，如果没有那就返回0.
- 注意：如果两个数组的长度不一样，是肯定不会旋转得到的，需要处理一下。
#include<stdio.h> #include<string.h> #include<assert.h> int is_left_move(char* arr1, const char* arr2) { assert(arr1 && arr2); int len1 = strlen(arr1); int len2 = strlen(arr2); if (len1 != len2) { return 0; } int i = 0; //这里如果用while len是变化的 for(i=0;i<len1;i++) { //一次翻转 char tmp = 0;//1. tmp = *arr1; int j = 0;//2. for (j = 0; j < len1 - 1; j++) { arr1[j] = arr1[j + 1]; } arr1[len1 - 1] = tmp;//3 //判断 if (strcmp(arr1, arr2) == 0) { return 1; } } return 0; } int main() { char arr1[] = "ABCDEF"; char arr2[] = "CDEFAB"; int ret=is_left_move(arr1, arr2); if (ret == 1) { printf("YES"); } else { printf("NO"); } return 0; }
方法2【追加找子串 】
- 把原字符串数组arr1追加，这样翻转所有的可能性都在追加字符串里
- 再去arr1追加字符串里找子串arr2，看是否和要比较字符串数组arr2，相符号的。
- 注意：如果两个数组的长度不一样，是肯定不会旋转得到的，需要处理一下。
#include<stdio.h> #include<string.h> #include<assert.h> int is_left_move(char* arr1, const char* arr2) { assert(arr1 && arr2); int len1 = strlen(arr1); int len2 = strlen(arr2); if (len1 != len2) { return 0; } int len = strlen(arr1); strncat(arr1, arr1, len); if (strstr(arr1, arr2) == NULL) return 0; else return 1; } int main() { char arr1[] = "ABCDEF"; char arr2[] = "CDEFAB"; int ret=is_left_move(arr1, arr2); if (ret == 1) { printf("YES"); } else { printf("NO"); } return 0; }
3.旋转数组
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
方法1【暴力求解】
同上
时间复杂度：O(N^2)
#include<stdio.h> #include<string.h> #include<assert.h> void right_move(char* arr,int k) { assert(arr); int len = strlen(arr); k%=len; int i = 0; 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 = tmp; } } int main() { char arr[] = "ABCDEF"; int k = 0; scanf("%d", &k); right_move(arr,k); printf("%s", arr); return 0; }
方法2【三步翻转】
界限：需要右旋&不需要右旋的逆置，整体逆置
时间复杂度：O(N)
#include<stdio.h> //逆序字符串函数 void reverse(char* begin, char* end) { while (begin < end) { char tmp = 0; tmp = *begin; *begin = *end; *end = tmp; begin++; end--; } } int main() { char arr[] = "ABCDEF"; int len = strlen(arr); int k = 0; scanf_s("%d", &k); k = k % len;//必须有不然会数组越界 reverse(arr,arr+len-k-1); reverse(arr+len-k,arr+len-1); reverse(arr,arr+len-1); printf("%s", arr); return 0; }
方法3【以时间换空间】
- 先拷贝前len-k个到后面位置
- 再拷贝k个 到前面位置
- 最后拷贝回去
- 变长数组和动态内存开辟的数组都可
- 关键就是下标和位置一定一定控制清楚
- 时间复杂度：O(N) 空间复杂度：O(N)
void rotate(int* nums, int numsSize, int k) { int tmp[numsSize]; int i=0; k%=numsSize;//就这个代码卡了我一下午，有时候真的很无助 for(i=0;i<k;i++) { *(tmp+i)=*(nums+numsSize-k+i); } for(i=0;i<numsSize-k;i++) { *(tmp+k+i)=*(nums+i); } for(i=0;i<numsSize;i++) { *(nums+i)=*(tmp+i); } }
4.移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
方法1【暴力求解】
- 首先遍历数组一遍找到元素
- 从后向前依次覆盖
- 时间复杂度：O(N^2)
int removeElement(int* nums, int numsSize, int val) { int i=0; for(i=0;i<numsSize;i++) { if(nums[i] == val) { for(;i<numsSize-i;i++)//❌ nums[i]=nums[i+1]; } } return numsSize; }
方法2【以空间换时间】
- 创建一个一摸一样的数组tmp
- 把是val的数值元素留下，不是的拷贝到tmp中
- 最后把tmp拷贝到nums里面去
- 时间复杂度：O(N)
但是我们发现，题目要求不允许这么做？怎么办呢？
方法3【方法2的优化】
那我们选择就在nums的基础上实现tmp等的功能。
- 使用src指针和des指针
- 时间复杂度O(N)
int removeElement(int* nums, int numsSize, int val){ int src=0; int dst=0; while(src<numsSize) { if(nums[src] != val) { nums[dst++]=nums[src++]; } else { src++; } } return dst; }
【暴力求解】&【三步翻转】
【注意】
- len&sz
- 指针&数组下标
- 如果找错了位置或者减少了都会发生错误❌
✔✔✔✔✔最后，感谢大家的阅读，若有错误和不足，欢迎指正！ 棠棣
代码---------→【唐棣棣 (TSQXG) - Gitee.com】
联系---------→【邮箱：2784139418@qq.com】
