函数与指针的习题
函数与指针的习题1、杨氏矩阵
杨氏矩阵：每行从左到右递增，每列从上到小递增
编写程序查找杨氏矩阵中的数字，并返回其下标（时间复杂度小于O(n)）
分析：对于矩阵右上角的元素，若目标值大于该值则目标值不在该行，若目标值小于该值则目标值不在该列。通过上述特点进行判断，并通过位移数组指针指向以缩小范围，最终确定目标值int main()
{
int arr = { 1,2,3,4,5,6,7,8,9 };
int k = 7;
int col = sizeof arr / sizeof arr;
int x = 0;
int y = col - 1;
while (x <= col - 1 && y >= 0)
{
if (arr > k)
{
y--;
}
else if (arr < k)
{
x++;
}
else
{
printf("已经找到，下标为[%d][%d]\n", x, y);
break;
}
}
if (x > col - 1 || y < 0)
{
printf("未找到\n");
}
return 0;
}2、字符串翻转
给出翻转个数，对字符串进行翻转
如：当翻转个数为2时，字符串"abcde"翻转结果为"cdeab"
分析：存在两种解题思路
[*]循环位移法
每一次进行向左移动1位操作，共执行k次
向左移动1位操作：可分为3步
[*]保存第一个字符于临时变量
[*]位移1位操作
[*]赋值最后一位
void LeftMove(char str[], int k)
{
assert(str != NULL);
int len = strlen(str);
for (int i = 0; i < k; i++)
{
// left move one
// 1. save str
char tmp = *str;
// 2. move
for (int j = 0; j < len - 1; j++)
{
str = str;
}
// 3. last element
str = tmp;
}
}
[*]三步反转法
[*]根据翻转个数k将字符串分为两部分
[*]分别对两部分的元素进行反转
[*]对整体字符串进行反转
void Reverse(char* str,int startIndex, int endIndex)
{
int left = startIndex;
int right = endIndex;
while (left < right)
{
int tmp = *(str + left);
*(str + left) = *(str + right);
*(str + right) = tmp;
left++;
right--;
}
}
void LeftMove(char str[], int k)
{
assert(str != NULL);
int len = strlen(str);
assert(k <= len);
// left part reverse
Reverse(str, 0, k - 1);
// right part reverse
Reverse(str, k, len - 1);
// whole part reverse
Reverse(str, 0, len - 1);
}给两个字符串，判断其中1个字符串是否为另一个的翻转字符串
分析：存在两种解题思路
[*]枚举法
对一个长度为i的字符串，其最多的翻转次数为i，故可遍历i次，查看是否为翻转后的字符串
int IsMove(char tar[], char src[])
{
int tar_len = strlen(tar);
int src_len = strlen(src);
if (tar_len == src_len)
{
for (int i = 1; i <= tar_len; i++)
{
LeftMove(src, 1);
if (strcmp(src, tar) == 0)
{
return 1;
}
}
return 0;
}
else
{
return 0;
}
}
[*]追加字符、判断子串
对目标字符串追加字符，使其在原基础上再向后复制一份原字符串，而若为翻转字符串则该字符串为其子串。
int IsMove(char tar[], char src[])
{
assert(tar != NULL && src != NULL);
int src_len = strlen(src);
int tar_len = strlen(tar);
if (src_len == tar_len)
{
// 1. 追加
strncat(src, src, src_len);
// 2. 判断子串
char* ret = strstr(src, tar);
if (ret == NULL)
{
return 0;
}
else
{
return 1;
}
}
else
{
return 0;
}
}
文档来源：51CTO技术博客https://blog.51cto.com/u_15285915/3260072
页:
[1]