简单的小题集（五）

本文主要是介绍简单的小题集（五），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

一、签到两题不嫌多
二、数字出现的次数
三、全球变暖好危险

一、签到两题不嫌多

：现给定 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;
}