华为OD机试 - 最大社交距离 - TreeSet（Python/JS/C/C++ 2024 C卷 100分）

在这里插入图片描述

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

专栏导读

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

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

一、题目描述

疫情期间需要大家保证一定的社交距离，公司组织开交流会议。

座位一排共 N 个座位，编号分别为 [0, N - 1] , 要求员工一个接着一个进入会议室，并且可以在任何时候离开会议室。

满足：

每当一个员工进入时，需要坐到最大社交距离（最大化自己和其他人的距离的座位）；
如果有多个这样的座位，则坐到索引最小的那个座位。

二、输入描述

会议室座位总数 seatNum 。(1 <= seatNum <= 500)
员工的进出顺序 seatOrLeave 数组，元素值为 1，表示进场；元素值为负数，表示出场（特殊：位置 0 的员工不会离开）。
例如 - 4 表示坐在位置 4 的员工离开（保证有员工坐在该座位上）

三、输出描述

最后进来员工，他会坐在第几个位置，如果位置已满，则输出 - 1 。

1、输入

10
[1,1,1,1,-4,1]

2、输出

3、说明

核心思想：每当一个员工进入时，需要坐到最大社交距离。

0 0 0 0 0 0 0 0 0 0

第一次坐在了0的位置；1 0 0 0 0 0 0 0 0 0
第二次坐在了9的位置；1 0 0 0 0 0 0 0 0 1
第三次坐在了4的位置；1 0 0 0 1 0 0 0 0 1
第四次坐在了2的位置；1 0 1 0 1 0 0 0 0 1
第五次4离开了；1 0 1 0 0 0 0 0 0 1
第六次坐在了5的位置；1 0 1 0 0 1 0 0 0 1

四、测试用例

测试用例1

1、输入

10
[1,1,1,1,-4,1]

2、输出

3、说明

核心思想：每当一个员工进入时，需要坐到最大社交距离。

0 0 0 0 0 0 0 0 0 0

第一次坐在了0的位置；1 0 0 0 0 0 0 0 0 0
第二次坐在了9的位置；1 0 0 0 0 0 0 0 0 1
第三次坐在了4的位置；1 0 0 0 1 0 0 0 0 1
第四次坐在了2的位置；1 0 1 0 1 0 0 0 0 1
第五次4离开了；1 0 1 0 0 0 0 0 0 1
第六次坐在了5的位置；1 0 1 0 0 1 0 0 0 1

测试用例2

1、输入

12
[1,1,1,1,1,-2,-5,1]

2、输出

3、说明

第1次坐在了0的位置；1 0 0 0 0 0 0 0 0 0 0 0
第2次坐在了11的位置；1 0 0 0 0 0 0 0 0 0 0 1
第3次坐在了5的位置；1 0 0 0 0 1 0 0 0 0 0 1
第4次坐在了8的位置；1 0 0 0 0 1 0 0 1 0 0 1
第5次坐在了2的位置；1 0 1 0 0 1 0 0 1 0 0 1
第6次2离开了；1 0 1 0 0 1 0 0 1 0 0 1
第7次5离开了；1 0 0 0 0 0 0 0 1 0 0 1
第8次坐在了4的位置；1 0 0 0 1 0 0 0 1 0 0 1

五、解题思路

题目要求：每当一个员工进入时，需要坐到最大社交距离。

核心解题思路：

找到距离最远的两个1；
求其中间值，如果有两个，则取索引小的。

0表示无人坐，1表示有人坐；
第一个人坐在0的位置，第二个人坐在离0最远的的n-1位置；
两头都有人坐了，则找到距离最远的两个1，求其中间值，如果有两个，则取索引小的；
通过遍历已经坐过的位置sitArr，获取两个1的最远距离；
再通过折半取值，获取中间值；

六、Python算法源码

python">import sysdef find_distant_seat(arr, n):# 使用有序列表存储已占座位occupied = set()occupied_ordered = []last_seat = -1for command in arr:if command > 0:  # 进场if not occupied:occupied.add(0)occupied_ordered.append(0)last_seat = 0else:max_dist = 0seat = -1# 排序已占座位occupied_ordered.sort()# 检查第一个座位到第一个已占座位的距离first = occupied_ordered[0]if first != 0 and first > max_dist:max_dist = firstseat = 0# 检查两个已占座位之间的距离for i in range(1, len(occupied_ordered)):prev = occupied_ordered[i-1]current = occupied_ordered[i]dist = (current - prev) // 2candidate = prev + distif dist > max_dist:max_dist = distseat = candidate# 检查最后一个已占座位到最后一个座位的距离last = occupied_ordered[-1]if (n - 1 - last) > max_dist:seat = n -1if seat != -1 and seat not in occupied:occupied.add(seat)occupied_ordered.append(seat)last_seat = seatelse:last_seat = -1breakelse:  # 出场leave_seat = -commandif leave_seat != 0 and leave_seat in occupied:occupied.remove(leave_seat)occupied_ordered.remove(leave_seat)# 检查最后一个命令是否为进场，且座位未满if arr and arr[-1] > 0:if len(occupied) <= n:return last_seatelse:return -1return -1def main():# 读取输入n = int(sys.stdin.readline())input_line = sys.stdin.readline().strip()arr = list(map(int, input_line[1:-1].split(',')))# 计算结果ans = find_distant_seat(arr, n)# 输出结果print(ans)if __name__ == "__main__":main()

七、JavaScript算法源码

javascript">function findDistantSeat(arr, n) {// 使用有序数组存储已占座位let occupied = new Set();let occupiedOrdered = [];let lastSeat = -1;for (let command of arr) {if (command > 0) { // 进场if (occupied.size === 0) {occupied.add(0);occupiedOrdered.push(0);lastSeat = 0;} else {let maxDist = 0;let seat = -1;// 排序已占座位occupiedOrdered.sort((a, b) => a - b);// 检查第一个座位到第一个已占座位的距离let first = occupiedOrdered[0];if (first !== 0 && first > maxDist) {maxDist = first;seat = 0;}// 检查两个已占座位之间的距离for (let i = 1; i < occupiedOrdered.length; i++) {let prev = occupiedOrdered[i-1];let current = occupiedOrdered[i];let dist = Math.floor((current - prev) / 2);let candidate = prev + dist;if (dist > maxDist) {maxDist = dist;seat = candidate;}}// 检查最后一个已占座位到最后一个座位的距离let last = occupiedOrdered[occupiedOrdered.length -1];if ((n -1 - last) > maxDist) {seat = n -1;}if (seat !== -1 && !occupied.has(seat)) {occupied.add(seat);occupiedOrdered.push(seat);lastSeat = seat;} else {lastSeat = -1;break;}}} else { // 出场let leaveSeat = -command;if (leaveSeat !== 0 && occupied.has(leaveSeat)) {occupied.delete(leaveSeat);occupiedOrdered = occupiedOrdered.filter(seat => seat !== leaveSeat);}}}// 检查最后一个命令是否为进场，且座位未满if (arr.length > 0 && arr[arr.length -1] > 0) {if (occupied.size <= n) {return lastSeat;} else {return -1;}}return -1;
}// 读取输入并处理
function main() {const fs = require('fs');const input = fs.readFileSync('/dev/stdin', 'utf8').trim().split('\n');const n = parseInt(input[0]);const arr = input[1].slice(1, -1).split(',').map(Number);const ans = findDistantSeat(arr, n);console.log(ans);
}main();

八、C算法源码

#include <stdio.h>
#include <stdlib.h>typedef struct {int *data;int size;int capacity;
} TreeSet;void initSet(TreeSet *set) {set->capacity = 10;set->size = 0;set->data = (int *)malloc(set->capacity * sizeof(int));
}void addSet(TreeSet *set, int val) {// 简单插入保持有序if (set->size == set->capacity) {set->capacity *=2;set->data = (int *)realloc(set->data, set->capacity * sizeof(int));}int i =0;while(i < set->size && set->data[i] < val) i++;for(int j = set->size; j > i; j--){set->data[j] = set->data[j-1];}set->data[i] = val;set->size++;
}void removeSet(TreeSet *set, int val) {int i=0;while(i < set->size && set->data[i] != val) i++;if(i < set->size){for(int j=i; j < set->size -1; j++) {set->data[j] = set->data[j+1];}set->size--;}
}int findDistantSeat(int arr[], int m, int n){TreeSet occupied;initSet(&occupied);int lastSeat = -1;for(int i=0; i<m; i++){int command = arr[i];if(command >0){ // 进场if(occupied.size ==0){addSet(&occupied, 0);lastSeat =0;}else{int maxDist =0;int seat = -1;// 检查第一个座位到第一个已占座位的距离int first = occupied.data[0];if(first !=0 && first > maxDist){maxDist = first;seat =0;}// 检查两个已占座位之间的距离for(int j=1; j < occupied.size; j++){int prev = occupied.data[j-1];int current = occupied.data[j];int dist = (current - prev)/2;int candidate = prev + dist;if(dist > maxDist){maxDist = dist;seat = candidate;}}// 检查最后一个已占座位到最后一个座位的距离int last = occupied.data[occupied.size -1];if((n-1 - last) > maxDist){seat = n-1;}if(seat != -1){addSet(&occupied, seat);lastSeat = seat;}else{lastSeat = -1;break;}}}else{ // 出场int leaveSeat = -command;if(leaveSeat !=0){removeSet(&occupied, leaveSeat);}}}// 检查最后一个命令是否为进场，且座位未满if(m >0 && arr[m-1] >0){if(occupied.size <=n){return lastSeat;}else{return -1;}}return -1;
}int main(){int n;scanf("%d", &n);char input[1000];scanf(" %[^\n]", input);int arr[500], m=0;char *token = strtok(input, ",[] ");while(token != NULL){arr[m++] = atoi(token);token = strtok(NULL, ",[] ");}int ans = findDistantSeat(arr, m, n);printf("%d", ans);return 0;
}

九、C++算法源码

#include <bits/stdc++.h>
using namespace std;int findDistantSeat(vector<int> arr, int n){set<int> occupied;int lastSeat = -1;for(auto command: arr){if(command >0){ // 进场if(occupied.empty()){occupied.insert(0);lastSeat =0;}else{int maxDist =0;int seat = -1;// 检查第一个座位到第一个已占座位的距离int first = *occupied.begin();if(first !=0 && first > maxDist){maxDist = first;seat =0;}// 检查两个已占座位之间的距离auto prev = occupied.begin();for(auto it = next(occupied.begin()); it != occupied.end(); ++it){int current = *it;int dist = (*it - *prev)/2;int candidate = *prev + dist;if(dist > maxDist){maxDist = dist;seat = candidate;}prev = it;}// 检查最后一个已占座位到最后一个座位的距离int last = *occupied.rbegin();if((n-1 - last) > maxDist){seat = n-1;}if(seat != -1){occupied.insert(seat);lastSeat = seat;}else{lastSeat = -1;break;}}}else{ // 出场int leaveSeat = -command;if(leaveSeat !=0){occupied.erase(leaveSeat);}}}// 检查最后一个命令是否为进场，且座位未满if(!arr.empty() && arr.back() >0){if(occupied.size() <=n){return lastSeat;}else{return -1;}}return -1;
}int main(){int n;cin >> n;string input;cin >> input;vector<int> arr;int num =0;bool negative = false;for(char c: input){if(c == '[' || c == ']' || c == ',') continue;if(c == '-'){negative = true;}else{if(isdigit(c)){num = num *10 + (c - '0');}else{if(negative){num = -num;}arr.push_back(num);num =0;negative = false;}}}// 添加最后一个数字if(input.back() != ',' && input.back() != ']'){if(negative){num = -num;}arr.push_back(num);}int ans = findDistantSeat(arr, n);cout << ans;
}