【C语言经典例题】——程序员必须会的经典基础例题（三）

2、有序序列合并

输入两个升序排列的序列，将两个序列合并为一个有序序列并输出。

数据范围： 1≤n,m≤1000 ， 序列中的值满足 0≤val≤30000

输入描述：

输入包含三行第一行包含两个正整数n, m，用空格分隔。n表示第二行第一个升序序列中数字的个数，m表示第三行第二个升序序列中数字的个数。

第二行包含n个整数，用空格分隔。

第三行包含m个整数，用空格分隔。

输出描述：

输出为一行，输出长度为n+m的升序序列，即长度为n的升序序列和长度为m的升序序列中的元素重新进行升序序列排列合并。

方法一：题目没有考虑到时间复杂度，这里最简单粗暴的就是将两次输入的数据放在一个m+n的数组里，然后再进行冒泡排序。如下：

#include 
//有序序列合并
//把两次输入的都放到同一个数组，然后对它进行冒泡排序
int main()
{
    int n = 0;
    int m = 0;
    scanf("%d %d", &n, &m);
    int arr[2000];
    int i = 0;
    int j = 0;
    for (i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
    }
    //下标从n开始，一直到n+m-1，一共m个元素
    for (i = n; i < m + n; i++)
    {
        scanf("%d", &arr[i]);
    }

    //冒泡排序//趟数
    for (i = 0; i < n + m; i++)
    {
        for (j = 0; j < n + m - 1 - i; j++)
        {
            //两两相邻元素比较
            if (*(arr + j) > *(arr + j + 1))
            {
                int min = *(arr + j + 1);
                *(arr + j + 1) = *(arr + j);
                *(arr + j) = min;
            }
        }

    }
    //打印
    for (i = 0; i < m + n; i++)
    {
        printf("%d ", *(arr + i));
    }
    return 0;
}

方法二：分别存放在两个数组里，然后进行比较，将数据小的元素输出，然后下标++，但是需要考虑到两种特殊情况，就是一个数组已经输出完了，另一个还没输出完，完整实现代码如下：

#include

int main()
{
	int n = 0;
	int m = 0;
	int arr1[1000];
	int arr2[1000];
	int i = 0;
	int j = 0;
	scanf("%d %d", &n, &m);
	for (i = 0; i < n; i++)
	{
		scanf("%d", &arr1[i]);
	}
	for (j = 0; j < m; j++)
	{
		scanf("%d", &arr2[j]);
	}
	i = 0, j = 0;
	while (i < n && j < m)
	{
		//输出小的
		if (arr1[i] < arr2[j])
		{
			printf("%d ", arr1[i]);
			i++;//下标++继续比较
		}
		else if (arr1[i] >= arr2[j])
		{
			printf("%d ", arr2[j]);
			j++;//++继续比较
		}
	}
	//当i==n时，说明arr1已经输出完了，直接把剩下的arr2输出即可
	if (i == n)
	{
		for (; j < m; j++)
		{
			printf("%d ", arr2[j]);
		}
	}
	//j==m时，说明arr2已经输出完了，直接把剩下的arr1输出即可
	else if (j == m)
	{
		for (; i < n; i++)
		{
			printf("%d ", arr1[i]);
		}
	}
	return 0;
}

两种方法都可以实现，方法一思路简单，直接粗暴的解决，方法二的时间复杂度要低于方法一，因此，假如考虑到时间复杂度的情况下，方法二优先。

3、有序序列插入一个数

题目：有一个有序数字序列，从小到大排序，将一个新输入的数插入到序列中，保证插入新数后，序列仍然是升序。

输入描述：

第一行输入一个整数(0≤N≤50)。

第二行输入N个升序排列的整数，输入用空格分隔的N个整数。

第三行输入想要进行插入的一个整数。

输出描述：

输出为一行，N+1个有序排列的整数。

思路：最简单的思路就是与上面相同，将插入的数放在同一个数组，然后直接qsort或者冒泡排序，简单粗暴。这里我采用了qsort（不会的或者已经遗忘的老铁可以去前面的文章复习一下）

#include
#include
//比较
int cmp(const void* e1, const void* e2) {
    return *(int*)e1 - *(int*)e2;
}
//打印
void print(int* arr, int N) {
    int i = 0;
    for (i = 0; i <= N; i++) {
        printf("%d ", arr[i]);
    }
}

int main() 
{
    int arr[50] = { 0 };
    int N = 0;
    int i = 0;

    scanf("%d", &N);
    for (i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
    }
    scanf("%d", &arr[N]);
    //qsort排序
    qsort(arr, N+1, sizeof(arr[0]), cmp);
    print(arr, N);
    return 0;
}

4、调整奇数偶数顺序

题目：

输入一个整数数组，实现一个函数，

来调整该数组中数字的顺序使得数组中所有的奇数位于数组的前半部分

所有偶数位于数组的后半部分

思路：这里题目没有说要保持相对位置不变，所以我们只需要将偶数与奇数分离即可

定义两个指针，一个指向首元素地址，另一个指向末元素地址

在有效范围内，一个从前往后找，找到偶数停止，另一个从后往前，直到找到奇数停止

当两者都停止时交换位置，继续循环

如下图（p1<p2）

代码实现：

#include
void swap(int* arr, int sz)
{
	int left = 0;
	int right = sz - 1;
	while (left < right)
	{
		//从前往后，找到偶数停止
		while ((left < right) && (*(arr + left) % 2 == 1))
		{
			left++;
		}
		//从后往前，找到奇数停止
		while ((left < right) && (*(arr + right) % 2 == 0))
		{
			right--;
		}
		//两者交换
		if (left < right)
		{
			int tmp = *(arr + left);
			*(arr + left) = *(arr + right);
			*(arr + right) = tmp;
		}
	}
	//打印
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", *(arr + i));
	}
}

int main()
{
	int arr[] = { 1,9,80,5,4,68,78,45,2,456,5,1,3,87,9,88,51,20 };
	int i = 0;
	int sz = sizeof(arr) / sizeof(arr[0]);
	swap(arr, sz);

	return 0;
}

5、修改数字—偶数改为0，奇数改为1

小乐乐喜欢数字，尤其喜欢0和1。他现在得到了一个数，想把每位的数变成0或1。如果某一位是奇数，就把它变成1，如果是偶数，那么就把它变成0。请你回答他最后得到的数是多少。

这里我们通过实际数字进行分析，比如数字123，分析如下：

代码实现：

#include 
#include
int main()
{
    int n=0;
    int tmp=0;
    int sum=0;
    int cont=0;//统计位数
    scanf("%d",&n);
    do
    {
        tmp=n%10;//得到尾数
        if(tmp%2 !=0)
        tmp=(int)1*pow(10,cont);
        else
        tmp=(int)0*pow(10,cont);
        sum+=tmp;//每次相加
        cont++;
    }while(n/=10);
    //打印即可
    printf("%d",sum);
    return 0;
}

6、猜名次

5位运动员参加了10米台跳水比赛，有人让他们预测比赛结果：

A选手说：B第二，我第三；

B选手说：我第二，E第四；

C选手说：我第一，D第二；

D选手说：C最后，我第三；

E选手说：我第四，A第一；

比赛结束后，每位选手都说对了一半，请编程确定比赛的名次

思路，把所有可能都列举出来，然后挑选符合题目要求的即可

#include
int main()
{
	int a = 0;
	int b = 0;
	int c = 0;
	int d = 0;
	int e = 0;
	//穷举
	for (a = 1; a <= 5; a++)
	{
		for (b = 1; b <= 5; b++)
		{
			for (c = 1; c <= 5; c++)
			{
				for (d = 1; d <= 5; d++)
				{
					for (e = 1; e <= 5; e++)
					{
						if ((b == 2) + (a == 3) == 1 &&
							(b == 2) + (e == 4) == 1 &&
							(c == 1) + (d == 2) == 1 &&
							(c == 5) + (d == 3) == 1 &&
							(e == 4) + (a == 1) == 1
							)
						{
						//所有的可能中，只有1，2，3，4，5这五个不同的排名名次，只有这个才符合答案
							if (a * b * c * d * e == 120 && a + b + c + d + e == 15)
							{
								printf("a=%d b=%d c=%d d=%d e=%d\n", a, b, c, d, e);//a=3 b=1 c=5 d=2 e=4
							}
						}
					}
				}
			}
		}
	}
	return 0;
}

7、猜凶手

日本某地发生了一件谋杀案，警察通过排查确定杀人凶手必为4个嫌疑犯的一个。

以下为4个嫌疑犯的供词:

A说：不是我。

B说：是C。

C说：是D。

D说：C在胡说

已知3个人说了真话，1个人说的是假话。

现在请根据这些信息，写一个程序来确定到底谁是凶手。

与上面的题思路一样，列举所有可能，然后只会存放在一种是符合题意的

#include
int main()
{
	//凶手
	char killer = '0';
	//ABCD中的一个，列举所有可能
	for (killer = 'A'; killer <= 'D'; killer++)
	{
		//有三个是真的
		if ((killer != 'A') + (killer == 'C') + (killer == 'D') + (killer != 'D') == 3)
		{
			printf("%c\n", killer); //C
		}
	}

	return 0;
}

8、字符串逆序单词并打印

将一句话的单词进行倒置，标点不倒置。比如 I like beijing. 经过函数后变为：beijing. like I

输入描述：

每个测试输入包含1个测试用例： I like beijing. 输入用例长度不超过100

输出描述：

依次输出倒置之后的字符串,以空格分割

示例1:

输入

I like beijing.

输出

beijing. like I

不使用库函数strlen等

思路：这里介绍的是三指针两次反转法，比如 I like beijing.

第一次反转（每个单词）I ekil .gnijieb

第二次反转 （整个）beijing. like I

由于这里不让用库函数，所以这里用来计算整个字符串长度的strlrn用不了，但自己可以写一个

代码实现

#include
#include

//模拟实现strlen
int is_mystrlen(const char*arr)
{
	assert(arr);
	int count = 0;
	while (*(arr++))
	{
		count++;
	}
	return count;
}
//反转
void reserve(char* left, char* right)
{
	assert(left);
	assert(right);

	while (left < right)
	{
		char tmp = *(left);
		*left = *right;
		*right = tmp;

		left++;
		right--;
	}
}

int main()
{
	char arr[101];

	gets(arr);
	//数组名首元素地址
	char* cut = arr;
	//遇到\0结束
	while (*cut)
	{
		char* star = cut;
		char* end = cut;
		while (*end != ' ' && *end !='\0')
		{
			end++;
		}
		//反转
		reserve(star, end - 1);  
		if (*end != '\0')
			cut = end + 1;
		else
			cut = end;
	}
	//计算字符串长度
	int count_ = is_mystrlen(arr);
	//反转整个字符串
	reserve(arr, arr + count_-1 );
	printf("%s", arr);
	return 0;
}

9、字符串左旋

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

例如：

ABCD左旋一个字符得到BCDA

ABCD左旋两个字符得到CDAB

思路：旋转k次，每次旋转一个字符，k取模，防止不必要的旋转

代码实现：

#include
#include
void leftRound(char* src, int time)
{
	int i, j, tmp;
	int len = strlen(src);
	time %= len; //长度为5的情况下，旋转6、11、16...次相当于1次，7、12、17...次相当于2次，以此类推。
	for (i = 0; i < time; i++) //执行k次的单次平移
	{
		tmp = src[0];
		for (j = 0; j < len - 1; j++) //单次平移
		{
			src[j] = src[j + 1];
		}
		//再把头赋值到尾
		src[j] = tmp;
	}
}
int main()
{
	int k = 0;
	char arr[1000] = { 0 };
	scanf("%s %d", arr,&k);
	leftRound(arr, k);
	printf("%s", arr);

	return 0;
}

10、判断字符串旋转结果

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

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

给定s1=abcd和s2=ACBD，返回0.

AABCD左旋一个字符得到ABCDA

AABCD左旋两个字符得到BCDAA

AABCD右旋一个字符得到DAABC

思路：和上个题是一样的，这里把它所有旋转的可能列举出来，然后用strcmp函数进行比较即可。

代码实现：

#include
#include
#include

int reverse(char* arr1, char* arr2)
{
	assert(arr1 && arr2);
	int len1 = strlen(arr1);
	int len2 = strlen(arr2);
	//长度不相等，肯定不是旋转后的
	if (len1 != len2)
		return 0;
	int i = 0;
	int j = 0;
	//把所有可能都旋转
	for (i = 0; i < len1; i++)
	{
		char p = *arr1;
		for (j = 0; j < len1 - 1; j++)
		{
			*(arr1 + j) = *(arr1 + j + 1);
		}
		*(arr1 + len1 - 1) = p;
		//strcmp比较字符串，==0表示相等
		if (strcmp(arr1, arr2) == 0)
		{
			//相等返回1
			return 1;
		}
	}
	//如果经历循环后还没返回，说明不相等，返回0
	return 0;
}
int main()
{
	char arr1[] = "abcdefg";
	char arr2[] = "defgabc";
	//两个字符串
	int ret = reverse(arr1, arr2);
	//返回1表示相等，可打印YES看一下
	if (ret == 1)
		printf("YES");
	else
		printf("NO");
	return 0;
}

end

生活原本沉闷。但跑起来就会有风！🌹