三步翻转法

三步翻转法是C语言中用来求旋转字符串的一种进阶方法，我们以具体例题对其进行介绍。

例：求一个字符串左旋n个字符后得到的新字符串

普通方法实现

我们知道，左旋一个字符一共分为三步：

1. 将字符串的第一个字符存放到临时变量中；
2. 将字符串中除’\0’外的所有字符整体向前挪动一位；
3. 将tmp放在末尾’\0’的前面；

那么，我们左旋n个字符就只需要把这三步操作放在循环里面循环n次即可。

#include 
#include 
#include 

char* left_rotate(char arr[], int n)  //返回值为char*，用于实现链式访问
{
	assert(arr != NULL);
	char* ret = arr;  //记录arr的地址用于返回
	int len = strlen(arr);
	n %= len;  //使得当n大于字符串长度时我们仍只需要左旋小于len次，提高效率，也避免越界
	int i = 0;
	int j = 0;
	for (i = 0; i < n; i++)
	{
		char tmp = arr[0];   //将字符串中的第一个位置的字符拿出来
		for (j = 0; j < len - 1; j++)   //将字符串整体向前挪动一个字符('\0'不动)
		{
			arr[j] = arr[j + 1];
		}
		arr[len - 1] = tmp;  //将第一个字符放到末尾'\0'的前面
	}
	return ret;
}

int main()
{
	char arr[] = "abcdef";
	int n = 0;
	scanf("%d", &n);
	left_rotate(arr, n);  //将arr左旋n个字符
	printf("%s\n", arr);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

三步翻转法实现

三步翻转法的原理如下：假设我们要左旋字符串 “abcdef” 中的 “ab” ，那么我们只需要进行三步操作即可：

1. 翻转 “ab” ;
2. 翻转 “cdef” ;
3. 翻转这个字符串 “abcdef” ;

即 ab cdef -> ba cdef -> ba fedc -> cdef ab，用三次逆序操作实现旋转字符串，所以此方法被称作三步翻转法。

#include 
#include 
#include 

void reverse(char* left, char* right)  //逆序字符串
{
	assert(left && right);
	while (left <= right)
	{
		char tmp = *left;
		*left = *right;
		*right = tmp;
		left++;
		right--;
	}
}

char* left_rotate(char arr[], int n)   //返回值为char*，用于实现链式访问
{
	assert(arr != NULL);
	char* ret = arr;  //记录arr的地址用于返回
	int len = strlen(arr);
	n %= len;   //使得当n大于字符串长度时我们仍只需要左旋小于len次，提高效率，也避免越界
	reverse(arr, arr + n - 1);        //翻转前面n个字符
	reverse(arr + n, arr + len - 1);  //翻转后面n个字符
	reverse(arr, arr + len - 1);      //翻转整个字符串
	return ret;
}

int main()
{
	char arr[] = "abcdef";
	int n = 0;
	scanf("%d", &n);
	left_rotate(arr, n);  //将arr左旋n个字符
	printf("%s\n", arr);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

---

杨氏矩阵

杨氏矩阵的介绍

杨氏矩阵。是对组合表示理论和舒伯特演算很有用的工具。它提供了一种方便的方式来描述对称和一般线性群的群表示，并研究它们的性质。杨氏矩阵是剑桥大学大学数学家阿尔弗雷德·扬在1900年提出。然后在1903年，它被用于格奥尔格·弗罗贝纽斯的对称群研究中。它的理论得益于许多数学家的贡献得到进一步发展，包括珀西·麦克马洪，W.V.D.霍奇，G.deB.罗宾逊，吉安·卡咯罗塔，阿兰拉斯克斯，马塞尔·保罗斯库森博格和理查德·P·史丹利。（来源：百度百科）

从图像上来看，杨氏矩阵就是下面这样的矩阵：

其实，杨氏矩阵就是一个二维数组，只不过这个二维数组的每行是递增的、每列也是递增的。

例：有一个二维数组，数组的每行从左到右是递增的，每列从上到下是递增的。在这样的数组中查找一个数字是否存在。

要求： 时间复杂度小于O(N)。

我们就以上面这个二维数组为例，由于题目要求时间复杂度小于O(N)，所以我们不能通过循环便利数组元素的方式求解。

由于杨氏矩阵行从左到右是递增的，每列从上到下是递增的，所以我们可以拿矩阵中左下角或者右上角的元素与目标元素进行比较，以右上角的元素3为例，我们知道，3是这一行中最大元素，同时是这一列中最小的元素，那么如果目标元素小于3，那么我们就可以排除掉3所在这一整列，而如果目标元素大于3，我们则可以排除3所在的这一整行，这样提高效率，达到题目时间复杂度的要求。

代码实现

#include 

int find_num(int arr[3][3], int row, int col, int n)
{
	int x = 0;
	int y = col - 1;  //找到右上角的元素
	int i = 0;
	int j = 0;
	for (i = x; i < row; i++) //x
	{
		for (j = y; j >= 0; j--)  //y>=0 ：查找的边界
		{
			if (n > arr[x][y])
				x++;  //如果目标元素大于右上角元素，则x++，直接查找第二行的元素
			else if (n < arr[x][y])
				y--;  //如果目标元素小于右上角元素，则y--，直接查找前面一列的元素
			else
				return 1;  //找到返回1
		}
	}
	return 0;  //没找到返回0
}

int main()
{
	int arr[3][3] = { 1,2,3,4,5,6,7,8,9 };
	int n = 0;  //要查找的数字
	scanf("%d", &n);
	int ret = find_num(arr, 3, 3, n);
	if (ret == 1)
		printf("找到了\n");
	else
		printf("没找到\n");
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

代码完善

我们发现上面的代码虽然能够实现题目的要求，但是它的功能是不完善的，如果找到了目标元素，我们最好是能够返回目标元素所在的下标；由于二维数组的下标有两个数，所以不能通过返回值的方式直接带回，而是可以通过一些其他方式：

1. 通过结构体带回；
2. 通过指针数组带回；
3. 通过传递两个变量的地址改变变量的值来标记；
4. 通过两个全局变量实现；

虽然使用全局变量的方式十分简单，但是由于全局变量十分不安全，所以不推荐使用，这里我提供结构体带回的实现方式。

#include 

struct flag
{
	int x;
	int y;
}f;

int find_num(int arr[3][3], int row, int col, int n)
{
	int x = 0;
	int y = col - 1;  //找到右上角的元素

	//结构体变量的初始化，注意这里不要初始化为0 0，应该初始化为两个无意义的数，因为目标元素可能在0 0 处
	f.x = -1;
	f.y = -1;

	int i = 0;
	int j = 0;
	for (i = x; i < row; i++) //x
	{
		for (j = y; j >= 0; j--)  //y>=0 ：查找的边界
		{
			if (n > arr[x][y])
				x++;  //如果目标元素大于右上角元素，则x++，直接查找第二行的元素
			else if (n < arr[x][y])
				y--;  //如果目标元素小于右上角元素，则y--，直接查找前面一列的元素
			else
			{
				f.x = x;  //找到了就使用结构体记录坐标
				f.y = y;
				return 1;  //找到返回1
			}
		}
	}
	return 0;  //没找到返回0
}

int main()
{
	int arr[3][3] = { 1,2,3,4,5,6,7,8,9 };
	int n = 0;  //要查找的数字
	scanf("%d", &n);
	int ret = find_num(arr, 3, 3, n);
	if (ret == 1)
		printf("arr[%d][%d] = %d\n", f.x, f.y, n);
	else
		printf("没找到\n");
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

---

辗转相除法

欧几里得算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式是：

gcd(a,b) = gcd(b,a mod b);
1

注：最小公倍数的计算公式如下：

lcm(a,b) = a*b/gcd(a,b);
1

假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里得算法，是这样进行的：

1997 / 615 = 3 (余 152)

615 / 152 = 4(余7)

152 / 7 = 21(余5)

7 / 5 = 1 (余2)

5 / 2 = 2 (余1)

2 / 1 = 2 (余0)

至此，最大公约数为1

以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 1997 和 615 的最大公约数 1。

代码实现（循环版本）

#include 

int gcd(int m, int n)
{
	int rem = 0;
	while (n > 0)
	{
		rem = m % n;
		m = n;
		n = rem;
	}
	return m;
}

int main()
{
	int a = 0;
	int b = 0;
	scanf("%d %d", &a, &b);
	int ret = gcd(a, b);
	printf("%d\n", ret);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

代码实现（递归版本）

#include 

int gcd(int m, int n)
{
	if (n == 0)
		return m;
	return gcd(n, m % n);
}

int main()
{
	int a = 0;
	int b = 0;
	scanf("%d %d", &a, &b);
	int ret = gcd(a, b);
	printf("%d\n", ret);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

练习题：小乐乐与欧几里得_牛客题霸_牛客网 (nowcoder.com)

#include 
int main()
{
	long long n = 0;
	long long m = 0;
	while (scanf("%lld %lld", &n, &m) == 2)
	{
		long long a = n;  //将n和m赋值给a和b，防止使用辗转相除法改变它们的值
		long long b = m;
		long long gcd = 0;
		long long lcm = 0;
		while (b)  //辗转相除法求最大公约数
		{
			long long rem = a % b;
			a = b;
			b = rem;
		}
		gcd = a;
		lcm = n * m / gcd;  //最小公倍数 = n * m /最大公约数
		printf("%lld\n", gcd + lcm);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

---