旋转字符串的秘密
最近离谱张童鞋对字符串旋转,翻转等问题非常感兴趣,看了些视频以及做了一些题目,现在有一些新的想法以及后续学习的目标以及规划要分享给大家.
目录:
1：介绍一下整体旋转字符串的2种方法
2：旋转单个字符,设计一个函数(两种方法,第一种是设计函数第二种是三步翻转法:特别巧妙,这里将会画图详细介绍.
3：题目1：旋转一个字符串然后单词也逆序.:
4：查找字符串,本题会把思路和代码详细的讲一遍.
好，接下来咱们先看这样一个问题
题目 :完成对一个字符串的逆序.
示例:abcd
输出:dcba
(偶数个)
示例:abcde
输出:edcba
(奇数个)
思路1:可以用循环来实现,把b一个字符串传入数组中,既然是数组,就可以用访问下标的形式来进行访问了,然后再倒序输出就行了
废话不多说,直接上代码(别急每一条代码后面有注释喔)
/*
方法1:for循环倒序输出:
思路:和倒序输入数字一样的,直接倒序打印就可以
*/
//已在编译器上测试过,没问题
#include <stdio.h>
#include <string.h>
int main()
{
char s[1000]={0};//创建一个数组用来存放字符串,大小的话,注意题目规范,还有变量初始化,好习惯一定要养成
scanf("%s",s);//输入字符串,也可以用gets
int n=strlen(s);//求出有几个字母,顺便可以算出下标
int i=0;//变量初始化,一定别忘了喔
for(i=n-1;s[i]!='';i--)//从最后一个字母的下标开始倒序输出.
{
printf("%c",s[i]);
}
return 0;
}
总结:这就是思路1啦,不难理解,接下来我们看思路1(2).
/*
方法2:也是用循环来完成的,但不过这个是用数组来实现字符串交换的,和这个题目有一些些相似,但是本质也还是相同的
这个和鹏哥之前的字符串汇聚蛮相似的,所以我想把他们放到一起来看
*/
//已在编译器上测试过,没问题
#include<stdio.h>
#include<string.h>
int main()
{
char arr[1000]={0};
int left=0,right=0,i=0;
scanf("%s",arr);//输入字符串的时候用gets也是可以的哟
int n=strlen(arr);//这样我是把这样条件都一股脑的写在了for循环里面,大家也可以写在外面
for(left=0,right=n-1;(right-left)>0;left++,right--)
{
/*
1:这里注意一点就是,right-left>1可以不可呢?答案是不可以,因为如果你交换的是偶数的话,第五和第六个元素,6-5=1,条件不满足,就退出来了,所以还是当右下标大于左下标的时候,这样就可以啦
2:然后就可以实现字符串的交换了哟
先创建一个临时变量用来存放左下标的元素.这就和交换三个数是一模一样的,大家类比就好啦
由于交换的是字符类型,所以,一定得用char型来创建临时变量的哟
*/
char t=0;
t=arr[left];
arr[left]=arr[right];
arr[right]=t;
}
//交换完毕之后,最后打印出来就好啦
printf("%s",arr);
return 0;
}
现在我们来回顾一下字符串汇聚的那个题目把:题目所示:
编写代码，演示从多个字符从两段移动，向中间汇聚。
思路如下（字多，详细，请大家耐心阅读）：
比如我让arr2的#号变成welcome bit
首先得创建两个数组arr1和arr2来存储这两个字符串儿
然后字符串的话,已经存放到了数组里面了,然后就可以采用访问数组下标的形式,定义左下标为0,右下标为sz-1.
,但是他不能算sz,因为他是个字符串,这时候就要了解一下strlen函数了,str是string是字符串,len是lengh是表示长度的的意思,所以,这个是strlen函数是这么由来的
那么所以left和right都应该等于什么呢？
int left=0;
int right=strlen(arr2)-1;
首先明确题目,是让arr1的每一个元素来传到arr2中对吧,所以就是让arr1的左下标来放入到arr2的左下标,同理的右坐标也是一样的.
因为咱们是每传一次,咱们看一下他这个变化对吧,就是在交换了之后面加一个打印就行了,
然后这个是一次,我让left++,和right减减,他是不是就可以向中间汇聚了呢？
所以是不是得加一个while循环啊,是不是,这个和二分查找是一样的,二分查得查找很多次啊.
好了,思路以及有了,代码如下
#include <stdio.h>
#include <stdio.h>
#include <string.h>
//已经在编译器上测试过
int main()
{
char arr1[]="welcome bit";
char arr2[]="###########";
int left=0;
int right=strlen(arr2)-1;
while(left<=right)
{
arr2[left]=arr1[left];//一定要注意,不是(),是[]
arr2[right]=arr1[right];
printf("%sn",arr2);//这样就每打印一行,加一下,效果是从中间汇聚的.
// sleep(1000);//手机上不能实现,停留,因为手机没有windows.h
left++;
right--;
}
return 0;
}好了,回过神来了,好了这个数组交换的方法,大家肯定会了,然后现在来看函数是如何实现的吧
方法三,用一个函数来实现,这个函数我们就把他定义为字符交换函数把,
字符交换函数
思路就是:要想交换一个字符串,就得把这个字符串的首尾地址传给这个交换函数,然后用指针的形式来进行交换,而我们定义的这个函数就得用两个指针来进行接收啦
好了,这个思路大致有了以后,咱们就来说敲代码了嗷
(1):首尾地址>可以用数组名来表示,因为数组名就代表着首元素的地址,而末尾元素的地址,则是字符串长度-1
(2):当把参数传给自定义函数里面,我们可以用左下标指针和右下标指针来进行接收他们,
(3)可以用while循环,或者是for循环来进行交换,
那条件是什么呢,我们可以这样想,就是当我们的左下标<=右下标的时候,这样是不是就停止了交换了呢？
好，思路有了，代码如下：
#include<stdio.h>
#include<string.h>
void my_string_reverse(char*left,char*right)
{
//交换,这里的*和[]是一样哒
while(left<right)
{
char t=*left;
*left=*right;
*right=t;
//交换这一步一定要写对
left++;
right--;
}
}
int main()
{
char arr[1000]={0};//好习惯的初始化
scanf("%s",arr);
int n=strlen(arr);
my_string_reverse(arr,arr+n-1);//传首尾元素的地址
//完成之后呢,我们来打印一下就ok啦,来看看他是否完成了交换
printf("%s",arr);
return 0;
}ok,这是整体交换的方法,我们再来聊聊,更近一步的,如何才能使交换一串儿字符的两个字符呢？这样可以是左交换,或者是右交换;
题目如下:加照片
其实每一个题目的思路都可以是这样的，首先要明确题目内容是什么,要把某个东西干什么,最终要完成什么目的,可以用到的工具是什么,依次来进行思路的搭建,
交换一个字符串中的两个(k个)字符,也称为左旋字符串.
要旋转的字符串会发生改变,所以我们可以存放在数组中,因为数组元素才可以被改变,
万万不可用char*p="ABCDEF"来改变常量字符串.
然后我们就要自定义函数啦,my_string_left(arr,k)再把arr这个数组传过去,k为旋转的个数,
然后用char*str来接收arr,int k来接收k.
既然传参部分都解决了,那么我们就开始想他如何实现吧,
现在有一个字符串ABCDEF,旋转的话我们可以这样想,把其中的一个A字母用一个临时变量存起来,然后BCDEF整体往前移动,往前移动嘛,那就是用一个for循环a[i-1]=a[i](如果是下标为0的，格式还可以这么写a[i]=a[i+1]就可以搞定啦,
最后在这个循环里面完成交换之后,把这个临时变量再放回到最后一位就行了。
好了，这就是大体思路,现在我们转为代码看看呗,
#include<stdio.h>
#include<string.h>
void my_string_left(char*str,int k)
{
int i=0,j=0;//初始化
int n=strlen(str);//st为首元素的地址,这里不懂的话,可以去查一查strlen接收的参数类型,这里为大家奉上:unsigned int strlen(const char *str);很明显,str是字符型指针,一会儿得接收地址
for(i=0;i<k;i++)//在for循环里面完成交换,一共有n个元素,现在拿出去第一个元素用于以后的存放,还剩下n-1要向前移动,然后要想把长度求出来,就得用strlen来求一下
{
char t=*str;//首先:把第一个元素存放到一个临时变量里面,放到for循环里面的目的是为了本次循环结束之后,下次循环,获得的是新的一个字符,如果放在for循环外面的话,每次获取的斗只是第一个字符
for(j=0;j<n-1;j++)
{
*(str+j)=*(str+j+1);//其次:这里的*(str)是解引用,把找第一个元素的地址来找到第一个首元素,而且不能没有*str,如果没有首元素的地址那你怎么能找到末尾的元素呢？
}
//最后:空出的这个位置有了,那就存放第一个元素吧
*(str+n-1)=t;
}
}
int main()
{
char arr[1000]={0};//初始化,好习惯
scanf("%s",arr);//输入字符串的时候，可不需要取地址喔，而且还可以用gets
int k=2;//把要旋转的字符传过去
//传左旋
my_string_left(arr,k);//自定义函数
printf("%s",arr);//最后打印
return 0;
}好的,那么既然左旋会了,那右旋是不是也一样呢,这里大家先自行思考一会儿,不许看代码喔嘿嘿
右旋:同左旋一一模一样的,稍微改变一下就行.
大家自行思考，再看代码
右旋字符串
#include <stdio.h>
#include<string.h>
void my_string_right(char*str,int k)
{
int i=0,j=0;
int n=strlen(str);//str为首元素的地址,这里不懂的话,可以去查一查strlen接收的参数类型,这里为大家奉上:
for(i=0;i<k;i++)//第二步,在for循环里面完成交换,一共有n个元素,现在拿出去第一个元素用于以后的存放,还剩下n-1要向后移动,然后要想把长度求出来,就得用strlen来求一下
{
char t=*(str+n-1);//首先把最后一个元素存放到一个临时变量里面,放到for循环里面的目的是为了本次循环结束之后,下次循环,获得的是新的一个字符,如果放在for循环外面的话,每次获取的只是第一个字符
for(j=n-2;j>=0;j--)
{
*(str+j+1)=*(str+j);//往后移动啦
}
//第三步:空出的这个位置有了,那就存放最后一个元素吧
*(str)=t;
}
}
int main()
{
char arr[1000]={0};
scanf("%s",arr);//输入字符串的时候，可不需要取地址喔，而且还可以用gets
int k=2;//把要旋转的字符传过去
//右旋两个
my_string_right(arr,k);//自定义函数喔
printf("%s",arr);
return 0;
}好了，思路回来,以上的两个代码,都是旋转一个字符串的左边或者右边的两个字符,但是我们这样想一下,右旋一个字符=左旋三个字符
eg1:
abcd >> 右旋一个 >>dabc
== 左旋三个>>dabc
eg2:
abcd >> 右旋二个>>cdab
== 左旋六个>>cdab
已经测试过了,没问题的.兄弟们,放心用
接下来让我我们回到那个最初的问题上…
接下来给大家介绍一种方法,三步翻转法,这样也可以进行字符串的翻转,很妙,很值得品味
三步翻转法
1左翻转
2右翻转
3整体翻转
如图所示:
#include <stdio.h>
#include<string.h>
void my_string_right(char*str,int k)
{
int i=0,j=0;
int n=strlen(str);//str为首元素的地址,这里不懂的话,可以去查一查strlen接收的参数类型,这里为大家奉上:
for(i=0;i<k;i++)//第二步,在for循环里面完成交换,一共有n个元素,现在拿出去第一个元素用于以后的存放,还剩下n-1要向后移动,然后要想把长度求出来,就得用strlen来求一下
{
char t=*(str+n-1);//首先把最后一个元素存放到一个临时变量里面,放到for循环里面的目的是为了本次循环结束之后,下次循环,获得的是新的一个字符,如果放在for循环外面的话,每次获取的只是第一个字符
for(j=n-2;j>=0;j--)
{
*(str+j+1)=*(str+j);//往后移动啦
}
//第三步:空出的这个位置有了,那就存放最后一个元素吧
*(str)=t;
}
}
int main()
{
char arr[1000]={0};
scanf("%s",arr);//输入字符串的时候，可不需要取地址喔，而且还可以用gets
int k=2;//把要旋转的字符传过去
//右旋两个
my_string_right(arr,k);//自定义函数喔
printf("%s",arr);
return 0;
}好啦,到这里,旋转字符串,不管是多个,还是任意个字符的旋转,大家肯定都会了,然后来一道题目来巩固一下吧
题目如下:
方法一:暴力穷举法:把能想到的可能都列出来,然后进行一一比对
就是判断s2是否由s1旋转得到的,就可以让s1先旋转一个,比一下,然后再旋转一个,比一下,这里用for循环就可.
外层for循环每次循环一次,就说明了已经完成了一次交换,这时候用strcmp函数来比较一下,看看是否相等,如果相等的话呢？那就跳出来就好了啦
#include <stdio.h>
#include <string.h>
#include <assert.h>
char is_pd_string_rotate(char*str1,char*str2)//最前面的类型,char可以,int也可以
//char*str1来接收arr1,char*str2来接收arr2
{
assert(str1);
assert(str2);
int i=0,j=0;
int n=strlen(str1);
for(i=0;i<n;i++)
{
char t=*str1;//第一步:记录起始位置
for(j=0;j<n-1;j++)
{
*(str1+j)=*(str1+j+1);//第二步往前移动:就是前面的比后面的小,那就往前移动
}
*(str1+n-1)=t;//第三步:把第一个元素放在最后面
//每一次完了之后进行一次比较,如果相同,那就返回1就好了啦
if(strcmp(str1,str2)==0)
{
return 1;
}
}//这层for循环如果停止的话,说明已经旋转了每一个了,就没有匹配的,说明s2不是由s1旋转的来的,那咱们return 0就好了
return 0;
}
int main()
{
char arr1[]="AABCD";//记得数组一定一定要初始化喔
char arr2[]="BCDAA";
int ret=is_pd_string_rotate(arr1,arr2);
if(ret==1)
{
printf("yes");
}
else
{
printf("no");
}
return 0;
}好了,到这里,我们的代码就实现啦,还有一个注意点就是这个如图,大家一定写函数类型的时候要小心,一定要小心谨慎
不要犯我这个小错误
方法二:追加自己的字符串，判断字符串是否包含的问题
思路:就是我们能不能把这一个字符串来变化一下,让它包含所有的情况呢？,答案是可以的,
首先:我们用字符串追加就可以了。
其次:到了最后，判断arr2是不是arr1的子串儿就好了。
#include <stdio.h>
#include <string.h>
#include <assert.h>
char is_pd_string_rotate(char*str1,char*str2)//char可以,int也可以
{
assert(str1);
assert(str2);
if(strlen(str1)!=strlen(str2))
{
//二者长度不一样,肯定旋转返回0就ok了
return 0;
}
//首先进行了字符串的追加,
int len=strlen(str1);
strncat(str1,str1,len);
//完成之后用strstr函数来看看是不是子串儿,如果是子串儿的话,就返回空指针(具体的话,大家可以自行查一下strstr函数
char*ret=strstr(str1,str2);
if(ret==NULL)
{
return 0;//那就是找不到子串儿
}
else
{
return 1;//如果找到了,那就返回1
}
//此时还有一个例外就是,如果他们的字符串长度原本就不想等,那么肯定不是旋转得来的
//所以啊,在前面加一个if判断就好了啦
}
int main()
{
char arr1[]="AABCD";//记得数组一定一定要初始化喔
char arr2[]="BCDAA";
int ret=is_pd_string_rotate(arr1,arr2);
if(ret==1)
{
printf("yes");
}
else
{
printf("no");
}
return 0;
}总结：本题用了C语言的库函数比较多，所以在执行方面和书写方面会比较快。比前面的自定义函数方便一些。
============================================================
接下来,我们来看下一道题吧(大家先自行思考10min再看代码)
题目如图所示:
先说整体思路：
思路:1先写一个可以逆序的函数(咱们之前的文章已经有啦)(把这一句话的首元素地址和末尾元素的地址传过去)
2传过去之后,那就看看单个单词的逆序就好啦,
具体思路:
先把整个字符串逆序，设计了一个翻转函数，然后再逆序每一个单词，要逆序单词的话，就得有每一个单词的下标，
要下标的话，得拿指针（或者left，right下标来算，做法是最后把下标传递给数组来算的。然后就是用到找下标的
方法了，找下标的话，如果遇到’’的话那就是最后一个单词的末尾了，然后接下来就是每一个单词的后面的空格了
，如果循环到不等于空格的时候，那就继续往下找，直到遇到一个单词的空格，那就开始走else了，else的话，传的
就是左下标为0和右下标减一，这样就是这一个单词的逆序了，然后else完了之后，走for循环right＋＋，这样就是
下一个单词了，依次类推，就完成了逆序。
方法是用到了for循环和数组来进行逆序
但是本质还是找到这个单词逆序的关键点还有如何找到下一个单词，以及空格和的处理
#include <stdio.h>
#include <string.h>
void my_string_fz_reverse(char a[],char left,char right)
{
//for前面的条件1就是char left来接受的0,和char right 接受的n-1
for(;(right-left)>0;)//条件3是放到了后面,当然兄弟们放到前面也行
{
char t=a[left];
a[left]=a[right];
a[right]=t;
left++;
right--;
}
}
int main()
{
char s[10000]={0};//初始化为0,好习惯
gets(s);
int n=strlen(s);
//一次性传3个元素,1数组,因为上面要用for循环来实现翻转;2left左下标,3:right右下标
my_string_fz_reverse(s,0,n-1);
int left,right;
for(left=0,right=0;s[right]!='';right++)
{
//接下来的if如果不对懂的话,前面有详细的叙述,兄弟们可以翻过去好好看看
if(s[right]!=' ')
continue;
else
{
my_string_fz_reverse(s,left,right-1);
left=right+1;
}
}
my_string_fz_reverse(s,left,right-1);
printf("%s",s);
return 0;
}好啦，这就是方法一。
再来看方法二：
方法二:指针加循环和方法一差不多,只是换一种形式而已
#include<stdio.h>
#include<string.h>
void reverse(char*left,char*right)
{
while(left<right)
{
char t=*left;
*left=*right;
*right=t;
left++;
right--;
}
}
int main()
{
char arr[1000]={0};
int left,right;
get(arr);//输入一串儿单词
int n=strlen(arr);
reverse(arr,arr+n-1);//这是交换整体的逆序
// 然后再进行单个单词的逆序,就得用双指针
char*start=arr;
while(*start)
{
char*end=start;
while(*end!=' ' && *end!='')
{
end++;//这样是地址的++,然后指向下一个地址;然后才能以便后续的解引用来进行找到元素
}
reverse(start,end-1);
if(*end==' ')
start=end+1;
else
start=end;
}
printf("%s",arr);
return 0;
}好了，这就是今天的内容了，最后这个题跟今天内容没有关系，但是可以很好的去锻炼我们的思维：
题目如下：
用三层for循环来进行一步一步的筛选
前提是注意for里面的内层嵌套还有if的使用
如果在本字符串中找到一个c,那就看看下一个是不是h,如果是h,那再看看是不是n,如果他们都满足的话,count++,这个一个chn,同理其他情况.
如图所示：
方法一：三层for循环的嵌套以及if语句和continue的用法
/*
方法一：用三层for循环来进行一步一步的筛选
前提是注意for里面的内层嵌套还有if的使用
eg：要找CCHNCHN中的CHN的个数，先找C，然后再进行判断，下一个字母如果是H，就往下走，如果不是的话，
就第一层for循环在进行下一个单词的查询，当找到H之后，再定位到下一个单词看看是不是N，如果是N的话，
那就count++，进行基数，如果第一个H的后面仍然有N的话，那z循环就会继续往后找，continue的作用就是
这样，跳过本次循环，进行下一次循环，如果下一次循环条件满足的话，就进行判断，再看看是否满足z循环，
*/
#include <stdio.h>
int main()
{
int count=0,i=0,j=0,z=0;
char s[100]={0};
scanf("%s",s);
for(i=0;s[i]!='';i++)
{
if(s[i]!='C')
continue;
if(s[i]=='C')
{
for(j=i+1;s[j]!='';j++)
{
if(s[j]!='H')
continue;
if(s[j]=='H')
{
for(z=j+1;s[z]!='';z++)
{
if(s[z]!='N')
continue;
if(s[z]=='N')
count++;
}
}
}
}
}
printf("%d",count);
return 0;
}/*方法二：要查找一个字符串对吧,可以用指针来指向这个字符串,然后用for循环,或者if循环来挨个指向
比如还是要查找CCHNCHN中有几个CHN
C C H N C H N
0 1 2 3 4 5 6
进入循环，*p指向的是第一个元素，不是0，所以往后走
紧接着是if的判断部分，第一个C,说明找到了，c=1，跳出循环，p++开始指向下一个元素，还是C，然后c变成
2了，再p++往后找，发现第三个是H，走else if 此次的ch=2，然后p++开始找第二个元素，，发现是N,然后
此时的CHN=2，再往下走，发现指向了C，此时的c变成了3，然后继续走，遇到了N，此时此刻的CH=2+3=5，最
后一个字符遇到了N，然后走CHN，这个语句，现在的CHN=2+5=7，所以就是7个CHN啦。
*/
#include<stdio.h>
int main()
{
int c=0;
long int ch=0;
long long int chn=0;
char arr[100]={0};
scanf("%s",arr);
char*p=arr;//用指针变量p来接收一个arr的数组名
while(*p)//*p会指向,因为会往后移动
{
if(*p=='C')
c++;
else if(*p=='H')
ch+=c;
else if(*p=='N')
chn+=ch;
p++;
}
printf("%d",chn);
return 0;
}
*/
#include<stdio.h>
int main()
{
int c=0;
long int ch=0;
long long int chn=0;
char arr[100]={0};
scanf("%s",arr);
char*p=arr;//用指针变量p来接收一个arr的数组名
while(*p)//*p会指向,因为会往后移动
{
if(*p=='C')
c++;
else if(*p=='H')
ch+=c;
else if(*p=='N')
chn+=ch;
p++;
}
printf("%d",chn);
return 0;
}
好啦，这就是今天的分享的题目啦，然后可能我叙述的会有一些冗杂和重复，希望大家可以耐着性子读下去，希望本篇博客对大家有所帮助，里面的思路可以帮助大家处理一些相似的问题。