Practice-Notes/Chapter 8. Greedy Alg Part 3 at main · Itaru-Shin/Practice-Notes · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
134. Gas station
首先要判断的一点就是，cost的总和需小于等于gas的总和，不然无论如何也跑不完一圈

贪心的算法非常巧妙。视频里面有一些细节可以看看，确实挺好的

贪心算法的题目还是比较好刷的

135. Candy
题目的理解也是需要努力的，因为只有两个条件，所以会出现同工不同酬的情况
因为要看两个方向的，所以这里的思想就是两个方向分别来看

首先确定右和左的关系，然后从前向后遍历
然后确定左和右的关系，然后从后向前遍历

两次遍历的顺序不一样，就是为了利用好上次的结果，保证两次计算都被考虑进去了

860. Lemonade Change

贪心体现在找20块钱的零的时候，要先从10块钱找起，没有10块钱的话再找5块钱的，因为5块钱更加万能

406. Queue Reconstruction by height

这里面是h和k两个维度，分发糖果是左和右两个维度

题解的思路真的是绝了。先按照h的大小进行排序，在身高相同的情况下，按照k从小到大的顺序进行排序

然后根据k的值进行调整（这里最关键了，因为矮的人插队不会产生任何影响，这一点之前是没有看透的）

        people.sort(key=lambda x: (-x[0], x[1]))
        que = []

python的这个排序我能学一年。这里充分地利用了元祖默认排序的顺序，先根据第一个元素从小到大排序，然后在相同的情况下，根据第二个元素从小到大排序

        for p in people:
            que.insert(p[1], p)
        return que

这一句能学更久。insert的机制是，当前位置及其之后的元素统统后移一个，然后插入这个元素。

酣畅淋漓地先按照h排序，然后按照k排序