考點：【字符串】【數(shù)組】

題目1. 打印X

題目描述

輸入一個正整數(shù)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) {// 分配字符串列表的內(nèi)存空間char** pattern = (char**)malloc(N * sizeof(char*));// 為每個字符串分配內(nèi)存空間for (int i = 0; i < N; i++) {pattern[i] = (char*)malloc((N+1) * sizeof(char));}// 構(gòu)建字符串列表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'; // 字符串末尾添加結(jié)束符}return pattern;
}int main() {int N;printf("請輸入一個正整數(shù)N：");scanf_s("%d", &N);char** pattern = generatePattern(N);// 輸出字符串列表for (int i = 0; i < N; i++) {printf("%s\n", pattern[i]);}// 釋放內(nèi)存空間for (int i = 0; i < N; i++) {free(pattern[i]);}free(pattern);return 0;
}

• 備注：其實也可以構(gòu)建一個數(shù)組，讓其先初始化全是’ ‘空格，然后在對稱的idx和N-idx-1改寫成’X’。

題目2. 最長和諧子序列

題目描述

• 我們將一個和諧數(shù)組定義為是其最大值和最小值之間的差值恰好為1的數(shù)組?，F(xiàn)在，給定一個整數(shù)數(shù)組，您需要在其所有可能的子序列中找到其最長的和諧子序列的長度。
• 示例：

輸入：[1,3,2,2,5,2,3,7]
輸出：5
解釋：最長的和諧子序列是[3,2,2,2,3]。

解題思路

• 先將數(shù)組排序，然后再進(jìn)行相近元素進(jìn)行比較，統(tǒng)計兩數(shù)之差小于等于1的元素個數(shù)，不停更新這種元素的個數(shù)，直達(dá)找到最大長度。

解題代碼

#include <stdio.h>
#include <stdlib.h>// 比較函數(shù)，用于排序
int cmpFunc(const void* a, const void* b)
{return (*(int*)a - *(int*)b);  //升序
}int findLHS(int* nums, int numsSize)
{int maxLen = 0;// 對數(shù)組進(jìn)行排序qsort(nums, numsSize, sizeof(int), cmpFunc);for (int i = 0; i < numsSize; i++){int count = 1;int j = i + 1;// 計算當(dāng)前數(shù)字和后續(xù)數(shù)字之間的差值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排序函數(shù)。函數(shù)原型如下：

void qsort(void *base, size_t num, size_t size,
int (*compar)(const void *, const void *));
//其中入?yún)?:
int (*compar)(const void *a, const void *b)
{return (*(int *)a) - *(int *)b)); //升序//return (*(int *)b) - *(int *)a)); //降序//該函數(shù)注意點：首先void *需要先強制轉(zhuǎn)成待比較的數(shù)據(jù)類型才行，比如如下：return (*(double *)a) - *(double *)b) > 0 ? 1 : - 1); //升序
}

• void *base: 一個指向要排序的數(shù)組或?qū)ο蟮闹羔?#xff0c;即數(shù)組的首地址或?qū)ο蟮牡刂贰?/li>
• size_t num: 數(shù)組中元素的數(shù)量。
• size_t size: 數(shù)組中每個元素的大小，以字節(jié)為單位。
• int (*compar)(const void *, const void *): 指向比較函數(shù)的指針。該函數(shù)用于定義元素之間的比較規(guī)則，并返回一個整數(shù)值表示比較結(jié)果。該比較函數(shù)接受兩個指向元素的指針，并返回一個負(fù)整數(shù)、零或正整數(shù)來表示第一個元素小于、等于或大于第二個元素。

題目3. 用C語言實現(xiàn)快速排序

算法描述

• 用C語言實現(xiàn)對一個數(shù)組進(jìn)行快速排序

解題代碼

#include <stdio.h>// 快速排序函數(shù)
void quickSort(int arr[], int low, int high) {if (low < high) {int pivot = arr[low]; //選取數(shù)組第一個元素作為基準(zhǔn)值int i = low, j = high;while (i < j) {// 從右向左找小于基準(zhǔn)值的元素while (i < j && arr[j] >= pivot)j--;if (i < j)arr[i++] = arr[j];// 從左向右找大于基準(zhǔn)值的元素while (i < j && arr[i] <= pivot)i++;if (i < j)arr[j--] = arr[i];}arr[i] = pivot; // 將基準(zhǔn)值放入中間位置// 遞歸排序基準(zhǔn)值左邊和右邊的子數(shù)組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("原始數(shù)組：");for (int i = 0; i < size; i++)printf("%d ", arr[i]);printf("\n");quickSort(arr, 0, size - 1);printf("排序后數(shù)組：");for (int i = 0; i < size; i++)printf("%d ", arr[i]);printf("\n");return 0;
}

• 運行結(jié)果：

原始數(shù)組：7 9 1 6 3 2 
排序后數(shù)組：1 2 3 6 7 9