leetcode 贪心

本次题解包括

  • 134 Gas Station
  • 135 Candy

134. Gas Station

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station’s index if you can travel around the circuit once, otherwise return -1.

题目地址:leetcode Gas Station

题意:已知每个加油站能加的汽油gas[i],还有第i个加油站到i+1个站点需要花费cost[i]的汽油。 假设初始油箱为空,且油箱容量无限,求从哪个站点开始,可以绕一圈。不存在返回-1

思路:首先想想朴素的算法,对于每个点,如果gas[i] – cost[i] >=0,那么以该点x为起点,向后判断。路途中若出现油箱为负,说明该起点不对。 起点x +1重复过程。。。

这样显然复杂度为o(n^2),如何做到更好呢?

上面的过程在起点错误的时候直接进行了+1,就是初始起点的下一个。 就是说,假如abcdefg 这么多个加油站,a为一开始的站点,遍历到d发现不行了。接着从b开始。

然而这没有必要。 因为在过程中,有:

  • gas[a] – cost[a] >=0 (这是枚举的条件)
  • gas[a] – cost[a] + gas[b] – cost[b] >=0
  • gas[a] – cost[a] + gas[b] – cost[b]  + gas[c] – cost[c] >=0
  • gas[a] – cost[a] + gas[b] – cost[b]  + gas[c] – cost[c]  + gas[d] – cost[d] < 0

在d之前的每一步都是不小于0的。然而他们的累加过不了d这个站点,也就是说,abc都不会是解。(比0大的数加上去都过不了了何况不加)

而d也不会是解,因为必然有gas[d] – cost[d] < 0

因此接下来从e开始最好。

C++

Python

 


 

 

135. Candy

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

  • Each child must have at least one candy.
  • Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

题目地址:leetcode Candy

题意:有N个孩子站成一排,每个孩子都有一个分数,求最少的糖果数目使得:

  • 每个孩子至少需要一颗糖
  • 如果一个孩子的分数大于旁边的孩子,那么他的糖果要比旁边的多一颗。

思路:贪心。

code1:

一开始觉得先排好序,先给低的孩子1颗糖果,分数高的只要比较两边即可。

需要注意的是122 这种数据只要4颗糖,糖果分发情况为第1个1颗,第2个2颗,第3个1颗。(因此WA一次)

 

code2:

O(nlogn)太慢,虽然可以过。但是可以优化到O(n)。

初始化所有孩子糖果为1颗,接下来从做到右扫描进行“修正”。

假设我们只考虑左边孩子的情况,如果当前孩子大于左边孩子,那么糖果要在左边孩子基础上+1.

这样扫描一遍以后,我们可以保证,对于任意的 i > 0 有 ans[i]>ans[i-1] ( if ratings[i] >rating[i-1])

接下来从右向左扫描,如果当前孩子大于右边的孩子,并且糖果数少于右边的,要在右边的孩子基础上+1

总结如下:第一次扫描保证了每个比左边高分的孩子比左边的糖果多,第二次则是右边。

Python

C++

 

 

 

 

 

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode 贪心
本文地址:https://www.hrwhisper.me/leetcode-greedy/

听说长得好看的已经打赏了

Leetcode , . permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *