本文重点
- 左旋字符串
- 法一:暴力求解
- 法二:逆序三次
- 拓展:判断一个字符串是否为另一个字符串旋转后的字符串
- 法一:穷举暴力求解
- 法二:追加
💜新专栏开通
biubiu~
😇日后小边会逐渐完善这个专栏,把所有面试经典题目都分享给小伙伴们
想得到就别等待趁现在去热爱呀!
正文开始@边通书
左旋字符串
题目描述:
字符串左旋
题目内容:
实现一个函数,可以左旋字符串中的k
个字符。
例如:
ABCD
左旋一个字符得到BCDA
ABCD
左旋两个字符得到CDAB
法一:暴力求解
💛思路:
代码实现:
#include<stdio.h>
#include<assert.h>
#include<string.h>
void left_move(char* arr, int k)
{
assert(arr);//断言--防止传入空指针
int i = 0;
int len = strlen(arr);
for (i = 0; i < k; i++)
{
//左旋一个字符
//1.保存第一个字符
char tmp = *arr;
int j = 0;
//2.将后续的字符一次向前移动
for (j = 0; j < len; j++)
{
*(arr + j) = *(arr + j + 1);
}
//3.把保存好的第一个字符放在末位
*(arr + len - 1) = tmp;
}
}
int main()
{
char arr[] = "ABCD";
int k = 0;
scanf("%d", &k);
left_move(NULL, k);
printf("%s\n", arr);
return 0;
}
注:
定义arr时,
❌不可用char* p = "ABCD";
的形式,因为"ABCD"
是常量字符串,不可更改,而这里要对字符串左旋,
✔️而要用char arr[] = "ABCD";
以字符串初始化数组,字符数组可以被更改。
测试用例:
法二:逆序三次
💛思路:
代码实现:
#include<stdio.h>
#include<string.h>
#include<assert.h>
//逆序
void reverse(char* left, char* right)
{
assert(left&&right);//断言
while (left < right)
{
char tmp = *left;
*left = *right;
*right = tmp;
left++;
right--;
}
}
int main()
{
char arr[] = "abcdef";
int len = strlen(arr);
int k = 2;
reverse(arr, arr + k - 1);//逆序左边
reverse(arr + k, arr + len - 1);//逆序右边
reverse(arr, arr + len - 1);//逆序整体
printf("%s\n", arr);
return 0;
}
测试用例:
拓展:判断一个字符串是否为另一个字符串旋转后的字符串
题目描述:
字符串旋转结果
题目内容: 写一个函数,判断一个字符串是否为另外一个字符串旋转之后的字符串。
例如:
给定s1 = AABCD
和s2 = BCDAA
,返回1
给定s1 = abcd
和s2 = ACBD
,返回0
AABCD
左旋一个字符得到ABCDA
AABCD
左旋两个字符得到BCDAA
AABCD
右旋一个字符得到DAABC
法一:穷举暴力求解
💛思路:
穷举:每次旋转arr1的一个字符,与arr2比较。 利用上文已经写好的
left_move
函数。
代码实现:
#include<stdio.h>
#include<string.h>
#include<assert.h>
void reverse(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)
{
assert(arr);
int len = strlen(arr);
k %= len;
reverse(arr, arr + k - 1);//逆序左边
reverse(arr + k, arr + len - 1);//逆序右边
reverse(arr, arr + len - 1);//逆序整体
}
//判断一个字符串是否为另外一个字符串旋转之后的字符串
int is_left_move(char* arr1, char* arr2)
{
assert(arr1&&arr2);
int len = strlen(arr1);
int i = 0;
for (i = 0; i < len; i++)
{
left_move(arr1, 1);//每次旋转1个字符,比较
if (strcmp(arr1, arr2) == 0)
{
return 1;
}
}
return 0;
}
int main()
{
char arr1[] = "AABCD";
char arr2[] = "ABCD";
int ret = is_left_move(arr1, arr2);
if (ret == 1)
{
printf("Yes\n");
}
else
{
printf("No\n");
}
return 0;
}
测试用例:
法二:追加
💛思路:
简单介绍strncat
和strstr
的使用:
代码实现:
#include<stdio.h>
#include<string.h>
#include<assert.h>
int is_left_move(char* arr1, char* arr2)
{
assert(arr1&&arr2);//断言
int len1 = strlen(arr1);
int len2 = strlen(arr2);
//1.在arr1后追加一个arr1字符串
strncat(arr1, arr1, len1);
//2.判断arr2是否为arr1的子串且字符串长度要相等
if (NULL != strstr(arr1, arr2) && len1 == len2)
{
return 1;
}
else
{
return 0;
}
}
int main()
{
char arr1[20] = "AABCD";//要保证arr1开辟空间足够大
char arr2[] = "ABCD";
int ret = is_left_move(arr1, arr2);
if (ret == 1)
{
printf("Yes\n");
}
else
{
printf("No\n");
}
return 0;
}
测试用例:
本文完@边通书