左旋字串

/***********************************************************************
目的：實作一個函式，可以左旋字串中的k個字符，例如：
ABCD左旋一個字符得到BCDA
ABCD左旋兩個字符得到CDAB
分析：假設一個字串里要左旋2次：
? 第一種方法（暴力移位法）：

? 第二種方法（三步翻轉法）：

平臺：Visual studio 2017 && windows
*************************************************************************/
📝 實作代碼1

#include<stdio.h>
#include<assert.h>
#include<string.h>
void string_left_rotation(char* str, int k)
{
	assert(str);
	int len = strlen(str);
	int i = 0;
	//一次回圈左旋一個字符
	for(i = 0; i < k; i++) 
	{
		//拷貝
		char temp = *str;
		//覆寫字符
		int j = 0;
		for(j = 0; j < len - 1; j++)
		{
			*(str + j) = *(str + j + 1); 
		}
		//將拷貝的字符拿上來
		*(str + len - 1) = temp;
	}
}
int main()
{
	char arr[10] = "ABCDEF";
	int k = 2;
	string_left_rotation(arr, k);
	printf("%s\n", arr); 
	return 0;
}

📝 實作代碼2

#include<stdio.h>
#include<assert.h>
#include<string.h>
void reverse(char* left, char* right)
{
	assert(left && right);
	while(left < right)
	{
		char temp = *left;
		*left = *right;
		*right = temp;
		left++;
		right--;
	}
}
void string_left_rotation(char* str, int k)
{
	assert(str);
	int len = strlen(str);
	reverse(str, str + k - 1);//第一部分
	reverse(str + k, str + len - 1);//第二部分
	reverse(str, str + len - 1);//整體
}
int main()
{
	char arr[10] = "ABCDEF";
	int k = 10;
	//我們當前寫的這個代碼是不適用于旋轉的字符k大于目標陣列的arr，所以如果k大于arr時，我們需要看看k有幾個arr,并把它排除掉
	k %= strlen(arr);
	string_left_rotation(arr, k);
	printf("%s\n", arr);
	return 0;
}

🧿拋磚引玉

/***********************************************************************
目的：寫一個函式判斷一個字串是否為另外一個字串旋轉(左旋或右旋)之后的字串，例如：
1、 S1 = AABCD 和 S2 = BCDAA，回傳1
2、 S1 = abcd和 S2 = ABCD，回傳0
分析：
? 第一種方法：
只要每左旋一次字串并比較兩字串是否相等即可

? 第二種方法（庫函式yyds）：
我們發現字串追加自己后，可以找到所以旋轉后的可能性

平臺：Visual studio 2017 && windows
*************************************************************************/
📝 實作代碼1

#include<stdio.h>
#include<assert.h>
#include<string.h>
int is_string_rotation1(char* str1, char* str2)
{
	assert(str1 && str2);
	int len = strlen(str1);
	int i = 0;
	//一次回圈左旋一個字符
	for(i = 0; i < len; i++) 
	{
		//拷貝
		char temp = *str1;
		//覆寫字符
		int j = 0;
		for(j = 0; j < len - 1; j++)
		{
			*(str1 + j) = *(str1 + j + 1); 
		}
		//將拷貝的字符拿上來
		*(str1 + len - 1) = temp;
		//每次旋轉一個字符后比較一次
		if(strcmp(str1, str2) == 0)
		{
			return 1;
		}
		
	}
	return 0;
}
int main()
{
	char arr1[] = "AABCD";
	char arr2[] = "BCDAA";
	int ret = is_string_rotation1(arr1, arr2);
	if(1 == ret)
	{
		printf("Yes\n");
	}
	else
	{
		printf("No\n");
	}
	return 0;
}

📝 實作代碼2

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<assert.h>
#include<string.h>
int is_string_rotation2(char* str1, char* str2)
{
	assert(str1 && str2);
	//str1追加str1(注意字串自己追加自己時不能用strcat，應為它會將'\0'覆寫掉；而strncat在追加完后會補'\0')
	int len = strlen(str1);
	strncat(str1, str1, len);
	//判斷str2是否為str1的子串
	char* ret = strstr(str1, str2);
	return ret != NULL;//同下
	
	/*if(ret == NULL)
	{
		return 0;
	}
	else
	{
		return 1;
	}*/
}
int main()
{
	char arr1[20] = "AABCD";
	char arr2[] = "BCDAA";
	int ret = is_string_rotation2(arr1, arr2);
	if(1 == ret)
	{
		printf("Yes\n");
	}
	else
	{
		printf("No\n");
	}
	return 0;
}

?? 代碼2其實是有問題的：
str1：A A B C D A A B C D
str2：B C D
Yes
str2一定是str1的子串，但是str1一定不是str2旋轉得來的

/***********************************************************************
目的：修改代碼2中的bug
分析：我們發現當str2與str1長度不相等時，那么一定不可能是旋轉得來的
平臺：Visual studio 2017 && windows
*************************************************************************/
📝 修改代碼2

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<assert.h>
#include<string.h>
int is_string_rotation2(char* str1, char* str2)
{
	assert(str1 && str2);
	//修改處
	if(strlen(str1) != strlen(str2))
	{
		return 0;
	}
	//str1追加str1(注意字串自己追加自己時不能用strcat，應為它會將'\0'覆寫掉；而strncat在追加完后會補'\0')
	int len = strlen(str1);
	strncat(str1, str1, len);
	//判斷str2是否為str1的子串
	char* ret = strstr(str1, str2);
	return ret != NULL;//同下
	
	/*if(ret == NULL)
	{
		return 0;
	}
	else
	{
		return 1;
	}*/
}
int main()
{
	char arr1[20] = "AABCD";
	char arr2[] = "BCDAA";
	int ret = is_string_rotation2(arr1, arr2);
	if(1 == ret)
	{
		printf("Yes\n");
	}
	else
	{
		printf("No\n");
	}
	return 0;
}