代码随想录

朱雀 2024-02-22 02:26 115阅读 0赞

## 前言 ##

代码随想录算法训练营day35

--------------------

## 一、Leetcode 860.柠檬水找零 ##

### 1.题目 ###

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。

给你一个整数数组 bills ，其中 bills\[i\] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

示例 1：

输入：bills = \[5,5,5,10,20\] 输出：true 解释： 前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。 第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。 第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。 由于所有客户都得到了正确的找零，所以我们输出 true。

示例 2：

输入：bills = \[5,5,10,10,20\] 输出：false 解释： 前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。 对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。 对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。 由于不是每位顾客都得到了正确的找零，所以答案是 false。

提示：

css

复制代码

`1 <= bills.length <= 105 bills[i] 不是 5 就是 10 或是 20`

来源：力扣（LeetCode） 链接：[leetcode.cn/problems/le…][leetcode.cn_problems_le]

### 2.解题思路 ###

方法一：贪心

由于顾客只可能给你三个面值的钞票，而且我们一开始没有任何钞票，因此我们拥有的钞票面值只可能是 55 美元，1010 美元和 2020 美元三种。基于此，我们可以进行如下的分类讨论。

yaml

复制代码

`55 美元，由于柠檬水的价格也为 55 美元，因此我们直接收下即可。 1010 美元，我们需要找回 55 美元，如果没有 55 美元面值的钞票，则无法正确找零。 2020 美元，我们需要找回 1515 美元，此时有两种组合方式，一种是一张 1010 美元和 55 美元的钞票，一种是 33 张 55 美元的钞票，如果两种组合方式都没有，则无法正确找零。当可以正确找零时，两种找零的方式中我们更倾向于第一种，即如果存在 55 美元和 1010 美元，我们就按第一种方式找零，否则按第二种方式找零，因为需要使用 55 美元的找零场景会比需要使用 1010 美元的找零场景多，我们需要尽可能保留 55 美元的钞票。`

基于此，我们维护两个变量 fivefive 和 tenten 表示当前手中拥有的 55 美元和 1010 美元钞票的张数，从前往后遍历数组分类讨论即可。

### 3.代码实现 ###

java

复制代码

`class Solution { public boolean lemonadeChange(int[] bills) { int five = 0, ten = 0; for (int bill : bills) { if (bill == 5) { five++; } else if (bill == 10) { if (five == 0) { return false; } five--; ten++; } else { if (five > 0 && ten > 0) { five--; ten--; } else if (five >= 3) { five -= 3; } else { return false; } } } return true; } }`

## 二、Leetcode 406.根据身高重建队列 ##

### 1.题目 ###

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people\[i\] = \[hi, ki\] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue\[j\] = \[hj, kj\] 是队列中第 j 个人的属性（queue\[0\] 是排在队列前面的人）。

示例 1：

输入：people = \[\[7,0\],\[4,4\],\[7,1\],\[5,0\],\[6,1\],\[5,2\]\] 输出：\[\[5,0\],\[7,0\],\[5,2\],\[6,1\],\[4,4\],\[7,1\]\] 解释： 编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。 编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。 编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。 编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。 编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。 编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。 因此 \[\[5,0\],\[7,0\],\[5,2\],\[6,1\],\[4,4\],\[7,1\]\] 是重新构造后的队列。

示例 2：

输入：people = \[\[6,0\],\[5,0\],\[4,0\],\[3,2\],\[2,2\],\[1,4\]\] 输出：\[\[4,0\],\[5,0\],\[2,2\],\[3,2\],\[1,4\],\[6,0\]\]

提示：

matlab

复制代码

`1 <= people.length <= 2000 0 <= hi <= 106 0 <= ki < people.length 题目数据确保队列可以被重建`

来源：力扣（LeetCode） 链接：[leetcode.cn/problems/qu…][leetcode.cn_problems_qu]

### 2.解题思路 ###

方法一：从低到高考虑

思路与算法

当每个人的身高都不相同时，如果我们将他们按照身高从小到大进行排序，那么就可以很方便地还原出原始的队列了。

为了叙述方便，我们设人数为 nn，在进行排序后，它们的身高依次为 h0,h1,⋯ ,hn−1h0,h1,⋯,hn−1，且排在第 ii 个人前面身高大于 hihi 的人数为 kiki。如果我们按照排完序后的顺序，依次将每个人放入队列中，那么当我们放入第 ii 个人时：

css

复制代码

`第 0,⋯ ,i−10,⋯,i−1 个人已经在队列中被安排了位置，并且他们无论站在哪里，对第 ii 个人都没有任何影响，因为他们都比第 ii 个人矮； 而第 i+1,⋯ ,n−1i+1,⋯,n−1 个人还没有被放入队列中，但他们只要站在第 ii 个人的前面，就会对第 ii 个人产生影响，因为他们都比第 ii 个人高。`

如果我们在初始时建立一个包含 nn 个位置的空队列，而我们每次将一个人放入队列中时，会将一个「空」位置变成「满」位置，那么当我们放入第 ii 个人时，我们需要给他安排一个「空」位置，并且这个「空」位置前面恰好还有 kiki 个「空」位置，用来安排给后面身高更高的人。也就是说，第 ii 个人的位置，就是队列中从左往右数第 ki+1ki+1 个「空」位置。

那么如果有身高相同的人，上述 kiki 定义中的大于就与题目描述中要求的大于等于不等价了，此时应该怎么修改上面的方法呢？我们可以这样想，如果第 ii 个人和第 jj 个人的身高相同，即 hi=hjhi=hj，那么我们可以把在队列中处于较后位置的那个人的身高减小一点点。换句话说，对于某一个身高值 hh，我们将队列中第一个身高为 hh 的人保持不变，第二个身高为 hh 的人的身高减少 δδ，第三个身高为 hh 的人的身高减少 2δ2δ，以此类推，其中 δδ 是一个很小的常数，它使得任何身高为 hh 的人不会与其它（身高不为 hh 的）人造成影响。

如何找到第一个、第二个、第三个身高为 hh 的人呢？我们可以借助 kk 值，可以发现：当 hi=hjhi=hj 时，如果 ki>kjki>kj，那么说明 ii 一定相对于 jj 在队列中处于较后的位置（因为在第 jj 个人之前比他高的所有人，一定都比第 ii 个人要高），按照修改之后的结果，hihi 略小于 hjhj，第 ii 个人在排序后应该先于第 jj 个人被放入队列。因此，我们不必真的去对身高进行修改，而只需要按照 hihi 为第一关键字升序，kiki 为第二关键字降序进行排序即可。此时，具有相同身高的人会按照它们在队列中的位置逆序进行排列，也就间接实现了上面将身高减少 δδ 这一操作的效果。

这样一来，我们只需要使用一开始提到的方法，将第 ii 个人放入队列中的第 ki+1ki+1 个空位置，即可得到原始的队列。

### 3.代码实现 ###

java

复制代码

`class Solution { public int[][] reconstructQueue(int[][] people) { Arrays.sort(people, new Comparator<int[]>() { public int compare(int[] person1, int[] person2) { if (person1[0] != person2[0]) { return person1[0] - person2[0]; } else { return person2[1] - person1[1]; } } }); int n = people.length; int[][] ans = new int[n][]; for (int[] person : people) { int spaces = person[1] + 1; for (int i = 0; i < n; ++i) { if (ans[i] == null) { --spaces; if (spaces == 0) { ans[i] = person; break; } } } } return ans; } }`

## 三、452. 用最少数量的箭引爆气球 ##

### 1.题目 ###

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points\[i\] = \[xstart, xend\] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。

示例 1：

输入：points = \[\[10,16\],\[2,8\],\[1,6\],\[7,12\]\] 输出：2 解释：气球可以用2支箭来爆破: -在x = 6处射出箭，击破气球\[2,8\]和\[1,6\]。 -在x = 11处发射箭，击破气球\[10,16\]和\[7,12\]。

示例 2：

输入：points = \[\[1,2\],\[3,4\],\[5,6\],\[7,8\]\] 输出：4 解释：每个气球需要射出一支箭，总共需要4支箭。

示例 3：

输入：points = \[\[1,2\],\[2,3\],\[3,4\],\[4,5\]\] 输出：2 解释：气球可以用2支箭来爆破:

*  在x = 2处发射箭，击破气球\[1,2\]和\[2,3\]。
 *  在x = 4处射出箭，击破气球\[3,4\]和\[4,5\]。

提示:

ini

复制代码

`1 <= points.length <= 105 points[i].length == 2 -231 <= xstart < xend <= 231 - 1`

### 2.解题思路 ###

方法一：排序 + 贪心

思路与算法

我们首先随机地射出一支箭，再看一看是否能够调整这支箭地射出位置，使得我们可以引爆更多数目的气球。

fig1

如图 1-1 所示，我们随机射出一支箭，引爆了除红色气球以外的所有气球。我们称所有引爆的气球为「原本引爆的气球」，其余的气球为「原本完好的气球」。可以发现，如果我们将这支箭的射出位置稍微往右移动一点，那么我们就有机会引爆红色气球，如图 1-2 所示。

那么我们最远可以将这支箭往右移动多远呢？我们唯一的要求就是：原本引爆的气球只要仍然被引爆就行了。这样一来，我们找出原本引爆的气球中右边界位置最靠左的那一个，将这支箭的射出位置移动到这个右边界位置，这也是最远可以往右移动到的位置：如图 1-3 所示，只要我们再往右移动一点点，这个气球就无法被引爆了。

复制代码

`为什么「原本引爆的气球仍然被引爆」是唯一的要求？别急，往下看就能看到其精妙所在。`

因此，我们可以断定：

复制代码

`一定存在一种最优（射出的箭数最小）的方法，使得每一支箭的射出位置都恰好对应着某一个气球的右边界。`

这是为什么？我们考虑任意一种最优的方法，对于其中的任意一支箭，我们都通过上面描述的方法，将这支箭的位置移动到它对应的「原本引爆的气球中最靠左的右边界位置」，那么这些原本引爆的气球仍然被引爆。这样一来，所有的气球仍然都会被引爆，并且每一支箭的射出位置都恰好位于某一个气球的右边界了。

有了这样一个有用的断定，我们就可以快速得到一种最优的方法了。考虑所有气球中右边界位置最靠左的那一个，那么一定有一支箭的射出位置就是它的右边界（否则就没有箭可以将其引爆了）。当我们确定了一支箭之后，我们就可以将这支箭引爆的所有气球移除，并从剩下未被引爆的气球中，再选择右边界位置最靠左的那一个，确定下一支箭，直到所有的气球都被引爆。

我们可以写出如下的伪代码：

let points := \[\[x(0), y(0)\], \[x(1), y(1)\], ... \[x(n-1), y(n-1)\]\]，表示 n 个气球 let burst := \[false\] \* n，表示每个气球是否被引爆 let ans := 1，表示射出的箭数

将 points 按照 y 值（右边界）进行升序排序

while burst 中还有 false 值 do let i := 最小的满足 burst\[i\] = false 的索引 i for j := i to n-1 do if x(j) <= y(i) then burst\[j\] := true end if end for end while

return ans

这样的做法在最坏情况下时间复杂度是 O(n2)O(n2)，即这 nn 个气球对应的区间互不重叠，whilewhile 循环需要执行 nn 次。那么我们如何继续进行优化呢？

事实上，在内层的 jj 循环中，当我们遇到第一个不满足 x(j)≤y(i)x(j)≤y(i) 的 jj 值，就可以直接跳出循环，并且这个 y(j)y(j) 就是下一支箭的射出位置。为什么这样做是对的呢？我们考虑某一支箭的索引 itit 以及它的下一支箭的索引 jtjt，对于索引在 jtjt 之后的任意一个可以被 itit 引爆的气球，记索引为 j0j0，有：

x(j0)≤y(it)x(j0)≤y(it)

由于 y(it)≤y(jt)y(it)≤y(jt) 显然成立，那么

x(j0)≤y(jt)x(j0)≤y(jt)

也成立，也就是说：当前这支箭在索引 jtjt（第一个无法引爆的气球）之后所有可以引爆的气球，下一支箭也都可以引爆。因此我们就证明了其正确性，也就可以写出如下的伪代码：

let points := \[\[x(0), y(0)\], \[x(1), y(1)\], ... \[x(n-1), y(n-1)\]\]，表示 n 个气球 let pos := y(0)，表示当前箭的射出位置 let ans := 1，表示射出的箭数

将 points 按照 y 值（右边界）进行升序排序

for i := 1 to n-1 do if x(i) > pos then ans := ans + 1 pos := y(i) end if end for

return ans

这样就可以将计算答案的时间从 O(n2)O(n2) 降低至 O(n)O(n)。

### 3.代码实现 ###

java

复制代码

`class Solution { public int findMinArrowShots(int[][] points) { if (points.length == 0) { return 0; } Arrays.sort(points, new Comparator<int[]>() { public int compare(int[] point1, int[] point2) { if (point1[1] > point2[1]) { return 1; } else if (point1[1] < point2[1]) { return -1; } else { return 0; } } }); int pos = points[0][1]; int ans = 1; for (int[] balloon: points) { if (balloon[0] > pos) { pos = balloon[1]; ++ans; } } return ans; } }`

作者：东离与糖宝  
链接：https://juejin.cn/post/7244810003591577658  
来源：稀土掘金  
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

[leetcode.cn_problems_le]: https://link.juejin.cn?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Flemonade-change
[leetcode.cn_problems_qu]: https://link.juejin.cn?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fqueue-reconstruction-by-height