一篇文章搞定字符串的旋转问题（数组旋转问题）！

叁歲伎倆 2024-03-29 14:24 5阅读 0赞

**目录**

### 前言 ###

### 一.如何实现字符串的旋转？ ###

### 1.用冒泡的思想实现 ###

### 2.分别逆序左右再整体逆序来实现 ###

### 二.如何快速判断一个字符串是否为另外一个字符串旋转之后的字符串？ ###

### 1.相关库函数的简略学习 ###

### 2.利用库函数快速实现判断 ###

### 总结 ###

--------------------

> 博客主页：[张栩睿的博客主页][Link 1]
> 
> 欢迎关注：点赞+收藏+留言
> 
> 系列专栏：[c语言学习][c]
> 
>  **家人们写博客真的很花时间的，你们的点赞和关注对我真的很重要，希望各位路过的朋友们能多多点赞并关注我，我会随时互关的，欢迎你们的私信提问，也期待你们的转发！**
> 
>  **希望大家*****关注我，*****你们将会看到更多精彩的内容！！！**

## 前言 ##

家人们在刷题的时候也许会碰到旋转数组的问题，这篇文章就来彻底教会你字符串的旋转！

## 一.如何实现字符串的旋转？ ##

我们先来看看这道题目：

![99663801e08143e99b0c2b4b76a84d67.png][]

题目要求我们实现字符串的旋转，这个时候我们会想到我们之前学的排序：冒泡排序。

### 1.用冒泡的思想实现 ###

![de0fb9eff5164803a9c07e1bbae66944.png][]

对于左旋转的题型，我们可以将第一个元素取出来，让后面的元素依次冒泡向前移动，最后将第一个元素放到最后去，这就实现了一次旋转，我们在通过循环就可以实现字符串的旋转。对于右旋转问题，改变方向即可。代码实现如下:

方法一：
    void left_move(char arr[], int k)
    {
    	int len = strlen(arr);
    	k %= len;
    	int j = 0;
    	for (int i = 0; i < k; i++)
    	{
    		char tmp = arr[0];
    		for (j = 0; j < len - 1; j++)
    		{
    			arr[j] = arr[j + 1];
    		}
    		arr[j] = tmp;
    	}
    }
    int main()
    {
    	char arr[] = "abcdef";
    	int k = 8;
    	left_move(arr, k);
    	printf("%s\n", arr);
    	return 0;
    }

对于这里的k%=len，是因为该字符串最多旋转他本身长度这么多次，超过他的长度次的旋转会导致重复计算，所有我们将取余来去掉重复操作。

### 2.分别逆序左右再整体逆序来实现 ###

这里有一种奇妙方法来实现逆序，我们来看看图解：

![fa6f9dda654e4e45b920615f1dd6a30c.png][]

我们通过旋转的长度，来把字符串分为左右两组，然后让他们分别逆序，在整体逆序就可以实现旋转，大家要注意，这种方法虽然很难理解其中的原因，**但是在其他题中也可能会用到**，一定要掌握他！代码实现如下：

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)
    {
    	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[])
    {
    	int len1 = strlen(arr1);
    	int len2 = strlen(arr2);
    	if (len1 != len2)
    		return 0;
    	int i = 0;
    	for (i = 0; i < len1; i++)
    	{
    		left_move(arr1, i);
    		if (strcmp(arr1, arr2) == 0)
    		{
    			return 1;
    		}
    	}
    
    	return 0;
    }

### 1.相关库函数的简略学习 ###

## strncat函数 ##

该函数的作用是是将两个字符串连接在一起，用法如下：

>     int main()
>     {
>     	char arr[20] = "hello ";
>     	strncat(arr, "world", 5);
>     	printf("%s\n", arr);
>     
>     	return 0;
>     }
> 
> ![d3f8a6c9cd1d4d8784432bc386ea0b2b.png][]
> 
> 括号内是将第二个字符串追加到第一个数组中，并保存在该数组中，后面的数字表示第二个字符串存入数组的字符个数。

## strstr函数： ##

该函数的作用是寻找第二个字符串是否存在于第一个字符串中。

int main()
    {
    	//是在arr1字符串中查找arr2是否存在
    	//如果存在则返回arr2在arr1中的地址
    	//如果不存在返回NULL
    	char arr1[] = "abcdefabcdef";
    	char arr2[] = "def";
    
    	char *ret = strstr(arr1, arr2);
    	if (ret == NULL)
    	{
    		printf("NO\n");
    	}
    	else
    	{
    		printf("%s\n", ret);
    	}
    	return 0;
    }

在arr1字符串中查找arr2是否存在  
如果存在则返回arr2在arr1中的地址  
如果不存在返回NULL

### 2.利用库函数快速实现判断 ###

那么，我们学了这两个函数有什么用呢？其实啊，我们通过循环会发现，如果旋转他的长度那么次，就会得到原字符串，那么我们将该字符串循环一遍，比如abcd变成abcdabcd，你就会惊奇的发现，所有的旋转结果都可以在这个字符串中找到。所以对于旋转字符串，最简洁的方法就是将他重复一遍，在其中寻找旋转字符串。代码实现如下：

int is_left_move(char arr1[], char arr2[])
    {
    	int len1 = strlen(arr1);
    	int len2 = strlen(arr2);
    	if (len1 != len2)
    		return 0;
    	strncat(arr1, arr1, len1);
    	if (strstr(arr1, arr2) != NULL)
    		return 1;
    	else
    		return 0;
    }
    //AABCDAABCD
    int main()
    {
    	char arr1[20] = "AABCD";
    	char arr2[] = "ABCDA";
    	int ret = is_left_move(arr1, arr2);
    	if (ret == 1)
    	{
    		printf("YES\n");
    	}
    	else
    	{
    		printf("NO\n");
    	}
    	return 0;
    }

### 总结 ###

通过旋转字符串我们又复习了一下循环的使用，之前逆序的写法，还学习了两个库函数。辛苦各位小伙伴们动动小手，三连走一波最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！

[Link 1]: https://blog.csdn.net/qq_74310471?spm=1000.2115.3001.5343
[c]: https://blog.csdn.net/qq_74310471/category_12157207.html?spm=1001.2014.3001.5482
[99663801e08143e99b0c2b4b76a84d67.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/71d94fa0a3f34249acc271b67f0ee54e.png
[de0fb9eff5164803a9c07e1bbae66944.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/a3fb564ac8b744438508cad65bc36a4a.png
[fa6f9dda654e4e45b920615f1dd6a30c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/b3b286757afa4a108e3ed40aa69e5275.png
[d3f8a6c9cd1d4d8784432bc386ea0b2b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/bedd21c1860a4e3fadf7aeeb12d1fde8.png