【C语言】逆置算法

目录

逆置字符串

循环版本 

递归版本 

旋转数组

暴力求解法 

反转法

结语 

  在力扣或者牛客网这些OJ刷题平台经常能够看到一些题目，要求你将字符串逆置或者旋转字符串、亦或者旋转数组。那今天就跟大家讲解一下逆置算法。首先我们来学习一下逆置字符串。

逆置字符串

循环版本 

代码示例：

#include 
#include 
 
void reverse_string(char* arr)
{
	char *left = arr;
	char *right = arr+strlen(arr)-1;
 
	while(left
	{
		char tmp = *left;
		*left = *right;
		*right = tmp;
 
		left++;
		right--;
	}
}
 
int main()
{
	char arr[] = "joyy";
	reverse(arr);
	printf("%s\n", arr);
	return 0;
}
 
 

#include 
#include 
void reverse_string(char* arr)
{
	int len = strlen(arr);
	int i = 0;
	for (i = 0; i < len / 2; i++)
	{
		char temp = *(arr + i);
		*(arr + i) = *(arr + len - 1 - i);
		*(arr + len - 1 - i) = temp;
	}
}
int main()
{
	char arr[] = "joyy";
	reverse_string(arr);
	printf("%s\n", arr);
	return 0;
}

递归版本 

代码示例： 

C语言实现逆置字符串

c 0星 超过10%的资源 278.0B

下载

#include 
#include 
 
void reverse_string(char* arr)
{
	int len = strlen(arr);
	char tmp = *arr;
	*arr = *(arr+len-1);
 
	*(arr+len-1) = '\0';
	if(strlen(arr+1)>=2) //判断条件改为strlen(arr+1)>0也行
		reverse_string(arr+1);
 
	*(arr+len-1) = tmp;
}
 
int main()
{
	char arr[] = "joyy";
	reverse_string(arr);
	printf("%s\n", arr);
	return 0;
}

  注意：上面循环的两个版本思路差不多，使用while循环的实现方式是通过指针加加减减来实现交换，而for循环的实现方式是通过下标的方式来堆成交换。 然后递归版本最需要注意的点就是：将*(str+len-1)赋给*arr后，一定要将*(str+len-1)改为'\0'以减小字符串的长度，否则无法实现递归。

旋转数组

示例：给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
示例：
输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]

暴力求解法 

分析：

代码示例：

#include 
void rotate(int* nums, int numsSize, int k)
{
	k %= numsSize;
	for (int i = 0; i < k; i++)
	{
		int temp = nums[numsSize - 1];
		for (int k = numsSize - 2; k >= 0; k--)
		{
			nums[k + 1] = nums[k];
		}
		nums[0] = temp;
	}
	
 
}
 
int main()
{
	int arr[] = { 1,2,3,4,5,6,7 };
	rotate(arr, 7, 10);
	for (int i = 0; i < 7; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

  这种方法还是比较容易想到的方法，但是它不是最优的方法。接下来，博主给大家介绍一种更加优的方法。 

将一线性链表逆置，如将(a,b,c,d)逆置为（d,c,b,a)

text/x-c 0星 超过10%的资源 997.0B

下载

反转法

分析：

  反转法主要涉及了三次逆置：第一次是前n-k个元素逆置，第二次是后k个元素逆置，第三次是整个数组逆置。所以反转法需要借助上面已经介绍到了的逆置算法。

代码示例：

void rotate(int* nums, int numsSize, int k)
{
	k %= numsSize;
	//前n-k个元素逆置
	reverse(nums, 0, numsSize - k - 1);
	//后k个元素逆置
	reverse(nums, numsSize - k, numsSize - 1);
	//整个数组逆置
	reverse(nums, 0, numsSize - 1);
 
}
 
int main()
{
	int arr[] = { 1,2,3,4,5,6,7 };
	rotate(arr, 7, 3);
	for (int i = 0; i < 7; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

  以上就是本篇博客的全部内容了，如果大家觉得有收获的话，可以给个三连支持一下！谢谢大家啦！

结语 

  每个优秀的人都有一段沉默的时光，那段时光是付出了很多努力却得不到结果的日子，我们把它叫做扎根。