网站规划的基本步骤/百度知道问答
OD统一考试(C卷)
分值: 200分
题解: Java / Python / C++
题目描述
疫情期间,需要大家保证一定的社交距离,公司组织开交流会议,座位有一排共N个座位,编号分别为[0…N-1],要求员工一个接着一个进入会议室,并且可以在任何时候离开会议室。
满足:每当一个员工进入时,需要坐到最大社交距离的座位(例如:位置A与左右有员工落座的位置距离分别为2和2,位置B与左右有员工落座的位置距离分别为2和3,影响因素都为2个位置,则认为座位A和B与左右位置的社交距离是一样的),如果有多个这样的座位,则坐到索引最小的那个座位。
输入描述
会议室座位总数seatNum,(1 <= seatNum <= 500) 员工的进出顺序 seatOrLeave数组,元素值为1: 表示进场,元素值为负数,表示出场(特殊:位置0的员工不会离开)。
例如-4表示坐在位置4的员工离开 (保证有员工坐在该座位上)。
输出描述
最后进来员工,他会坐在第几个位置,如果位置已满,则输出-1。
示例1
输入:
10
[1, 1, 1, 1, -4, 1]输出:
5说明:
seat ->0,坐在任何位置都行,但是要给他安排索引最小的位置,也就是座位0。
seat ->9, 要和旁边的人距离最远,也就是座位9。
seat ->4,位置4与0和9的距离为(4和5),位置5与0和9的距离(5和4),所以位置4和5都是可以选择的座位,按照要求需索引最小的那个座位,也就是座位4。
seat ->2,位置2与0和4的距离为(2和2),位置6与4和9的距离(2和3),位置7与4和9的距离(3和2),影响因素都为2个位置,按照要求需索引最小的那个座位,也就是座位2。leave(4),4号座位的员工离开。
seat-> 5,员工最后坐在5号座位上。
此题为非ACM模式,只需要实现 conferenceSeatDistance 方法即可。
题解
这是一个模拟会议室座位安排的问题,需要根据特定规则安排员工的座位。
- 使用有序 Set 来维护已经被坐的座位情况(java 代码使用 TreeSet )。并通过插入两个虚拟的座位作为边界来方便计算最大社交距离的座位。
- 进入会议室的算法: 使用
join
方法来计算员工进入会议室时的最佳座位。通过遍历 TreeSet 中相邻的位置,计算中间座位的社交距离,找到最大距离的座位,并插入到 TreeSet 中。- 座位计算: 在主方法中,遍历员工的进出顺序,根据不同情况调用
join
方法或者从TreeSet中移除座位。- 输出: 输出最后一个员工坐的位置。
Java
import java.util.Iterator;
import java.util.Scanner;
import java.util.TreeSet;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int seatNum = sc.nextInt();sc.nextLine();String seatOrLeaveLine = sc.nextLine();String[] c = seatOrLeaveLine.substring(1, seatOrLeaveLine.length() - 1).split(", ");int[] seatOrLeave = new int[c.length];for (int i = 0; i < c.length; i++) {seatOrLeave[i] = Integer.parseInt(c[i]);}Main socialDistance = new Main();int ans = socialDistance.conferenceSeatDistance(seatNum, seatOrLeave);System.out.println(ans);}/*** 计算最后进来的人,坐的位置** @param seatNum 会议室座位总数* @param seatOrLeave 员工的进出顺序* @return 最后进来的人,坐的位置*/public int conferenceSeatDistance(int seatNum, int[] seatOrLeave) {TreeSet<Integer> seatTree = new TreeSet<>();// 插入两个虚拟的座位,有了这两个个边界方便计算最大社交距离的座位seatTree.add(-2 * (seatNum - 1));seatTree.add(2 * (seatNum - 1));int last = -1;for (int t : seatOrLeave) {if (t == 1) { // 进来last = join(seatTree, seatNum);} else { // 座位 -t 的人离开seatTree.remove(-t);}}return last;}/*** 计算员工进行会议该做的位置** @param seatTree 已经被坐的座位情况* @param N 会议室座位个数* @return -1 没有合适的位置可坐*/public int join(TreeSet<Integer> seatTree, int N) {// 最大的社交距离int maxDistance = 0, idx = -1;// 根据 TreeSet key 的有序性,遍历所有相邻的位置看中间的座位是否是会议室中社交距离最大的座位Iterator<Integer> it = seatTree.iterator();int pre = it.next();while (it.hasNext()) {int cur = it.next();int distance = (cur - pre) / 2;// 判断在 pre 和 cur 中间坐社交距离是否更大 if (distance > maxDistance) {// 坐在 pre 和 pre 中间的位置(索引最小的)int pos = (cur + pre) / 2;// 当前 pos 是有效的可坐位置if (0 <= pos && pos < N) {idx = pos;maxDistance = distance;}}pre = cur;}// 找到了合适的座位,则坐在 idx 位置上if (idx != -1) seatTree.add(idx);return idx;}
}
Python
from itertools import pairwiseclass Solution:def conference_seat_distance(self, seat_num, seat_or_leave):# 记录座位情况self.seat_list = [-2 * (seat_num - 1), 2 * (seat_num - 1)]last = -1for t in seat_or_leave:if t == 1: # 进来last = self.join(seat_num)else: # 座位 -t 的人离开self.seat_list.remove(-t)return lastdef join(self, N):max_distance, idx = 0, -1# 遍历所有相邻的位置看中间的座位是否是会议室中社交距离最大的座位for pre, cur in pairwise(self.seat_list):distance = (cur - pre) // 2# 判断在 pre 和 cur 中间坐社交距离是否更大if distance > max_distance:# 坐在 pre 和 pre 中间的位置(索引最小的)pos = (cur + pre) // 2# 当前 pos 是有效的可坐位置if 0 <= pos < N:idx = posmax_distance = distance# 找到了合适的座位,则坐在 idx 位置上if idx != -1:self.seat_list.append(idx)self.seat_list.sort()return idxsolution = Solution()
last = solution.conference_seat_distance(10, [1, 1, 1, 1, -4, 1])
print(last)
C++
#include <iostream>
#include <vector>
#include <set>using namespace std;class Solution {
public:int conferenceSeatDistance(int seatNum, vector<int>& seatOrLeave) {set<int> seatTree;seatTree.insert(-2 * (seatNum - 1));seatTree.insert(2 * (seatNum - 1));int last = -1;for (int t : seatOrLeave) {if (t == 1) {last = join(seatTree, seatNum);} else {seatTree.erase(-t);}}return last;}int join(set<int>& seatTree, int N) {int maxDistance = 0, idx = -1;auto it = seatTree.begin();int pre = *it++;while (it != seatTree.end()) {int cur = *it++;int distance = (cur - pre) / 2;if (distance > maxDistance) {int pos = (cur + pre) / 2;if (pos >= 0 && pos < N) {idx = pos;maxDistance = distance;}}pre = cur;}if (idx != -1) seatTree.insert(idx);return idx;}
};
❤️华为OD机试面试交流群(每日真题分享): 加V时备注“华为od加群”
🙏整理题解不易, 如果有帮助到您,请给点个赞 ❤️ 和收藏 ⭐,让更多的人看到。🙏🙏🙏
相关文章:

选座位 - 华为OD统一考试(C卷)
OD统一考试(C卷) 分值: 200分 题解: Java / Python / C 题目描述 疫情期间,需要大家保证一定的社交距离,公司组织开交流会议,座位有一排共N个座位,编号分别为[0…N-1],要…...

【微服务】mybatis typehandler使用详解
目录 一、前言 二、TypeHandler简介 2.1 什么是TypeHandler 2.1.1 TypeHandler特点 2.2 TypeHandler原理 2.3 mybatis自带的TypeHandler 三、环境准备 3.1 准备一张数据表 3.2 搭建一个springboot工程 3.2.1 基础依赖如下 3.2.2 核心配置文件 3.2.3 测试接口 四、T…...

计网 - 深入理解HTTPS:加密技术的背后
文章目录 Pre发展历史Http VS HttpsHTTPS 解决了 HTTP 的哪些问题HTTPS是如何解决上述三个风险的混合加密摘要算法 数字签名数字证书 Pre PKI - 数字签名与数字证书 PKI - 借助Nginx 实现Https 服务端单向认证、服务端客户端双向认证 发展历史 HTTP(超文本传输协…...

Jmeter之单接口的性能测试
前言: 服务端的整体性能测试是一个非常复杂的概念,包含生成虚拟用户,模拟并发,分析性能结果等各种技术,期间可能还要解决设计场景、缓存影响、第三方接口mock、IP限制等问题。如何用有限的测试机器,在测试环…...

成像光谱遥感技术中的AI革命:ChatGPT应用指南
“成像光谱遥感技术中的人工智能革命:ChatGPT应用指南”,这是一门旨在改变您使用人工智能处理遥感数据的方式。将最新的人工智能技术与实际的遥感应用相结合,提供不仅是理论上的,而且是适用和可靠的工具和方法。无论你是经验丰富的…...

掌握BeautifulSoup4:爬虫解析器的基础与实战【第91篇—BeautifulSoup4】
掌握BeautifulSoup4:爬虫解析器的基础与实战 网络上的信息浩如烟海,而爬虫技术正是帮助我们从中获取有用信息的重要工具。在爬虫过程中,解析HTML页面是一个关键步骤,而BeautifulSoup4正是一款功能强大的解析器,能够轻…...

从源码解析Kruise(K8S)原地升级原理
从源码解析Kruise原地升级原理 本文从源码的角度分析 Kruise 原地升级相关功能的实现。 本篇Kruise版本为v1.5.2。 Kruise项目地址: https://github.com/openkruise/kruise 更多云原生、K8S相关文章请点击【专栏】查看! 原地升级的概念 当我们使用deployment等Wor…...

2024年【广东省安全员C证第四批(专职安全生产管理人员)】复审考试及广东省安全员C证第四批(专职安全生产管理人员)模拟考试题
题库来源:安全生产模拟考试一点通公众号小程序 广东省安全员C证第四批(专职安全生产管理人员)复审考试是安全生产模拟考试一点通总题库中生成的一套广东省安全员C证第四批(专职安全生产管理人员)模拟考试题࿰…...

udp服务器【Linux网络编程】
目录 一、UDP服务器 1、创建套接字 2、绑定套接字 3、运行 1)读取数据 2)发送数据 二、UDP客户端 创建套接字: 客户端不用手动bind 收发数据 处理消息和网络通信解耦 三、应用场景 1、服务端执行命令 2、Windows上的客户端 3…...

【k8s资源调度-Deployment】
1、标签和选择器 1.1 标签Label 配置文件:在各类资源的sepc.metadata.label 中进行配置通过kubectl 命令行创建修改标签,语法如下 创建临时label:kubectl label po <资源名称> apphello -n <命令空间(可不加࿰…...

【Oracle】玩转Oracle数据库(五):PL/SQL编程
前言 嗨,各位数据库达人!准备好迎接数据库编程的新挑战了吗?今天我们要探索的是Oracle数据库中的神秘魔法——PL/SQL编程!🔮💻 在这篇博文【Oracle】玩转Oracle数据库(五)࿱…...

JavaScript流程控制
文章目录 1. 顺序结构2. 分支结构2.1 if 语句2.2 if else 双分支语句2.3 if else if 多分支语句三元表达式 2.4 switch 语句switch 语句和 if else if语句区别 3. 循环结构3.1 for 循环断点调试 3.2 双重 for 循环3.3 while 循环3.4 do while 循环3.5 contiue break 关键字 4. …...

五个使用Delphi语言进行开发的案例
案例一:学生信息管理系统 某学校需要开发一个学生信息管理系统,用于记录学生的基本信息、成绩和考勤情况等。开发者使用Delphi语言进行开发,设计了一个包含多个窗体的应用程序。主窗体用于展示学生的列表和基本信息,其他窗体则用…...

蓝桥杯第1374题——锻造兵器
题目描述 小明一共有n块锻造石,第块锻造石的属性值为ai. 现在小明决定从这n块锻造石中任取两块来锻造兵器 通过周密计算,小明得出,只有当两块锻造石的属性值的差值等于C,兵器才能锻造成功 请你帮小明算算,他有多少种选…...

坚鹏:政府数字化转型数字机关、数据共享及电子政务类案例研究
政府数字化转型数字机关、数据共享及电子政务类案例研究 课程背景: 很多地方政府存在以下问题: 不清楚政府数字化转型的数字机关类成功案例 不清楚政府数字化转型的数据共享类成功案例 不清楚政府数字化转型的电子政务类成功案例 课程特色&…...

【架构】面向人工智能 (AI) 的硬件的可靠性(2021)
由于激进的技术扩展,现代系统越来越容易受到可靠性威胁的影响,例如软错误、老化和工艺变化。这些威胁在硬件级别表现为位翻转,并且根据位置,可能会损坏输出,从而导致不准确或潜在的灾难性结果。 传统的缓解技术基于冗…...

Unity3D MVC开发模式与开发流程详解
前言 MVC(Model-View-Controller)是一种常用的软件架构模式。将MVC应用于Unity3D开发可以提高项目的可维护性和可扩展性,使代码更加清晰和易于理解。本文将详细介绍Unity3D中MVC开发模式的应用以及开发流程,并给出技术详解和代码…...

简单介绍一下Android里面的IntentFirewall
源码链接 https://android.googlesource.com/platform/frameworks/base//633dc9b/services/java/com/android/server/firewall/IntentFirewall.java 源码如下: package com.android.server.firewall; import android.content.Intent; import android.content.Inte…...

Stable Diffusion 3 发布及其重大改进
1. 引言 就在 OpenAI 发布可以生成令人瞠目的视频的 Sora 和谷歌披露支持多达 150 万个Token上下文的 Gemini 1.5 的几天后,Stability AI 最近展示了 Stable Diffusion 3 的预览版。 闲话少说,我们快来看看吧! 2. 什么是Stable Diffusion…...

【后端】springboot项目
文章目录 1. 2.3.7.RELEASE版本搭建1.1 pom文件1.1.1 方式一1.1.2 方式二 1.2 启动类1.3 测试类 2. 引入Value乱码问题解决 【后端目录贴】 1. 2.3.7.RELEASE版本搭建 1.1 pom文件 1.1.1 方式一 <parent><groupId>org.springframework.boot</groupId><…...

React Native调用摄像头画面及拍照和保存图片到相册全流程
今天主要做了一个demo,功能很简单,就是调用手机摄像头画面,并且可以通过按钮控制拍照以及将图片保存到手机相册的功能,接下来我将从创建项目开始一步一步完成这个demo,各位只需要复制粘贴即可 创建React Native项目 npx react-native init yx_rnDemo --version 0.70.6 // 这里…...

Kubernetes基本部署概念
文章目录 命名空间(Namespaecs)查看命名空间查看带有命名空间对象下资源 文件存储持久卷(pv,Persistent Volumes)卷容量卷模式(volumeMode)访问模式(accessModes)回收策略…...

QT c++ 海康红外热像仪
//本文描述2通道海康通道红外热像仪预览和抓图 #include "mainwindow.h" #include "ui_mainwindow.h" MainWindow::MainWindow(QWidget *parent) : QMainWindow(parent) , ui(new Ui::MainWindow) { ui->setupUi(this); userID-1; …...

OpenAI 的 GPTs 提示词泄露攻击与防护实战:防御卷(一)
前面的OpenAI DevDay活动上,GPTs技术的亮相引起了广泛关注。随着GPTs的创建权限开放给Plus用户,社区里迅速涌现了各种有趣的GPT应用,这些都是利用了Prompt提示词的灵活性。这不仅展示了技术的创新潜力,也让人们开始思考如何获取他…...

中科大计网学习记录笔记(十五):可靠数据传输的原理
前前言:看过本节的朋友应该都知道本节长度长的吓人,但其实内容含量和之前的差不多,老师在本节课举的例子和解释比较多,所以大家坚持看完是一定可以理解透彻的。本节课大部分是在提出问题和解决问题,先明确出现的问题是…...

五种多目标优化算法(MOGWO、MOJS、NSWOA、MOPSO、MOAHA)性能对比(提供MATLAB代码)
一、5种多目标优化算法简介 1.1MOGWO 1.2MOJS 1.3NSWOA 1.4MOPSO 1.5MOAHA 二、5种多目标优化算法性能对比 为了测试5种算法的性能将其求解9个多目标测试函数(zdt1、zdt2 、zdt3、 zdt4、 zdt6 、Schaffer、 Kursawe 、Viennet2、 Viennet3)࿰…...

力扣:93. 复原 IP 地址
回溯: 1.先定义一个接收的集合,之后再定义一个记录小数点的变量。之后编写回溯函数,终止条件为小数点的个数为3时,同时要判断最后一段的组合的值是否属于ip地址的范围。之后再用for循环来遍历ip地址的组合,先判断组合…...

利用序列化和反序列化实现深拷贝
利用序列化和反序列化可以实现对象的深拷贝,具体步骤如下: 将要深拷贝的对象序列化为字节流。从字节流中反序列化出一个新的对象,即完成了深拷贝。下面是一个示例代码: import java.io.*;class MyClass implements Serializable {private static final long serialVersion…...

【AHK】68键键盘键位布局优化/esc改退格键/回车键
本人习惯使用~作为退格键,但是由于keychron 68键的布局只能用esc平替~来修改,然后也将回车键通过alt和大小写锁定键一起触发 esc::bs ;次步骤与下面步骤相对应,如果是用send bs方式则下面的不生效^esc:: ;通过建立 保留esc功能 send {esc} re…...

计算机体系架构初步入门
🎬个人简介:一个全栈工程师的升级之路! 📋个人专栏:高性能(HPC)开发基础教程 🎀CSDN主页 发狂的小花 🌄人生秘诀:学习的本质就是极致重复! 目录 1 计算机五大…...