华为OD机试真题 Java 实现【路灯照明问题】【2022Q4 100分】,感谢fly晨发现这个问题,并提供更优质的算法

这篇具有很好参考价值的文章主要介绍了华为OD机试真题 Java 实现【路灯照明问题】【2022Q4 100分】,感谢fly晨发现这个问题,并提供更优质的算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

华为OD机试真题 Java 实现【路灯照明问题】【2022Q4 100分】,感谢fly晨发现这个问题,并提供更优质的算法,华为OD机试(JAVA)真题(A卷+B卷),华为od,java,华为,程序人生,学习,原力计划

专栏导读

本专栏收录于《华为OD机试(JAVA)真题(A卷+B卷)》。
刷的越多,抽中的概率越大,每一题都有详细的答题思路、详细的代码注释、样例测试,订阅后,专栏内的文章都可看,可加入华为OD刷题群(私信即可),发现新题目,随时更新,全天CSDN在线答疑。

  • 专栏福利:限时订阅49.9,订阅后可加入华为OD刷题群,获得哪吒优先答疑机会(华为OD刷题指导,远程代码调试),群里大佬众多可以抱团取暖,群友刷题经验分享,考试经验分享。

一、题目描述

在一条笔直的公路上安装了N个路灯,从位置0开始安装,路灯之间间距固定为100米。

每个路灯都有自己的照明半径,请计算第一个路灯和最后一个路灯之间,无法照明的区间的长度和。

二、输入描述

第一行为一个数N,表示路灯个数,1<=N<=100000。

第二行为N个空格分隔的数,表示路径的照明半径,1<=照明半径<=100000*100。

三、输出描述

第一个路灯和最后一个路灯之间,无法照明的区间的长度和。

四、解题思路

题目要求计算第一个路灯和最后一个路灯之间无法照明的区间的长度和。

例如:

3
20 70 30
路灯1 覆盖0-20
路灯2 覆盖30-170
路灯3 覆盖170-230

没被覆盖的区间只有20~30。

所以输出10。

华为OD机试真题 Java 实现【路灯照明问题】【2022Q4 100分】,感谢fly晨发现这个问题,并提供更优质的算法,华为OD机试(JAVA)真题(A卷+B卷),华为od,java,华为,程序人生,学习,原力计划
但是,如果路灯的照明范围大于100,怎么办?

特别鸣谢:感谢fly晨发现这个问题,并提供更优质的算法。

华为OD机试真题 Java 实现【路灯照明问题】【2022Q4 100分】,感谢fly晨发现这个问题,并提供更优质的算法,华为OD机试(JAVA)真题(A卷+B卷),华为od,java,华为,程序人生,学习,原力计划

华为OD机试真题 Java 实现【路灯照明问题】【2022Q4 100分】,感谢fly晨发现这个问题,并提供更优质的算法,华为OD机试(JAVA)真题(A卷+B卷),华为od,java,华为,程序人生,学习,原力计划

解题思路如下:

  1. 获取输入的灯数量;
  2. 通过Java8 Steam加载n个路灯的照明半径;
  3. 定义allResList,存储每个灯的照明范围;
  4. 定义maxRight,计算第一个灯和最后一个灯的距离;
  5. 将每个灯的照明范围放入一个集合中(左起点,右终点);
  6. 将每个灯的照明范围按照左起点进行升序排序;
    • 先按左边最小距离排序;
    • 如果左边距离相等的情况下 按照右边距离最小的排序;
  7. 当前节点和下一个节点做比较;
    • 用当前节点的右边照明范围和下一个节点的左边照明范围比较;
    • 大于的情况下 需要将下一个节点的右边距离取两个节点的最大值;
    • 说明两个节点之间存在黑暗距离;
  8. 输出黑暗距离之和totalBlack;

五、Java算法源码

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int lightNum = sc.nextInt();
    // 获取输入的灯数量
    sc.nextLine();
    // n个路灯的照明半径
    List<Integer> allLightLength = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).boxed().collect(Collectors.toList());

    // 每个灯的照明范围
    List<List<Integer>> allResList = new ArrayList<>();

    // 计算第一个灯和最后一个灯的距离
    int maxRight = (lightNum - 1) * 100;

    // 将每个灯的照明范围放入一个集合中
    for (int i = 0; i < allLightLength.size(); i++) {
        // 当前灯的照明范围,左起点,右终点
        List<Integer> currentList = new ArrayList<>();
        // 左起点,注意左边范围不要小于总范围的最小长度
        Integer left = Math.max(0, i * 100 - allLightLength.get(i));
        // 右终点,注意右边范围不要大于总范围的最大长度
        Integer right = Math.min(maxRight, i * 100 + allLightLength.get(i));
        currentList.add(left);
        currentList.add(right);
        allResList.add(currentList);
    }

    // 将每个灯的照明范围按照左起点进行升序排序
    allResList = allResList.stream().sorted((list1, list2) -> {
        Integer oneLeft = list1.get(0);
        Integer twoLeft = list2.get(0);
        // 先按左边最小距离排序
        if (!oneLeft.equals(twoLeft)) {
            return oneLeft - twoLeft;
        }
        // 如果左边距离相等的情况下  按照右边距离最小的排序
        return list1.get(1) - list2.get(1);
    }).collect(Collectors.toList());

    int totalBlack = 0;
    // 当前节点和下一个节点做比较
    for (int i = 0; i < lightNum - 1; i++) {
        List<Integer> currentList = allResList.get(i);
        List<Integer> nextList = allResList.get(i + 1);

        // 用当前节点的右边照明范围和下一个节点的左边照明范围比较
        if (currentList.get(1) >= nextList.get(0)) {
            // 大于的情况下 需要将下一个节点的右边距离取两个节点的最大值
            nextList.set(1, Math.max(currentList.get(1), nextList.get(1)));
            continue;
        }
        // 说明两个节点之间存在黑暗距离
        int currentBlackLength = nextList.get(0) - currentList.get(1);
        totalBlack += currentBlackLength;
    }

    System.out.println(totalBlack);
}

六、效果展示

1、输入

4
20 70 175 10

2、输出

5

3、思路

华为OD机试真题 Java 实现【路灯照明问题】【2022Q4 100分】,感谢fly晨发现这个问题,并提供更优质的算法,华为OD机试(JAVA)真题(A卷+B卷),华为od,java,华为,程序人生,学习,原力计划

华为OD机试真题 Java 实现【路灯照明问题】【2022Q4 100分】,感谢fly晨发现这个问题,并提供更优质的算法,华为OD机试(JAVA)真题(A卷+B卷),华为od,java,华为,程序人生,学习,原力计划


🏆下一篇:华为OD机试真题 Java 实现【跳房子II】【2023 B卷 100分】,附详细解题思路

🏆本文收录于,华为OD机试(JAVA)(2022&2023)

刷的越多,抽中的概率越大,每一题都有详细的答题思路、详细的代码注释、样例测试,订阅后,专栏内的文章都可看,可加入华为OD刷题群(私信即可),发现新题目,随时更新,全天CSDN在线答疑。

华为OD机试真题 Java 实现【路灯照明问题】【2022Q4 100分】,感谢fly晨发现这个问题,并提供更优质的算法,华为OD机试(JAVA)真题(A卷+B卷),华为od,java,华为,程序人生,学习,原力计划文章来源地址https://www.toymoban.com/news/detail-598440.html

到了这里,关于华为OD机试真题 Java 实现【路灯照明问题】【2022Q4 100分】,感谢fly晨发现这个问题,并提供更优质的算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 华为OD机试真题 Java 实现【快递投放问题】【2023 B卷 100分】,附详细解题思路

    有N个快递站点用字符串标识,某些站点之间有道路连接。每个站点有一些包裹要运输,每个站点间的包裹不重复,路上有检查站会导致部分货物无法通行,计算哪些货物无法正常投递。 第一行输入M N,M个包裹N个道路信息。 0=M,N=100,检查站禁止通行的包裹如果有多个以空格

    2024年02月13日
    浏览(40)
  • 2023华为od机试真题B卷【矩阵稀疏扫描】Java 实现

             所有题目均有五种语言实现。 C实现目录 、 C++ 实现目录 、 Python实现目录 、 Java实现目录 、 JavaScript实现目录         如果矩阵中的许多系数都为零,那么该矩阵就是稀疏的。对稀疏现象有兴趣是因为它的开发可以带来巨大的计算节省,并且在许多大的实践

    2024年02月08日
    浏览(36)
  • 华为OD机试真题Java实现【5键键盘的输出】真题+解题思路+代码(2022&2023)

    题目 有一个特殊的5键键盘,上面有a,ctrl-c,ctrl-x,ctrl-v,ctrl-a五个键。a键在屏幕上输出一个字母a;ctrl-c将当前选择的字母复制到剪贴板;ctrl-x将当前选择的字母复制到剪贴板,并清空选择的字母;ctrl-v将当前剪贴板里的字母输出到屏幕;ctrl-a选择当前屏幕上的所有字母。

    2024年02月15日
    浏览(41)
  • 华为OD机试真题 Java 实现【字符统计】【2023 B卷 100分】

    华为OD机试 2023B卷题库疯狂收录中,刷题 点这里 输入一个只包含小写英文字母和数字的字符串,按照不同字符统计个数由多到少输出统计结果,如果统计的个数相同,则按照ASCII码由小到大排序输出。 数据范围:字符串长度满足 1≤len(str)≤1000 。 一个只包含小写英文字母和

    2024年02月07日
    浏览(47)
  • 华为OD机试真题 Java 实现【端口合并】【2022.11 Q4 新题】

        所有题目均有五种语言实现。 C语言实现目录 、 C++ 实现目录 、 Python实现目录 、 Java实现目录 、 JavaScript实现目录 有 M(1=M=10) 个端口组 每个端口组是长度为 N(1=N=100)的整数数组,如果端口组间存在2个及以上不同端口相同,则认为这2个端口组 互相关联,可以合并

    2023年04月08日
    浏览(44)
  • 华为OD机试真题 Java 实现【打印文件】【2023Q1 100分】

    有 5 台打印机打印文件,每台打印机有自己的待打印队列。 因为打印的文件内容有轻重缓急之分,所以队列中的文件有1~10不同的优先级,其中数字越大优先级越高。 打印机会从自己的待打印队列中选择优先级最高的文件来打印。 如果存在两个优先级一样的文件,则选择最早

    2024年02月07日
    浏览(40)
  • 华为OD机试真题B卷 Java 实现【字符统计】,附详细解题思路

    华为OD机试 2023B卷题库疯狂收录中,刷题 点这里 输入一个只包含小写英文字母和数字的字符串,按照不同字符统计个数由多到少输出统计结果,如果统计的个数相同,则按照ASCII码由小到大排序输出。 数据范围:字符串长度满足 1≤len(str)≤1000 。 一个只包含小写英文字母和

    2024年02月07日
    浏览(49)
  • 华为OD机试真题B卷 Java 实现【查字典】,附详细解题思路

    华为OD机试 2023B卷题库疯狂收录中,刷题 点这里 输入一个单词前缀和一个字典,输出包含该前缀的单词。 单词前缀+字典长度+字典。 字典是一个有序

    2024年02月07日
    浏览(43)
  • 华为OD机试真题B卷 Java 实现【寻找峰值】,附详细解题思路

    给定一个长度为n的数组nums,请你找到峰值并返回其索引。数组可能包含多个峰值,在这种情况下,返回任何一个所在位置即可。 1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于; 2.假设 nums[-1] = nums[n] = -infty−∞; 3.对于所有有效的 i 都有 nums[i] !=

    2024年02月06日
    浏览(64)
  • 华为OD机试真题 Java 实现【工单调度策略】【2023 Q1 | 100分】

        所有题目均有四种语言实现。 C++ 实现目录 、 Python实现目录 、 Java实现目录 、 JavaScript实现目录 题目描述:         当小区通信设备上报告警时,系统会自动生成待处理的工单,华为工单调度系统需要根据不同的策略,调度外线工程师(FME)上站去修复工单对应的

    2023年04月08日
    浏览(66)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包