当前位置: 首页 > news >正文

华为OD机试真题---预定酒店


华为OD机试真题中的“预定酒店”题目是一道典型的算法题,主要考察的是如何在给定的酒店价格数组中找到最接近心理价位的k个酒店,并按价格从低到高输出。以下是对该题目的详细解析:

一、题目描述

放暑假了,小明决定到某旅游景点游玩,他在网上搜索到了各种价位的酒店(长度为n的数组A),他的心理价位是x元,请帮他筛选出k个最接近x元的酒店(n>=k>0),并由低到高打印酒店的价格。
备注:

1)酒店价格数组A和小明的心理价位x均为整型数据;(0 < n,k,x < 10000)

2)优先选择价格最接近心理价位的酒店;若两家酒店和心理价位差价相同,则选择价格较低的酒店。(比如100元和300元距离心理价位200元同样接近,此时选择100元);

3)酒店价格可能相同重复。

二、输入描述

  • 第一行:n,k,x,分别表示酒店价格数组的长度、需要筛选出的酒店数量以及小明的心理价位。
  • 第二行:A[0] A[1] A[2]…A[n-1],表示酒店的价格数组。

三、输出描述

从低到高打印筛选出的酒店价格。
补充说明:
1)酒店价格数组A和小明的心理价位x均为整型数据

2)优先选择价格最接近心理价位的酒店;若两家酒店距离心理价位差价相同,则选择价格较低的酒店。(比如100元和300元距离心理价位200元同样接近,此时选择100元)

3)酒店价格可能相同重复。

四、示例

示例1

  • 输入:5 3 10 12 15 10 9 11
  • 输出:9 10 11

示例2

  • 输入:10 4 6 1 2 3 4 5 6 7 8 9 10
  • 输出:4 5 6 7

五、解题思路

  1. 读取输入

    • 使用Scanner类读取输入的n、k、x以及酒店价格数组A。
  2. 计算差值

    • 遍历酒店价格数组A,计算每个酒店价格与心理价位x的差值diff = |price - x|
    • 创建一个类(如HotelPriceDiff)或数据结构(如Pair)来存储价格和差值信息,以便后续排序。
  3. 排序

    • 使用优先队列(最小堆)或自定义排序算法对价格和差值信息进行排序。
    • 排序规则:首先按照差值升序排序,如果差值相同则按照价格升序排序。
  4. 筛选结果

    • 从排序后的结果中取出前k个酒店价格。
    • 由于题目要求按价格从低到高输出,可以使用TreeSetPriorityQueue(最小堆)来自动排序结果,或者手动对结果进行排序。
  5. 输出

    • 打印筛选出的k个酒店价格。

六、解题策略

  1. 数据结构选择

    • 使用优先队列(最小堆)可以高效地获取最接近心理价位的k个酒店,因为优先队列可以在O(log k)时间内完成插入和删除操作。
    • 使用TreeSet可以自动对结果进行排序,但需要注意TreeSet的插入和删除操作时间复杂度为O(log n)。
  2. 算法效率

    • 遍历酒店价格数组计算差值的时间复杂度为O(n)。
    • 优先队列的插入和删除操作时间复杂度为O(log k),因此整体排序的时间复杂度为O(n log k)。
    • 如果使用TreeSet进行排序,则整体排序的时间复杂度为O(n log n),但在k较小且n较大时,优先队列通常更高效。
  3. 内存使用

    • 优先队列和TreeSet都会占用额外的内存来存储元素和进行比较操作。
    • 如果内存使用是一个关键因素,可以考虑使用数组和手动排序算法来减少内存占用。

七、代码实现(队列)


import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.TreeSet;public class HotelSelection {// 定义一个内部类来存储价格和差值信息static class HotelPriceDiff {int price;int diff;HotelPriceDiff(int price, int diff) {this.price = price;this.diff = diff;}}public static void main(String[] args) {// 创建Scanner对象以读取输入Scanner scanner = new Scanner(System.in);// 读取输入int n = scanner.nextInt(); // 酒店数量int k = scanner.nextInt(); // 需要选择的酒店数量int x = scanner.nextInt(); // 顾客的心理价位// 创建一个数组来存储每家酒店的价格int[] prices = new int[n];for (int i = 0; i < n; i++) {prices[i] = scanner.nextInt();}// 使用优先队列(最小堆)来存储价格和差值信息PriorityQueue<HotelPriceDiff> pq = new PriorityQueue<>((a, b) -> {// 自定义比较规则:首先按照差值升序排序,差值相同则按照价格升序排序if (a.diff != b.diff) {return Integer.compare(a.diff, b.diff);} else {return Integer.compare(a.price, b.price);}});// 计算每个酒店价格与顾客心理价位的差值,并将酒店信息加入优先队列for (int price : prices) {int diff = Math.abs(price - x);pq.offer(new HotelPriceDiff(price, diff));}// 从优先队列中取出前k个最接近心理价位的酒店价格TreeSet<Integer> result = new TreeSet<>(); // 使用TreeSet自动排序结果while (!pq.isEmpty() && result.size() < k) {result.add(pq.poll().price);}// 打印结果for (int price : result) {System.out.print(price + " ");}}
}

八、代码实现(数组)

import java.util.*;  public class HotelReservation {  // 定义一个内部类来存储价格和差值  static class PriceDiff {  int diff;  int price;  PriceDiff(int diff, int price) {  this.diff = diff;  this.price = price;  }  }  public static void main(String[] args) {  Scanner scanner = new Scanner(System.in);  // 读取输入  int n = scanner.nextInt();  int k = scanner.nextInt();  int x = scanner.nextInt();  int[] prices = new int[n];  for (int i = 0; i < n; i++) {  prices[i] = scanner.nextInt();  }  // 计算差值并存储在一个列表中  List<PriceDiff> priceDiffs = new ArrayList<>();  for (int price : prices) {  int diff = Math.abs(price - x);  priceDiffs.add(new PriceDiff(diff, price));  }  // 根据差值排序,如果差值相同则按价格排序  Collections.sort(priceDiffs, Comparator.comparingInt(a -> a.diff).thenComparingInt(a -> a.price));  // 筛选前k个价格  List<Integer> topKPrices = new ArrayList<>();  for (int i = 0; i < k; i++) {  topKPrices.add(priceDiffs.get(i).price);  }  // 对结果排序(虽然已经在上一步中按差值排序过,但题目要求按价格排序,这里再次确保)  Collections.sort(topKPrices);  // 输出结果  for (int price : topKPrices) {  System.out.print(price + " ");  }  }  
}示例1:输入:5 3 10 12 15 10 9 11
输出:9 10 11

九、注意事项

  1. 输入验证:在实际应用中,需要对输入进行验证,确保n、k、x以及价格数组A的输入格式正确。
  2. 性能优化:在处理大规模数据时,需要注意算法的性能优化,如使用更高效的数据结构或算法来减少时间复杂度。
  3. 边界情况:需要考虑边界情况,如k等于n、价格数组A中有重复价格等。

十、运行实例解析

输入
10 5 6
1 2 3 4 5 6 7 8 9 10
  1. 读取输入

    • n = 10:表示酒店价格数组的长度。
    • k = 5:表示需要筛选出的最接近心理价位的酒店数量。
    • x = 6:表示小明的心理价位。
    • A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]:表示酒店的价格数组。
  2. 计算差值

    • 对于每个价格,计算其与心理价位x的差值diff = |price - x|
  3. 使用优先队列(最小堆)

    • 创建一个优先队列,按照差值升序排序,差值相同时按价格升序排序。
    • 将每个价格及其差值加入优先队列。
  4. 筛选前k个价格

    • 从优先队列中依次取出前k个元素(即最接近心理价位的酒店价格)。
    • 由于优先队列已经按照差值和价格排序,所以取出的前k个元素就是符合条件的酒店价格。
  5. 输出结果

    • 将筛选出的酒店价格按升序打印出来。

十一、运行步骤

  1. 初始化优先队列。

  2. 遍历价格数组[1, 2, 3, 4, 5, 6, 7, 8, 9, 10],计算差值并加入优先队列:

    • 1:差值5
    • 2:差值4
    • 3:差值3
    • 4:差值2
    • 5:差值1
    • 6:差值0(最接近)
    • 7:差值1
    • 8:差值2
    • 9:差值3
    • 10:差值4

    优先队列中的元素(按差值和价格排序)将是:

    • (6, 0)
    • (5, 1)
    • (7, 1)
    • (4, 2)
    • (8, 2)
    • (3, 3)
    • (9, 3)
    • (2, 4)
    • (10, 4)
    • (1, 5)(但实际上我们只需要前5个)
  3. 从优先队列中取出前5个元素:

    • 6
    • 5
    • 7
    • 4
    • 8
  4. 打印输出结果:

    4 5 6 7 8
    

十二、结论

对于给定的输入,程序将正确地筛选出最接近心理价位6的5个酒店价格,并按升序打印出来。输出结果为4 5 6 7 8,与预期相符。

相关文章:

华为OD机试真题---预定酒店

华为OD机试真题中的“预定酒店”题目是一道典型的算法题&#xff0c;主要考察的是如何在给定的酒店价格数组中找到最接近心理价位的k个酒店&#xff0c;并按价格从低到高输出。以下是对该题目的详细解析&#xff1a; 一、题目描述 放暑假了&#xff0c;小明决定到某旅游景点游…...

力扣242.有效的字母异位词

题目链接&#xff1a;242. 有效的字母异位词 - 力扣&#xff08;LeetCode&#xff09; 给定两个字符串 s 和 t &#xff0c;编写一个函数来判断 t 是否是 s 的 字母异位词。 示例 1: 输入: s "anagram", t "nagaram"输出: true 示例 2: 输入: s &q…...

Android IP路由策略和防火墙

Android IP路由策略和防火墙 Platform: RK3368 OS: Android 6.0 Kernel: 3.10.0 文章目录 Android IP路由策略和防火墙ip route, ip rule, iptables简介ip routeip ruleiptables Android路由策略Android路由策略优先级命令查看当前路由策略 Android路由表命令查看路由表命令…...

MySQL insert ... select 语句锁表导致数据写不进去

问题现象 调用后台接口向表 t1 insert 写入数据时一直等待直到超时&#xff0c;猜测表 t1 被其它事务加锁了没有释放。 问题分析 在发生死锁时&#xff0c;通过执行下面命令查看事务和锁信息&#xff1a; select * from information_schema.INNODB_TRX 用来查看正在运行的事…...

Android摄像头Camera2和Camera1的一些总结

Android 系统对摄像头的同时使用有限制&#xff0c;不能同时使用摄像头进行预览或者录制音视频。 例如&#xff1a;界面上有两个SurfaceView, 这两个SurfaceView不能同时预览或者录制音视频&#xff0c;只能有一个正常工作&#xff08;一个SurfaceView预览前置摄像头&#xff…...

【Linux 从基础到进阶】Linux中的用户认证与授权

Linux中的用户认证与授权 1. 引言 在Linux系统中&#xff0c;**用户认证&#xff08;authentication&#xff09;和授权&#xff08;authorization&#xff09;**是两个核心的安全机制&#xff0c;用来控制系统资源的访问和管理用户操作权限。用户认证确保登录的用户是合法的…...

用户界面设计:视觉美学与交互逻辑的融合

1、什么是用户界面 用户界面&#xff08;UI&#xff09;是人与机器之间沟通的桥梁&#xff0c;同时也是用户体验&#xff08;UX&#xff09;的重要组成部分。用户界面设计包括两个核心要素&#xff1a;视觉设计&#xff08;即产品的外观和感觉&#xff09;和交互设计&#xff…...

ZK集群搭建:详细步骤与注意事项

在大数据和分布式系统日益重要的今天&#xff0c;ZooKeeper&#xff08;简称ZK&#xff09;作为一种分布式协调服务&#xff0c;扮演着举足轻重的角色。它主要用于管理大型分布式系统中的配置信息、命名、同步等。下面将详细介绍如何搭建一个ZooKeeper集群&#xff0c;帮助大家…...

如何将csdn文章导出为pdf

前言 在csdn上浏览文章的时候我发现有的文章支持pdf导出&#xff0c;但是有的文章不支持pdf导出&#xff0c;为了解决能将csdn上所有文章都能以pdf格式导出遂作此文。 正文 先上代码&#xff1a; (function(){use strict;var contentBox $("div.article_content")…...

【艾思科蓝】Imagen:重塑图像生成领域的革命性突破

【连续七届已快稳ei检索】第八届电子信息技术与计算机工程国际学术会议&#xff08;EITCE 2024&#xff09;_艾思科蓝_学术一站式服务平台 更多学术会议请看 学术会议-学术交流征稿-学术会议在线-艾思科蓝 目录 引言 一、Imagen模型的技术原理 1. 模型概述 2. 工作流程 …...

java类和对象(下): 封装 static成员 内部类

前言&#xff1a; 在前期的知识点中&#xff0c;我们学习了java中this函数的使用和相关的概念。这期我们将介绍封装的概念&#xff0c;以及常见内部类的使用&#xff0c;让我们开车吧&#xff01;&#xff01;&#xff01;&#xff01; 本期目录&#xff1a; 6. 封装 7. st…...

外包干了3周,技术退步太明显了。。。。。

先说一下自己的情况&#xff0c;大专生&#xff0c;21年通过校招进入武汉某软件公司&#xff0c;干了差不多3个星期的功能测试&#xff0c;那年国庆&#xff0c;感觉自己不能够在这样下去了&#xff0c;长时间呆在一个舒适的环境会让一个人堕落!而我才在一个外包企业干了3周的功…...

VIVO算法题——数位之积

记录算法究极无敌菜菜菜鸟的垃圾思维 题目&#xff1a; 现给定任意正整数 n&#xff0c;请寻找并输出最小的正整数 m&#xff08;m>9&#xff09;&#xff0c;使得 m 的各位&#xff08;个位、十位、百位 … …&#xff09;之乘积等于n&#xff0c;若不存在则输出 -1。 菜鸟…...

OPC Router快速打通设备层与influxDB数据通讯

随着时代演化&#xff0c;数据量呈几何倍数增加的情况下出现了时序数据库。时序数据库是基于时间进行存储的数据库&#xff0c;每一条数据中都有一个时间戳&#xff0c;这种数据库特别适合存储那些随着时间变化的数据&#xff0c;通过一些工具处理后&#xff0c;能够分析出数据…...

鸿蒙开发 四十四 ArkTs BuilderParam传递UI(二)

子组件多个BuilderParam&#xff0c;必须通过参数的方式传入&#xff0c;如果界面中有多个界面需要传递&#xff0c;可以定义多个尾随闭包&#xff0c;如图&#xff1a; 在自定义组件中调用&#xff1a; 在使用时候调用是作为参数传递给自定义的组件&#xff0c;参数是界面&…...

同期数分析-留存率

目录 同期数分析 加载数据 单月实现 统计每个月的订单量 求2月份的订单量和用户数量 求2月之前的历史订单量 筛选出2023年2月的新增的用户数 计算2023年2月在后面的留存情况 完整的2023年2月份同期群结果 遍历合并和分析 引入月份列表 遍历 调整成留存率的形式 回…...

Java前后端交互:构建现代Web应用

在现代Web应用开发中&#xff0c;前后端分离是一种常见的架构模式。后端通常负责数据处理和业务逻辑&#xff0c;而前端则负责用户界面和用户体验。Java作为后端开发的强大语言&#xff0c;提供了多种方式与前端进行交互。本文将探讨Java后端与前端交互的几种主要方式&#xff…...

vue3中用axios请求怎么添加cookie

在 Vue 3 中使用 axios 发起请求时&#xff0c;可以通过配置 axios 的请求选项来携带 Cookies。具体来说&#xff0c;确保跨域请求时&#xff0c;设置 withCredentials: true&#xff0c;以便发送和接收 Cookies。 1. Axios 配置携带 Cookie 首先确保你在 axios 请求中设置了…...

informer学习笔记

一、informer讲解 infomer 要解决的三大问题&#xff1a; Attention计算的更快Decoder要一次性输出所有预测堆叠encoder也要更快 1. Attention 在长序列中&#xff0c;并非每一个位置的Attention都重要&#xff0c;对于每一个Q来说&#xff0c;只有一小部分的K与其有较强的…...

Elasticsearch介绍和使用

一、Elasticsearch 强大的搜索和分析能力&#xff1a; Elasticsearch 是一个基于 Lucene 的分布式搜索和分析引擎。它能够快速地对大量数据进行全文搜索、结构化搜索和复杂的数据分析操作。对于大型数据集&#xff0c;它可以高效地处理各种查询需求&#xff0c;包括关键词搜索…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:

一、属性动画概述NETX 作用&#xff1a;实现组件通用属性的渐变过渡效果&#xff0c;提升用户体验。支持属性&#xff1a;width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项&#xff1a; 布局类属性&#xff08;如宽高&#xff09;变化时&#…...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

基于当前项目通过npm包形式暴露公共组件

1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹&#xff0c;并新增内容 3.创建package文件夹...

企业如何增强终端安全?

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信

文章目录 Linux C语言网络编程详细入门教程&#xff1a;如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket&#xff08;服务端和客户端都要&#xff09;2. 绑定本地地址和端口&#x…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

GruntJS-前端自动化任务运行器从入门到实战

Grunt 完全指南&#xff1a;从入门到实战 一、Grunt 是什么&#xff1f; Grunt是一个基于 Node.js 的前端自动化任务运行器&#xff0c;主要用于自动化执行项目开发中重复性高的任务&#xff0c;例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...

uniapp手机号一键登录保姆级教程(包含前端和后端)

目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号&#xff08;第三种&#xff09;后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...