题解 | #大胃王牛牛#

大胃王牛牛

https://www.nowcoder.com/practice/4e55777e218b4850928d054a8cddaf50

考察的知识点:贪心;

解答方法分析:

  1. 使用一个变量eat来记录当前的累积值,和一个变量start来记录可能的起始位置。然后使用一个循环,从列表的第一个元素遍历。
  2. 在每一次遍历中,我们将当前位置的产出值加到eat中,并减去当前位置的消耗值。然后判断eat的值是否小于0,如果是,则表示当前位置不可能是起始位置,需要将start移动到下一个位置,并将eat重置为0。如果eat大于等于0,表示从当前位置出发可以保持非负累积值。继续遍历下一个位置。
  3. 如果在遍历过程中发现回到了起始位置,并且标记flag为true,表示已经绕了一圈,并且始终维持了非负累积值,那么当前起始位置即为所求的位置。
  4. 如果遍历结束仍未找到合适的起始位置,则返回-1,表示无法找到满足条件的位置。

所用编程语言:C++;

完整编程代码:↓

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param grass int整型vector
     * @param cost int整型vector
     * @return int整型
     */
    int can_complete_circuit(vector<int>& grass, vector<int>& cost) {
        int len = grass.size();
        int i = 0, start = 0;
        int eat = 0;
        bool flag = false;
        while (true) {
            eat = eat + grass[i] - cost[i];
            if (eat < 0) {
                if (flag)
                    return -1;
                eat = 0;
                start = i + 1;
            }
            if (start == i && flag)
                return start + 1;
            i++;
            if (i >= len) {
                i = i % len;
                flag = true;
            }
        }
    }
};

全部评论

相关推荐

06-17 00:26
门头沟学院 Java
程序员小白条:建议换下项目,智能 AI 旅游推荐平台:https://github.com/luoye6/vue3_tourism_frontend 智能 AI 校园二手交易平台:https://github.com/luoye6/vue3_trade_frontend GPT 智能图书馆:https://github.com/luoye6/Vue_BookManageSystem 选项目要选自己能掌握的,然后最好能自己拓展的,分布式这种尽量别去写,不然你只能背八股文了,另外实习的话要多投,尤其是学历不利的情况下,多找几段实习,最好公司title大一点的
无实习如何秋招上岸
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务