华为OD机试 - 积木最远距离（Python/JS/C/C++ 2024 E卷 100分）

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

小华和小薇一起通过玩积木游戏学习数学。

他们有很多积木，每个积木块上都有一个数字，积木块上的数字可能相同。

小华随机拿一些积木块并排成一排，请你帮她找到这排积木中相同数字且所处位置最远的2块积木，计算它们的距离，小薇请你帮忙着地解决这个问题。

二、输入描述

第一行输入为N，表示小华排成一排的积木总数。

接下来N行每行一个数字，表示小华排成一排的积木上数字。

三、输出描述

相同数字的积木块位置最远距离；如果所有积木块的数字都不相同，请返回-1。

备注

0 <= 积木上的数字 < 10⁹

1 <= 积木长度 <= 10⁵

四、测试用例

测试用例1：

1、输入

5
1
2
3
1
4

2、输出

3、说明

共有5个积木，第1个和第4个积木数字相同，其距离为3。

测试用例2：

1、输入

2
1
2

2、输出

-1

3、说明

共有两个积木，没有积木数字相同，返回-1。

测试用例3：

1、输入

6
5
1
5
2
5
3

2、输出

3、说明

数字5在索引0、2、4出现。最大距离是4 - 0 = 4。

五、解题思路

为了找到一排积木中相同数字且位置最远的两块积木，我们可以采用以下步骤：

遍历积木序列：我们需要遍历整个积木序列，记录每个数字第一次出现的位置。
记录第一次出现的位置：使用一个哈希表（HashMap）来存储每个数字第一次出现的索引位置。
计算距离：当我们再次遇到已经存在于哈希表中的数字时，计算当前索引与第一次出现的索引之间的距离，并更新最大距离。
输出结果：遍历完成后，如果找到了至少一对相同数字的积木，输出最大的距离；否则，输出-1。

这种方法的时间复杂度为O(N)，适用于N高达10^5的情况。

六、Python算法源码

# 导入必要的模块
import sysdef main():# 读取输入N = int(sys.stdin.readline())  # 读取积木总数Nfirst_occurrence = {}  # 初始化哈希表，用于存储数字第一次出现的位置max_distance = -1  # 初始化最大距离为-1for i in range(N):num = int(sys.stdin.readline())  # 读取当前积木上的数字if num in first_occurrence:# 计算当前索引与第一次出现索引之间的距离distance = i - first_occurrence[num]if distance > max_distance:max_distance = distance  # 更新最大距离else:# 记录数字第一次出现的位置first_occurrence[num] = i# 输出结果print(max_distance)if __name__ == "__main__":main()

七、JavaScript算法源码

// 导入读取输入的模块
const readline = require('readline');function main() {const rl = readline.createInterface({input: process.stdin,output: process.stdout});let input = [];rl.on('line', (line) => {input.push(line);});rl.on('close', () => {let N = parseInt(input[0]); // 读取积木总数Nlet firstOccurrence = new Map(); // 初始化哈希表let maxDistance = -1; // 初始化最大距离为-1for (let i = 0; i < N; i++) {let num = BigInt(input[i + 1]); // 读取当前积木上的数字，使用BigInt处理大数if (firstOccurrence.has(num)) {// 计算当前索引与第一次出现索引之间的距离let distance = i - firstOccurrence.get(num);if (distance > maxDistance) {maxDistance = distance; // 更新最大距离}} else {// 记录数字第一次出现的位置firstOccurrence.set(num, i);}}// 输出结果console.log(maxDistance);});
}main();

八、C算法源码

#include <stdio.h>
#include <stdlib.h>// 定义哈希表的大小
#define HASH_SIZE 100003// 定义哈希表节点结构
typedef struct Node {long long key; // 数字int value; // 第一次出现的位置struct Node* next; // 指向下一个节点的指针
} Node;// 哈希函数
int hash_func(long long key) {return key % HASH_SIZE;
}int main(){int N;scanf("%d", &N); // 读取积木总数N// 初始化哈希表Node* hash_table[HASH_SIZE];for(int i=0;i<HASH_SIZE;i++) {hash_table[i] = NULL;}int maxDistance = -1; // 初始化最大距离为-1for(int i=0; i<N; i++) {long long num;scanf("%lld", &num); // 读取当前积木上的数字int hash_index = hash_func(num); // 计算哈希值Node* current = hash_table[hash_index];int found = 0;while(current != NULL){if(current->key == num){// 计算当前索引与第一次出现索引之间的距离int distance = i - current->value;if(distance > maxDistance){maxDistance = distance; // 更新最大距离}found = 1;break;}current = current->next;}if(!found){// 插入新的节点到哈希表Node* newNode = (Node*)malloc(sizeof(Node));newNode->key = num;newNode->value = i;newNode->next = hash_table[hash_index];hash_table[hash_index] = newNode;}}// 输出结果printf("%d\n", maxDistance);// 释放内存for(int i=0;i<HASH_SIZE;i++) {Node* current = hash_table[i];while(current != NULL){Node* temp = current;current = current->next;free(temp);}}return 0;
}

九、C++算法源码

#include <iostream>
#include <unordered_map>
using namespace std;int main() {ios::sync_with_stdio(false); // 关闭同步，加快输入速度cin.tie(0); // 取消cin和cout的绑定int N;cin >> N; // 读取积木总数Nunordered_map<long long, int> firstOccurrence; // 初始化哈希表int maxDistance = -1; // 初始化最大距离为-1for (int i = 0; i < N; i++) {long long num;cin >> num; // 读取当前积木上的数字if (firstOccurrence.find(num) != firstOccurrence.end()) {// 计算当前索引与第一次出现索引之间的距离int distance = i - firstOccurrence[num];if (distance > maxDistance) {maxDistance = distance; // 更新最大距离}} else {// 记录数字第一次出现的位置firstOccurrence[num] = i;}}// 输出结果cout << maxDistance << "\n";return 0;
}