简单的小题集（五）

一、签到两题不嫌多

：现给定 n 个长度相同的十进制正整数，我们分别对所有正整
数的个位，十位，百位…排序，请按从高到低的顺序输出每一位排序后
中间的数字，这里保证 n 是奇数，正整数的位数 <= 10.

#include <stdio.h>
#include <stdlib.h>
// 获取数字的位数
int getNumDigits(int num) {
 int count = 0;
 while (num != 0) {
 num /= 10;
 count++;
 }
 return count;
}
// 获取指定数字的第 d 位数字
int getDigit(int num, int d) {
 return (num / (int)pow(10, d - 1)) % 10;
}
// 基数排序
void radixSort(int *numbers, int n, int numDigits) {
 int i, d;
 // 对每一位进行排序
 for (d = 1; d <= numDigits; d++) {
 int count[10] = {0}; // 计数数组
 int *temp = (int *)malloc(n * sizeof(int)); // 临时数组
 // 统计当前位的数字出现次数
 for (i = 0; i < n; i++) {
 int digit = getDigit(numbers[i], d);
 count[digit]++;
 }
 // 计算每个数字在排序后的数组中的起始位置
 int sum = 0;
 for (i = 0; i < 10; i++) {
 int tempCount = count[i];
 count[i] = sum;
 sum += tempCount;
 }
 // 将数字按当前位排序到临时数组中
 for (i = 0; i < n; i++) {
 int digit = getDigit(numbers[i], d);
 temp[count[digit]] = numbers[i];
 count[digit]++;
 }
 // 将临时数组的内容复制回原数组
 for (i = 0; i < n; i++) {
 numbers[i] = temp[i];
 }
 free(temp);
 }
}
// 输出中间数字
void printMiddle(int *numbers, int n) {
 printf("中间数字：");
 printf("%d ", numbers[n / 2]);
 printf("\n");
}
int main() {
 int n, i;
 printf("请输入正整数的个数：");
 scanf("%d", &n);
 int *numbers = (int *)malloc(n * sizeof(int));
 if (numbers == NULL) {
 printf("内存分配失败\n");
 return 1;
 }
 printf("请输入%d 个长度相同的正整数：\n", n);
 for (i = 0; i < n; i++) {
 scanf("%d", &numbers[i]);
 }
 int numDigits = 0;
 if (n > 0) {
 numDigits = getNumDigits(numbers[0]);
 }
 radixSort(numbers, n, numDigits);
 printMiddle(numbers, n);
 free(numbers);
 return 0;
}

二、数字出现的次数

现在给你 n 个正整数，现要进行 m 次询问某一个数出现了
多少次。已知 n,m <= 10^5, 单个正整数 <= 10^12.

#include <stdio.h>
#include <stdlib.h>
// 二分查找，找到目标数第一次出现的位置
int binarySearchFirst(int *arr, int n, int target) {
 int left = 0;
 int right = n - 1;
 int result = -1;
 while (left <= right) {
 int mid = left + (right - left) / 2;
 if (arr[mid] == target) {
 result = mid;
 right = mid - 1;
 } else if (arr[mid] < target) {
 left = mid + 1;
 } else {
 right = mid - 1;
 }
 }
 return result;
}
// 二分查找，找到目标数最后一次出现的位置
int binarySearchLast(int *arr, int n, int target) {
 int left = 0;
 int right = n - 1;
 int result = -1;
 while (left <= right) {
 int mid = left + (right - left) / 2;
 if (arr[mid] == target) {
 result = mid;
 left = mid + 1;
 } else if (arr[mid] < target) {
 left = mid + 1;
 } else {
 right = mid - 1;
 }
 }
 return result;
}
// 计算某个数出现的次数
int countOccurrences(int *arr, int n, int target) {
 int firstIndex = binarySearchFirst(arr, n, target);
 int lastIndex = binarySearchLast(arr, n, target);
 if (firstIndex == -1 || lastIndex == -1) {
 return 0;
 }
 return lastIndex - firstIndex + 1;
}
int compareInt(const void *a, const void *b) {
 return (*(int *)a - *(int *)b);
}
int main() {
 int n, m;
 printf("请输入正整数的个数：");
 scanf("%d", &n);
 printf("请输入查询次数：");
 scanf("%d", &m);
 long long *numbers = (long long *)malloc(n * sizeof(long long));
 if (numbers == NULL) {
 printf("内存分配失败\n");
 return 1;
 }
 printf("请输入%d 个正整数：\n", n);
 for (int i = 0; i < n; i++) {
 scanf("%lld", &numbers[i]);
 }
 // 对数组进行排序
 qsort(numbers, n, sizeof(long long), compareInt);
 printf("请输入%d 次查询的目标数：\n", m);
 for (int i = 0; i < m; i++) {
 long long target;
 scanf("%lld", &target);
 int occurrences = countOccurrences(numbers, n, target);
 printf("目标数 %lld 出现的次数为：%d\n", target, occurrences);
 }
 free(numbers);
 return 0;
}

三、全球变暖好危险

由于人类活动导致温室气体的大量排放，全球气温逐渐的在
上升，导致南极冰川正在融化，科学家预测在未来的几十年内，由于冰
川的融化，会导致许多海拔低的岛屿被海水淹没，小东在研究生面试的
时候被老师问到：假设给你一张卫星地图（为了国家安全，只能给你一
张灰度图，简单理解为只有 0 和 1，0 表示该地点没有岛屿，被海水覆
盖，1 表示该地点是岛屿）。请你判断一下若干年之后，这篇地图之上还
能看到的岛屿数目。

#include <stdio.h>
#include <stdlib.h>
#define MAX_ROWS 100
#define MAX_COLS 100
// 检查当前位置是否为岛屿且未被访问过
int isIsland(int map[MAX_ROWS][MAX_COLS], int row, int col, int rows, int cols) {
 return (row >= 0 && row < rows && col >= 0 && col < cols && map[row][col] 
== 1);
}
// 使用广度优先搜索（BFS）遍历连接的岛屿
void bfs(int map[MAX_ROWS][MAX_COLS], int row, int col, int rows, int cols) {
 // 定义上、下、左、右四个方向的偏移量
 int offsets[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
 Coordinate* queue = (Coordinate*) malloc(rows * cols * sizeof(Coordinate));
 int front = 0;
 int rear = 0;
 // 将起始位置加入队列
 Coordinate start;
 start.row = row;
 start.col = col;
 queue[rear++] = start;
 map[row][col] = -1; // 标记为已访问
 // 遍历队列中的位置
 while (front < rear) {
 Coordinate current = queue[front++];
 int currentRow = current.row;
 int currentCol = current.col;
 // 遍历四个方向
 for (int i = 0; i < 4; i++) {
 int newRow = currentRow + offsets[i][0];
 int newCol = currentCol + offsets[i][1];
 // 检查新位置是否为岛屿且未被访问过，如果是，则将其加入队列，
并标记为已访问
 if (isIsland(map, newRow, newCol, rows, cols)) {
 Coordinate next;
 next.row = newRow;
 next.col = newCol;
 queue[rear++] = next;
 map[newRow][newCol] = -1; // 标记为已访问
 }
 }
 }
 free(queue);
}
// 计算未来若干年后仍可见的岛屿数量
int countVisibleIslands(int map[MAX_ROWS][MAX_COLS], int rows, int cols) {
 int count = 0;
 // 遍历地图的每个位置
 for (int i = 0; i < rows; i++) {
 for (int j = 0; j < cols; j++) {
 // 如果当前位置是岛屿且未被访问过，进行广度优先搜索
 if (isIsland(map, i, j, rows, cols)) {
 bfs(map, i, j, rows, cols);
 count++;
 }
 }
 }
 return count;
}
int main() {
 int rows, cols;
 printf("请输入地图的行数和列数（以空格分隔）：");
 scanf("%d %d", &rows, &cols);
 int map[MAX_ROWS][MAX_COLS];
 printf("请输入地图数据（0 表示海水，1 表示岛屿）：\n");
 for (int i = 0; i < rows; i++) {
 for (int j = 0; j < cols; j++) {
 scanf("%d", &map[i][j]);
 }
 }
 int visibleIslands = countVisibleIslands(map, rows, cols);
 printf("若干年后仍可见的岛屿数量为：%d\n", visibleIslands);
 return 0;
}