专栏名称: labuladong
算法,编程,致力于把问题讲清楚!
今天看啥  ›  专栏  ›  labuladong

[原创]当老司机学会了贪心算法 🤔

labuladong  · 公众号  ·  · 2021-07-28 11:50
后台回复进群一起刷力扣点击卡片可搜索关键词👇读完本文,可以去力扣解决如下题目:134.加油站(Medium)今天讲一个贪心的老司机的故事,就是力扣第 134 题「加油站」:题目应该不难理解,就是每到达一个站点i,可以加gas[i]升油,但离开站点i需要消耗cost[i]升油,问你从哪个站点出发,可以兜一圈回来。要说暴力解法,肯定很容易想到,用一个 for 循环遍历所有站点,假设为起点,然后再套一层 for 循环,判断一下是否能够转一圈回到起点:int n = gas.length;for (int start = 0; start     for (int step = 0; step         int i = (start + step) % n;        tank += gas[i];        tank -= cost[i];        // 判断油箱中的油是否耗尽    }}很明显时间复杂度是 O



文章无法展示全部,请购买VIP后 使用网页访问内容 或者 使用第三方RSS订阅工具访问内容





今天看啥 - 让阅读更高品质
本文地址:http://www.jintiankansha.me/t/H8boQMUS95