目录

一.杨氏矩阵

1.初级

2.想把下标带回来

二.字符串左旋

算法改进

三.判断是否为字符串旋转结果

算法改进

四. 3个字符函数

1.strcat

2.strncat

3.strstr

一.杨氏矩阵

数字矩阵，每行从左到右递增，每列从上到下递增，编写程序在矩阵中查找某个数字是否存在。

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

1.初级

我们采用这样的算法：

• 由于每行每列都是递增的，用矩阵左下或右上角的数与目标数比较(右上角为例)。
• 右上角的元素，是其所在行中最大的，列中最小的。
• 若目标数大，则删除右上角元素所在行。用新矩阵的右上角再与目标数比较。
• 若目标数小，则删除右上角元素所在列。用新矩阵的右上角再与目标数比较。
• 重复以上过程，直至找到，或越界

代码演示：

void find_k(int arr[3][3], int r, int c, int k)
{
	int x = 0;
	int y = c - 1;
	int flag = 0;
	while (x <= r - 1 && y >= 0)
	{
		if (k > arr[x][y])
		{
			x++;
		}
		else if (k < arr[x][y])
		{
			y--;
		}
		else
		{
			printf("找到了，下标是：%d %d\n", x, y);
			flag = 1;
			break;
		}
	}
	if (flag == 0)
		printf("找不到\n");
}
 
int main()
{
	int arr[3][3] = { 1,2,3,4,5,6,7,8,9 };
	int k = 7;//要查找的元素
 
	find_k(arr, 3, 3, k);
 
	return 0;
}
AI写代码

2.想把下标带回来

难道要这样吗？

		else
		{
			printf("找到了，下标是：%d %d\n", x, y);
			flag = 1;
			return x, y;
		}
AI写代码

错了。没有这样写的，只能返回一个值

我们需要把x，y创建在调用函数外面，再传x，y地址。

int find_k(int arr[3][3], int* px, int* py, int k)
{
	int x = 0;
	int y = *py - 1;
	while (x <= *px - 1 && y >= 0)
	{
		if (arr[x][y] < k)
		{
			x++;
		}
		else if (arr[x][y] > k)
		{
			y--;
		}
		else
		{
			*px = x;
			*py = y;
			return 1;
		}
	}
	return 0;
}
 
int main()
{
	int arr[3][3] = { 1,2,3,4,5,6,7,8,9 };
	int k = 17;//查找的值
	int x = 3;
	int y = 3;
	int ret = find_k(arr, &x, &y, k);
	if (ret == 0)
		printf("找不到\n");
	else
		printf("找到了，下标是:%d %d", x, y);
 
	return 0;
}
AI写代码

二.字符串左旋

实现一个函数，可以左旋字符串中的k个字符。

例如：ABCD左旋一个字符得到BCDA          ABCD左旋两个字符得到CDAB

思路是这样：

左旋一个字符：

1. 把第一个字符放进 tmp 中。
2. 将后面的字符向前挪。
3. 将 tmp 中的第一个字符放到最后面

左旋 k 个字符：重复 k 次。

代码演示：

void left_move(char arr[], int k)
{
	int i = 0;
	int len = strlen(arr);
	k %= len;
	for (i = 0; i < k; i++)
	{
		//旋转1个字符
		//1
		char tmp = arr[0];
		//2
		int j = 0;
		for (j = 0; j < len - 1; j++)
		{
			arr[j] = arr[j + 1];
		}
		//3
		arr[len - 1] = tmp;
	}
}
 
int main()
{
	char arr[] = "abcdef";
	int k = 8;
	left_move(arr, k);
	printf("%s\n", arr);
	return 0;
}
AI写代码

算法改进

当字符串比较长时，上面那种一个一个交换的方法效率低下。

我们尝试这样的思路：逆序字符串。逆序左边，逆序右边，整体逆序。

例如：

#include 
 
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 main()
{
	char arr[] = "abcdef";
	int k = 8;
	left_move(arr, k);
	printf("%s\n", arr);
	return 0;
}
AI写代码

三.判断是否为字符串旋转结果

写一个函数，判断一个字符串是否为另外一个字符串旋转之后的字符串。

例如：给定s1 =AABCD和s2 = BCDAA，返回1              给定s1=abcd和s2=ACBD，返回0

思路：每左旋一次，都进行判断。

代码演示：

#include 
 
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, 1);//每次旋转1个
		if (strcmp(arr1, arr2) == 0)//比较
		{
			return 1;
		}
	}
	//从来没有 return 1; 那就不可能 YES
	return 0;
}
 
int main()
{
	char arr1[] = "AABCD";
	char arr2[] = "ABCDA";
	int ret = is_left_move(arr1, arr2);
	if (ret == 1)
	{
		printf("YES\n");
	}
	else
	{
		printf("NO\n");
	}
	return 0;
}
AI写代码

这种方法其实也不够简练

算法改进

各位读者先阅读 四.

上面的方法其实把 arr1 旋转后所有的可能情况都列出来了，再进行比较。

有没有办法让它直接得到所有旋转后的可能性？ 有的兄弟，有的！

比如：AABCDAABCD（自己重复两遍）

发现：AABCDAABCD 里包含了 AABCD 所有旋转后的可能性。

只需要给 arr1 追加 arr1 后，去看 arr2 是不是追加后的子串。如果是，那就是 arr1 旋转得来的。

前提：如果长度不一样，要提前 Pass

注意：给 arr1 追加时，要有空间，最好 char arr1[20]，给大一点。要不然程序崩了

代码演示：

#include 
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;
}
 
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;
}
AI写代码

这样写，我们把大量代码依赖于库函数实现

四. 3个字符函数

1.strcat

头文件：#include

#include 
int main()
{
	char arr[20] = "hello ";//想在后面追加 world
	strcat(arr, "world");
	printf("%s\n", arr);
 
	return 0;
}
AI写代码

2.strncat

头文件：#include

在 hello 后追加几个，由我们控制。用 strcat 的另一个版本：strncat

#include 
int main()
{
	char arr[20] = "hello ";
	strncat(arr, "world", 3); // 5
	printf("%s\n", arr);
 
	return 0;
}
AI写代码

3.strstr

头文件：#include

strstr 是在arr1字符串中查找arr2是否存在

• 如果存在则返回 arr2 在 arr1 中首次出现的地址(位置)
• 如果不存在返回 NULL

#include 
int main()
{
	char arr1[] = "abcdefabcdef";
	char arr2[] = "def";
 
	char* ret = strstr(arr1, arr2);
	if (ret == NULL)
	{
		printf("不存在\n");
	}
	else
	{
		printf("%s\n", ret);
	}
	return 0;
}
AI写代码

本篇的分享就到这里了，感谢观看，如果对你有帮助，别忘了点赞+收藏+关注。

小编会以自己学习过程中遇到的问题为素材，持续为您推送文章。