前言
有的时候,这个系列专栏中的解法之间并无优劣,只是给大家提供不同的解题思路
我决定将代码实现的过程写成注释,方便大家直接找到对应的函数,只有需要补充说明的知识才会单拿出来强调
这个系列的文章会更的比较慢,因为多种解法的需要慢慢收集、整理
字符串左旋
实现一个函数,可以左旋字符串中的k个字符。
例如:
ABCD左旋一个字符得到BCDA
ABCD左旋两个字符得到CDAB
暴力求解法1:数组传参
#include<stdio.h>
#include<string.h>
void left_move(char arr[], int k)
{
int i = 0;
int len = strlen(arr);
for (i = 0; i < k; i++)
{
char tmp = arr[0];
int j = 0;
for (j = 0; j < len - 1; j++)
{
arr[j] = arr[j + 1];
}
arr[len - 1] = tmp;
}
}
int main()
{
int k = 0;
scanf("%d", &k);
char arr[] = "abcdef";
printf("%s\n", arr);
left_move(arr,k);
printf("%s\n", arr);
return 0;
}
在此简单的解释一下:先将前面的元素提取出来存在别的地方,然后后面的元素向前移动一位,再将前面的元素放在后面
通过循环即可实现
暴力求解法2:指针传参
#include<stdio.h>
#include<string.h>
#include<assert.h>
//函数主体(应用场景)
void left_move(char *arr, int k)
{
assert(arr);
//为了良好的代码风格(前面在《实用调试技巧》中有提到过),我们可以在函数体开头使用断言,防止arr是空指针
int i = 0;
for (i = 0; i < k; i++)//旋转一个字符
{
int len = strlen(arr);//求数组长度
char* tmp = arr;//存储第一个元素
int j = 0;
for (j = 0; j < len - 1; j++)//把后面的元素都向前移动一位
{
*(arr + j) = *(arr + j + 1);
//因为此处会访问到j+1,所以如果j<len的话,会出现数组越界的情况,所以在for循环的判断那里要注意一下
}
*(arr + len - 1) = tmp;
//将第一个元素存储到最后
}
}
int main()
{
char arr[] = "abcdef";
int k = 0;
scanf("%d", &k);
left_move(arr, k);//左旋函数
printf("%s\n", arr);//输出结果
return 0;
}
提示:使用assert
使用assert可以改善我们的代码风格,具体原因在我的另一篇文章中有详细说明,感兴趣的朋友可以去看一看
三步翻转法
思路:
先逆序前k个元素,再逆序后面的元素,最后再逆序整体
也就是同一个逆序函数要调用三次,我们为了整洁,就单独封装出一个reverse函数
需求:
想要实现逆序,就需要知道两端的地址
reverse函数
void reverse(char* left, char* right)
{
assert(left);//建议存在指针传参的时候,就使用断言,反正也不吃亏
assert(right);
while (left<right)
{
char tmp = *left;
*left = *right;
*right = tmp;
left++;
right--;
}
}
left_move函数
void left_move(char* arr, int k)
{
assert(arr);
int len = strlen(arr);
assert(len);//判断k是否超出数组大小
reverse(arr, arr + k - 1);//逆序左边k个元素
reverse(arr + k, arr + len - 1);//逆序右边的元素
reverse(arr, arr + len - 1);//逆序整体
}
代码
#include<stdio.h>
#include<string.h>
#include<assert.h>
void reverse(char* left, char* right)
{
assert(left);
assert(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);
assert(len);
reverse(arr, arr + k - 1);//逆序左边k个元素
reverse(arr + k, arr + len - 1);//逆序右边的元素
reverse(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;
}
拓展
做一道类似的题,帮助大家巩固
写一个函数,判断一个字符串是否为另外一个字符串旋转之后的字符串。
例如:给定s1 =AABCD和s2 = BCDAA,返回1
给定s1=abcd和s2=ACBD,返回0.
AABCD左旋一个字符得到ABCDA
AABCD左旋两个字符得到BCDAA
AABCD右旋一个字符得到DAABC
解法一:穷举,列出所有可能
void reverse(char* left, char* right)
{
assert(left);
assert(right);
while (left<right)
{
char tmp = *left;
*left = *right;
*right = tmp;
left++;
right--;
}
}
int left_move(char* arr, int k)
{
assert(arr);
int len = strlen(arr);
assert(len);
reverse(arr, arr + k - 1);//逆序左边k个元素
reverse(arr + k, arr + len - 1);//逆序右边的元素
reverse(arr, arr + len - 1);//逆序整体
}
int is_left_move(char* s1, char* s2)
{
int len = strlen(s1);//求字符串长度,来判断有多少种可能性
int i = 0;
for (i = 0; i < len; i++)
{
left_move(s1, 1);//左旋的每种可能
int ret =strcmp(s1, s2);//比较二者是否相等
if (ret == 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\n");//是
}
else
{
printf("no\n");//不是
}
return 0;
}
解法二:双倍数组
创建两个数组,如果要对比的字符串,是这个大的数组的子集,那就符合要求,不然就不符合要求
is_left_move函数的实现
int is_left_move(char* s1, char* s2)
{
int len2 = strlen(s2);
//分为两步:
//1.在str1字符串中再放一个str1字符串,要确保str1足够大,并且str1一定要确定数组大小,不然在使用srtncat函数的时候会报错
// strnact函数:字符串操作函数
int len1 = strlen(s1);
if (len1 != len2)
{
return 0;
}
strncat(s1, s2, len1);
//2.判断str2指向的字符串是否是str1指向的字符串的子串(类似子集)
//strstr:找子串的函数
char* ret = strstr(s1, s2);
if (ret == NULL)
{
return 0;
}
else
{
return 1;
}
return 0;
}
单独说明:
此处单独说明三个比较重要的函数:
stract与strnact
strcat:字符串操作函数,需要包含头文件<string.h>
语法格式:
stract(s1, s2);//把后者追加到前者的后面
但是,要注意自己追加自己是不能使用这个函数的,程序会直接报错
简单的解释一下:
我们创建两个数组,分别存储abc\0和def\0
想要追加的话,首先,要找到第一个字符串中的\0,然后用’d‘取代\0,之后存入ef\0,遇到\0说明追加结束,
而如果想要自己追加自己,我们还是要先找到\0,然后再放入abc,但当我们想放入\0时,却发现原来字符串中的\0已经被我替换成’a‘了,这样追加永远无法结束,程序崩溃~
那么我们可以使用strnact函数
语法格式
strnact(s1, s2, len)
此处简单的说明一下吧,strnact比stract多了一个参数
下图是二者的函数
strnact函数多了一个count参数
前者是直接追加,遇到\0,就停止追加
后者则是追加count位字符之后停止追加
strstr
字符串操作函数,找后者是不是前者的子串
语法格式:
strstr(s1, s2)
返回值的说明:
如果是子串,就返回s2的首元素地址
如果不是子串,就返回空指针NULL
小疑问
代码此时看起来已经可以运行了,但是小明这时候提出了一个疑问:
如果s2是cdef,输出结果是什么
输出结果是yes
这就是问题所在,所以我们在使用那些库函数之前,先要进行一个判断:s1和s2的长度是否相等,如果相等再去判断,如果不等,直接返回0结束判断。
最终代码:
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<string.h>
#include<assert.h>
int is_left_move(char* s1, char* s2)
{
int len1 = strlen(s1);
int len2 = strlen(s2);
if (len1 != len2)
{
return 0;
}
strncat(s1, s2, len1);
char* ret = strstr(s1, s2);
if (ret == NULL)
{
return 0;
}
else
{
return 1;
}
}
int main()
{
char arr1[50] = "abcdef";//此处不能使用指针,因为使用指针变量的话,它就是常量,是不能改变的
char arr2[] = "cdefab";
int ret = is_left_move(arr1, arr2);//接收返回值来判断是否是
if (ret == 1)
{
printf("yes\n");//是
}
else
{
printf("no\n");//不是
}
return 0;
}
结语
本来是想整理五道题再发的,但现在刚写两道就四千多字了,那我想还是发出去吧,毕竟字符串左旋也比较经典,就单独列出一篇来。文章来源:https://www.toymoban.com/news/detail-649052.html
希望对各位有帮助,我们下次见文章来源地址https://www.toymoban.com/news/detail-649052.html
到了这里,关于C语言题目的多种解法分享 2之字符串左旋和补充题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!