考点：【字符串】【数组】

题目1. 打印X

题目描述

输入一个正整数N， 你需要按样例的方式返回一个字符串列表。
1≤N≤15。
样例 1：
输入：1
输出：[“X”]

X

样例 2：
输入：2
[“XX”, “XX”]

XX
XX

样例 3：
输入：3
[“X X”, " X ", “X X”]

X XX
X X

样例 4：
输入：4
[“X X”, " XX ", " XX ", “X X”]
理解成图案：

X  X XX  XX 
X  X

解题代码如下：

#include <stdio.h>
#include <stdlib.h>char** generatePattern(int N) {// 分配字符串列表的内存空间char** pattern = (char**)malloc(N * sizeof(char*));// 为每个字符串分配内存空间for (int i = 0; i < N; i++) {pattern[i] = (char*)malloc((N+1) * sizeof(char));}// 构建字符串列表for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {if (j == i || j == (N - i - 1)) {pattern[i][j] = 'X';}else {pattern[i][j] = ' ';}}pattern[i][N] = '\0'; // 字符串末尾添加结束符}return pattern;
}int main() {int N;printf("请输入一个正整数N：");scanf_s("%d", &N);char** pattern = generatePattern(N);// 输出字符串列表for (int i = 0; i < N; i++) {printf("%s\n", pattern[i]);}// 释放内存空间for (int i = 0; i < N; i++) {free(pattern[i]);}free(pattern);return 0;
}

• 备注：其实也可以构建一个数组，让其先初始化全是’ ‘空格，然后在对称的idx和N-idx-1改写成’X’。

题目2. 最长和谐子序列

题目描述

• 我们将一个和谐数组定义为是其最大值和最小值之间的差值恰好为1的数组。现在，给定一个整数数组，您需要在其所有可能的子序列中找到其最长的和谐子序列的长度。
• 示例：

输入：[1,3,2,2,5,2,3,7]
输出：5
解释：最长的和谐子序列是[3,2,2,2,3]。

解题思路

• 先将数组排序，然后再进行相近元素进行比较，统计两数之差小于等于1的元素个数，不停更新这种元素的个数，直达找到最大长度。

解题代码

#include <stdio.h>
#include <stdlib.h>// 比较函数，用于排序
int cmpFunc(const void* a, const void* b)
{return (*(int*)a - *(int*)b);  //升序
}int findLHS(int* nums, int numsSize)
{int maxLen = 0;// 对数组进行排序qsort(nums, numsSize, sizeof(int), cmpFunc);for (int i = 0; i < numsSize; i++){int count = 1;int j = i + 1;// 计算当前数字和后续数字之间的差值while (j < numsSize && nums[j] - nums[i] <= 1){if (nums[j] == nums[i] || nums[j] == nums[i] + 1){count++;}j++;}// 更新最大长度if (count > maxLen){maxLen = count;}}return maxLen;
}int main()
{int nums[] = { 1, 3, 2, 2, 5, 2, 3, 7 };int numsSize = sizeof(nums) / sizeof(nums[0]);int maxLength = findLHS(nums, numsSize);printf("最长的和谐子序列的长度为：%d\n", maxLength);return 0;
}

• 备注：代码用到stdlib.h中的qsort排序函数。函数原型如下：

void qsort(void *base, size_t num, size_t size,
int (*compar)(const void *, const void *));
//其中入参4:
int (*compar)(const void *a, const void *b)
{return (*(int *)a) - *(int *)b)); //升序//return (*(int *)b) - *(int *)a)); //降序//该函数注意点：首先void *需要先强制转成待比较的数据类型才行，比如如下：return (*(double *)a) - *(double *)b) > 0 ? 1 : - 1); //升序
}

• void *base: 一个指向要排序的数组或对象的指针，即数组的首地址或对象的地址。
• size_t num: 数组中元素的数量。
• size_t size: 数组中每个元素的大小，以字节为单位。
• int (*compar)(const void *, const void *): 指向比较函数的指针。该函数用于定义元素之间的比较规则，并返回一个整数值表示比较结果。该比较函数接受两个指向元素的指针，并返回一个负整数、零或正整数来表示第一个元素小于、等于或大于第二个元素。

题目3. 用C语言实现快速排序

算法描述

• 用C语言实现对一个数组进行快速排序

解题代码

#include <stdio.h>// 快速排序函数
void quickSort(int arr[], int low, int high) {if (low < high) {int pivot = arr[low]; //选取数组第一个元素作为基准值int i = low, j = high;while (i < j) {// 从右向左找小于基准值的元素while (i < j && arr[j] >= pivot)j--;if (i < j)arr[i++] = arr[j];// 从左向右找大于基准值的元素while (i < j && arr[i] <= pivot)i++;if (i < j)arr[j--] = arr[i];}arr[i] = pivot; // 将基准值放入中间位置// 递归排序基准值左边和右边的子数组quickSort(arr, low, i - 1);quickSort(arr, i + 1, high);}
}int main() {int arr[] = {7, 9, 1, 6, 3, 2};int size = sizeof(arr) / sizeof(arr[0]);printf("原始数组：");for (int i = 0; i < size; i++)printf("%d ", arr[i]);printf("\n");quickSort(arr, 0, size - 1);printf("排序后数组：");for (int i = 0; i < size; i++)printf("%d ", arr[i]);printf("\n");return 0;
}

• 运行结果：

原始数组：7 9 1 6 3 2 
排序后数组：1 2 3 6 7 9