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

🕗 发布于 2024-10-15 18:28 华为od 职场和发展 开发语言 java 数据结构

华为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

解题思路

读取输入：
- 使用Scanner类读取输入的n、k、x以及酒店价格数组A。
计算差值：
- 遍历酒店价格数组A，计算每个酒店价格与心理价位x的差值diff = |price - x|。
- 创建一个类（如HotelPriceDiff）或数据结构（如Pair）来存储价格和差值信息，以便后续排序。
排序：
- 使用优先队列（最小堆）或自定义排序算法对价格和差值信息进行排序。
- 排序规则：首先按照差值升序排序，如果差值相同则按照价格升序排序。
筛选结果：
- 从排序后的结果中取出前k个酒店价格。
- 由于题目要求按价格从低到高输出，可以使用TreeSet或PriorityQueue（最小堆）来自动排序结果，或者手动对结果进行排序。
输出：
- 打印筛选出的k个酒店价格。

解题策略

数据结构选择：
- 使用优先队列（最小堆）可以高效地获取最接近心理价位的k个酒店，因为优先队列可以在O(log k)时间内完成插入和删除操作。
- 使用TreeSet可以自动对结果进行排序，但需要注意TreeSet的插入和删除操作时间复杂度为O(log n)。
算法效率：
- 遍历酒店价格数组计算差值的时间复杂度为O(n)。
- 优先队列的插入和删除操作时间复杂度为O(log k)，因此整体排序的时间复杂度为O(n log k)。
- 如果使用TreeSet进行排序，则整体排序的时间复杂度为O(n log n)，但在k较小且n较大时，优先队列通常更高效。
内存使用：
- 优先队列和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

注意事项

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

运行实例解析

输入

10 5 6
1 2 3 4 5 6 7 8 9 10

读取输入：
- n = 10：表示酒店价格数组的长度。
- k = 5：表示需要筛选出的最接近心理价位的酒店数量。
- x = 6：表示小明的心理价位。
- A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]：表示酒店的价格数组。
计算差值：
- 对于每个价格，计算其与心理价位x的差值diff = |price - x|。
使用优先队列（最小堆）：
- 创建一个优先队列，按照差值升序排序，差值相同时按价格升序排序。
- 将每个价格及其差值加入优先队列。
筛选前k个价格：
- 从优先队列中依次取出前k个元素（即最接近心理价位的酒店价格）。
- 由于优先队列已经按照差值和价格排序，所以取出的前k个元素就是符合条件的酒店价格。
输出结果：
- 将筛选出的酒店价格按升序打印出来。

运行步骤

初始化优先队列。
遍历价格数组[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个）
从优先队列中取出前5个元素：
- 6
- 5
- 7
- 4
- 8
打印输出结果：
```
4 5 6 7 8
```

结论

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

原文地址：https://blog.csdn.net/lbp0123456/article/details/142911929

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：Oracle-19g数据库的安装
下一篇：WebGl 使用uniform变量动态修改点的颜色

leetcode289:生命游戏
根据，简称为，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。给定一个包含m × n个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1即为（live），或0即为
阅读更多2024-10-20
MongoDB数据恢复
注意：两个MongoDB的版本要一致，本文使用的是mongo:4.2.24。先把K8S上面的MongoDB 容器停止（可以把副本改成0）。1、将容器挂载MongoDB的数据目录备份到本地。经常是数据文
阅读更多2024-10-20
C#中实现事务
C#中实现事务
阅读更多2024-10-20
【LeetCode每日一题】——560.和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。子数组是数组中元素的连续非空序列。
阅读更多2024-10-20
「漏洞复现」满客宝智慧食堂系统 selectUserByOrgId 未授权访问漏洞
请勿利用文章内的相关技术从事非法测试，由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失，均由使用者本人负责，作者不为此承担任何责任。工具来自网络，安全性自测，如有侵权请联系删除。本次
阅读更多2024-10-20
React面试题目（从基本到高级）
React前端面试常见题目涵盖了React的基础概念、组件、状态管理、生命周期、性能优化等多个方面。
阅读更多2024-10-20
12.个人博客系统（Java项目基于spring和vue）
1 在校学习的学生，可用于日常学习使用或是毕业设计使用 2 毕业一到两年的开发人员，用于锻炼自己的独立功能模块设计能力，增强代码编写能力。 3 亦可以部署为商化项目使用。 4 需要完整资料及源码
阅读更多2024-10-20
YoloV8改进策略：注意力改进|DeBiFormer，可变形双级路由注意力|引入DeBiLevelRoutingAttention注意力模块（全网首发）
本次改进的核心在于将DeBiLevelRoutingAttention模块嵌入到YoloV8的主干网络中，具体位置是在SPPF（Spatial Pyramid Pooling Fast）模块之后。这一
阅读更多2024-10-20
word取消自动单词首字母大写
情况说明：在word输入单词后首字母会自动变成大写取消单词首字母大写步骤：（1）点击菜单栏文件（2）点击“更多”——>“选项”（3）点击“校对”——>“自动更正选项”（4）取消“句首字母大
阅读更多2024-10-20
web前端网页用户注册页面
【代码】web前端网页用户注册页面。
阅读更多2024-10-20