数据结构OJ题

1.字符串左旋

2.字符串旋转结果

3.旋转数组

4.移除元素

本篇主要是讲解一些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]);//计算了\0int 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;elsereturn 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;
}

【暴力求解】&【三步翻转】

【注意】