简单的小题集(五)
2023-12-13 06:37:55
一、签到两题不嫌多
:现给定 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;
}
文章来源:https://blog.csdn.net/magic171/article/details/134946082
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!