[数据结构与算法]C语言：刷题总结（3）

C语言的学习告一段落，本文是对近期学习C语言的刷题总结，题目大部分来自牛客网&力扣。

本篇文章是C语言本阶段的最后一篇文章，结束了几个月的学习，接下来会写一些关于Java的博客，后面有机会的话还会再继续来完善C语言内容。

题目十五：数对

题目描述：一个正整数数对（x,y），x和y的值均不大于n，并且x%y的值大于等于k。

输入描述：输入包括两个正整数n, k(1 <= n <= 10 ^ 5, 0 <= k <= n - 1)。
输出描述：对于每个测试用例, 输出一个正整数表示可能的数对数量。

思路：一开始的想法是直接用两个循环暴力求解出符合的数对个数，但是时间复杂度过大，所以编译不通过。这里通过一个例子来引出另一种思路：?假设输入 n=10 , k=3 ；
当 y <= k 时，意味着任何数字取模y的结果都在 [0, k-1]之间，都是不符合条件的。
当 y = k+1=4 时，x符合条件的数字有 3,7
当 y = k+2=5 时，x符合条件的数字有 3,4,8,9
当 y = k+3=6 时，x符合条件的数字有 3,4,5,9,10
当 y = k+n时，
x小于y当前值，且符合条件的数字数量是：y-k个，
x大于y当前值，小于2*y的数据中，且符合条件的数字数量是：y-k个
从上一步能看出来，在y的整数倍区间内，x符合条件的数量就是 (n / y) * (y - k)个
n / y 表示有多少个完整的 0 ~ y区间， y - k 表示有每个区间内有多少个符合条件的数字
最后还要考虑的是6...往后这种超出倍数区间超过n的部分的统计
n % y 就是多出完整区间部分的数字个数，其中k以下的不用考虑，则符合条件的是 n % y - (k-1) 个
这里需要注意的是类似于9这种超出完整区间的数字个数 本就小于k的情况，则为0
得出最终公式：(n / y) * (y - k) + ((n % y < k) ? 0, (n % y - k + 1));

实现代码：

#include <stdio.h>
int main()
{
	long n = 0;
	long k = 0;
	scanf("%ld %ld", &n, &k);
	if (k == 0)
	{
		printf("%ld\n", n * n);
	}
	else
	{
		long count = 0;
		for (long y = k + 1; y <= n; y++)
		{
			count += ((n / y) * (y - k)) + ((n % y < k) ? 0: (n % y - k + 1));
		}
		printf("%ld\n", count);
	}
	return 0;
}

题目十六：旋转字符串问题——左旋转字符串

题目描述：输入k，输出左旋转k个字符后的字符串

思路一：常规方法，将第一个字符存起来，其他字符都向前移动一位，最后将存起来的那个字符复制到最后，依次循环k次，就可以得出结果

实现代码：

#include <stdio.h>
#include <string.h>

void left_move(char* arr, int k)
{
	int len = strlen(arr);
	while (k--)
	{
		char ret = *arr;
		int i = 0;
		for (i = 0; i < len - 1; i++)
		{
			*(arr + i) = *(arr + i + 1);
		}
		*(arr + len - 1) = ret;
	}
}

int main()
{
	char arr[] = "abcdef";
	int k = 0;
	scanf("%d", &k);
	left_move(arr, k);
	printf("%s\n", arr);
	return 0;
}

思路二：三逆序实现旋转，假如是旋转k位，则在第k位的位置将这个字符串分隔为两个字符串，然后将这两个字符串分别逆序，最后再将整个字符串逆序一遍，也可以得出结果

实现代码：

void reverse(char* left, char* right)
{
	while (left < right)
	{
		char ret = *left;
		*left = *right;
		*right = ret;
		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 = 0;
	scanf("%d", &k);
	left_move(arr, k);
	printf("%s\n", arr);
	return 0;
}

题目十七：杨氏矩阵

题目描述：有一个三维数组，数组的每行从左到右是递增的，每列从上到下是递增的.。在这个的数组中查找一个数字是否存在。

思路：本题最简单、最暴力的思路就是直接把整个三维数组遍历一遍，但是有时候是不能够通过测试用例的，这里介绍一种时间复杂度较低的且比较常规的思路——三维杨氏矩阵九个元素中只有两个元素是符合的（斜对角线顶点的两个元素，也就是第一行第三列和第三行第一列的两个元素），选其中的任意一个都可以，这里我用第一行第三列的元素（暂且称之为k）来实现，如果查找的数小于k的值，那么就来k前面的两个元素查找即可，如果是大于k的值，那么则找本列下一行的元素，再重复上面的比较，直到找到所要查找的元素，返回该元素坐标，如果查找是超出三维数组的界限，那么则可以判断该数组中并无这个数。

实现代码：

#include <stdio.h>

void find_int_arr(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)
		{
			y--;
		}
		else if (arr[x][y] < k)
		{
			x++;
		}
		else
		{
			*px = x;
			*py = y;
			return;
		}
	}
	*px = -1;
	*py = -1;
	return;
}

int main()
{
	int arr[3][3] = { 1,2,3,4,5,6,7,8,9 };
	int k = 0;
	int x = 3;
	int y = 3;
	scanf("%d", &k);
	find_int_arr(arr, &x, &y, k);
	if (x == -1 && y == -1)
	{
		printf("找不到\n");
	}
	else
	{
		printf("找到了，下标是:(%d,%d)", x, y);
	}
	return 0;
}

题目十八：找单身狗

题目描述：一个数组中只有两个数字是出现一次，其他所有数字都出现了两次。编写一个函数找出这两个只出现一次的数字。

思路：我们在前面的题目中就已经知道：只需要把数组中的所有数都异或在一起，就可以找出数组中只出现一次的数字。但是这道题相对于之前的那道题，还是有不同之处的，总体来说也会增加一个难度，因为该题是要找出数组中两个只出现一次的数字，乍一看，感觉还是挺类似的，但是仔细想想，如果像之前那样全部异或起来的话，只能够得出一个错误的值，所以这里就想到一个思路——就是将这个数组分为两部分，把两个只出现一次的数字分别分到两个组里面去，然后分别异或找出来即可。那么该如何识别出并将两个数分到两个组里面去呢？第一步，将数组中全部数字都异或起来；第二步，寻找异或之后的二进制有那个位按位与1之后值是1，是1则可以说明这两个只出现一次的数字在二进制中这一位是不相同的，相异或之后才会是1；第三步，将二进制中以刚才得出的不同位为准，就可以将这些数字分为两组，这两个只出现一次的数字分在不同组中了。这样就可以得出最后的结果。

实现代码：?

#include <stdio.h>
int main()
{
	int arr[] = { 1,2,3,4,5,1,2,3,4,6 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	//1.先将全部数异或在一起
	int ret = 0;
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		ret ^= arr[i];
	}
	//2.计算ret的二进制第几位是1
	int pos = 0;
	for (i = 0; i < 32; i++)
	{
		if (((ret >> i) & 1) == 1)
		{
			pos = i;
			break;
		}
	}
	//3.按pos位是0或1来对数组进行分组
	int n = 0;
	int m = 0;
	for (i = 0; i < sz; i++)
	{
		if (((arr[i] >> pos) & 1) == 1)
		{
			n ^= arr[i];
		}
	}
	m = ret ^ n;
	printf("%d %d\n", n, m);
	return 0;
}

题目十九：判断字符串是否是另一字符串旋转得来的

题目描述：判断字符串是否是另一字符串旋转得来的

思路：大多数人受之前旋转字符串代码的影响，对这道题的第一想法应该都是先旋转字符串再来进行判断是否相等，如此循环。但是对于这道题还有一种更加简便的方法——拷贝自身字符串并添加到后面的位置，再通过字符串查找，来判定是否存在，进而解决这道题。

实现代码：

#include <stdio.h>
#include <string.h>
int main()
{
	char str[20] = "abcde";
	char* sub = "cdeab";
	char* tmp = strncat(str, str, 5);
	char* ret = strstr(tmp, sub);
	if (ret == NULL)
	{
		printf("找不到\n");
	}
	else
	{
		printf("%s\n", ret);
	}
	return 0;
}