Java 题解 | #大胃王牛牛#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param grass int整型一维数组
     * @param cost int整型一维数组
     * @return int整型
     */
    public int can_complete_circuit (int[] grass, int[] cost) {
        // write code here
        int sz = grass.length;
        int remain = 0;
        int res = -1;

        if (sz > 0 && sz == cost.length) {
            for (int i = 0; i < sz; i++) {
                remain += grass[i] - cost[i];
            }

            if (remain >= 0) {
                remain = 0;
                res = 0;

                for (int i = 0; i < sz; i++) {
                    remain += grass[i] - cost[i];

                    if (remain < 0) {
                        remain = 0;
                        res = i + 1;
                    }
                }
                res++;
            }
        }

        return res;
    }
}

编程语言是Java。

该题考察的知识点是贪心算法。

贪心算法通常用于解决最优化问题，每一步都选择当前最优解，以期望最终能够达到全局最优解。

代码的文字解释如下：

• 获取数组的长度，即牛棚数量，并将其赋值给变量 sz。
• 创建一个变量 remain，用于记录当前剩余的草料量，初始化为0。
• 创建一个变量 res，用于记录起始牛棚的索引，初始化为-1。
• 如果牛棚数量大于0且与 cost 数组长度相等，则执行以下操作：遍历牛棚：每次更新剩余草料量 remain，加上当前牛棚的草料量减去到下一个牛棚的消耗草料量。如果剩余草料量 remain 大于等于0：将剩余草料量 remain 重置为0。将起始牛棚索引 res 设置为0。再次遍历牛棚：每次更新剩余草料量 remain，加上当前牛棚的草料量减去到下一个牛棚的消耗草料量。如果剩余草料量 remain 小于0：将剩余草料量 remain 重置为0。将起始牛棚索引 res 设置为当前索引加1。将起始牛棚索引 res 增加1，因为循环遍历中最后一次剩余草料量小于0时，已经进行了一次加1的操作。
• 返回起始牛棚索引 res。