算法:加油站

2023-12-28 12:09:44

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档

目录

一、问题描述

二、原始解法

总结


提示:以下是本篇文章正文内容,下面案例可供参考

一、问题描述

在一条环路上有N个加油站,其中第i个加油站有汽油?a[i]?

你有一辆油箱容量无限的的汽车,从第?i?个加油站开往第?i+1?个加油站需要消耗汽油?b[i]?升。你从其中的一个加油站出发,开始时油箱为空。

如果你可以绕环路行驶一周,则返回出发时加油站的编号,否则返回 -1

输入:?
a? = [1,2,3,4,5]
b = [3,4,5,1,2]
输出: 3

输入:?
a ?= [2,3,4]
b = [3,4,3]
输出: -1

二、原始解法

解题思路:

首先,汽车是加了油,然后才能跑下一段路程,到下一个目的地,如果油量不足,就从下一个目的地始发,循环往复,直到最后一个目的地,如果最后一个目的地符合,则需要从第一个节点再重新出发,到达倒数第二个节点,这样就完成了整个环行路的遍历。

代码示例:

public void test() {
        // 记录油量
        int[] a = new int[]{2, 4, 5};
        // 记录每一段举例的路程
        int[] b = new int[]{3, 5, 6};
        // 记录从第几个节点出发
        int index = 0;
        // 记录剩余油量
        int left = 0;
        boolean result = true;
        while (index < a.length) {
            for (int i = index; i < a.length; i++) {
                if (left + a[i] < b[i]) {
                    // 当前节点出发不能满足, 则记录节点的索引index向前推进, index直接跳到下一个节点, 即为i+1
                    index = i + 1;
                    // 重置剩余油量
                    left = 0;
                    // 设置当前结果
                    result = false;
                    continue;
                }
                // 计算剩余油量
                left = left + a[i] - b[i];
                // 设置当前结果
                result = true;
            }
            // 从0开始, 整个循环如果结束, 且结果为通过, 则跳出while循环
            if (result) {
                break;
            }
        }
        // 如果index位于0到a.length-1之间, 说明前边是成功的, 需要将0到index之间的再走一遍, 这一遍比较特殊, 只需要从前到后判断一次即可
        if (index > 0 && index < a.length && left >= 0) {
            for (int i = 0; i < index; i++) {
                if (left + a[i] < b[i]) {
                    // 不通过, 设置最后的结果
                    result = false;
                    // 跳出循环
                    break;
                }
                // 计算剩余油量
                left = left + a[i] - b[i];
                // 设置当前结果
                result = true;
            }
        }
        // 输出结果
        System.out.println(result);
        // 输出第一个符合的出发点
        System.out.println(index < a.length ? index : -1);
    }

这种算法理解起来比较简单,主要要记录一下本次出发的起点,结果以及剩余油量

当遇到类似的问题时,可以先用最小的例子来攻破,比如我们就用两个数组,每个数组里只有2个元素,推导一下整个过程,然后转化成代码,然后再验证,随后再增加到3个元素,进行验证,查漏补缺,基本上就没问题了。


总结

复杂的搞不懂,先上简单的算法,简单到有手就行!

文章来源:https://blog.csdn.net/ql_gome/article/details/135265023
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。