文章目录
- day35学习内容
- 一、柠檬水找零
- 1.1、思路
- 1.2、代码-正确写法
- 二、根据身高重建队列
- 2.1、思路
- 2.2、正确写法1
- 2.2.1、 如何理解上面这段代码
- 2.2.2、 如何理解 que.add(p[1], p)？
- 2.2.3、这段代码贪心在哪里呢？
- 三、最少的箭引爆气球
- 3.1、思路
- 3.2、正确写法1
- 总结
- 1.感想
- 2.思维导图
day35学习内容
day35主要内容
- 柠檬水找零
- 根据身高重建队列
- 最少的箭引爆气球
声明
本文思路和文字，引用自《代码随想录》
一、柠檬水找零
860.原题链接
1.1、思路
思路比较简单，
- 如果顾客支付了5美元（bills[i] == 5），则不需要找零，直接将5美元钞票的数量five增加1。
- 如果顾客支付了10美元（bills[i] == 10），需要找回一张5美元的钞票作为零钱。这时，将5美元钞票的数量five减少1，并将10美元钞票的数量ten增加1。
- 如果顾客支付了20美元（bills[i] == 20），有两种找零方式：
- 首先尝试使用一张10美元和一张5美元的组合找零（如果有的话），这样ten减少1，five也减少1；
- 如果没有10美元钞票，则需要使用三张5美元钞票找零，这时five减少3。
1.2、代码-正确写法
class Solution {
public boolean lemonadeChange(int[] bills) {
int five = 0;
int ten = 0;
int twenty = 0;
for (int i = 0; i < bills.length; i++) {
// 五元找零
if (bills[i] == 5) {
five++;
}
if (bills[i] == 10) {
five--;
ten++;
}
// 二十找零
if (bills[i] == 20) {
// 如果有10元钞票，优先使用10元的
if (ten > 0) {
ten--;
five--;
} else { // 如果没有10元的，需要三张才能找零
five -= 3;
}
}
if (five < 0 || ten < 0) {
return false;
}
}
return true;
}
}
二、根据身高重建队列
406.原题链接
2.1、思路
-
先处理身高高的人：
- 首先对数组进行排序，身高高的人（
h值大）排在前面，如果身高相同，则k值小的（即前面应有较少的人高于或等于他）排在前面。 - 这样的排序策略很好理解吧，
要满足题意要求，只能K更小的数排在前面咯。
- 首先对数组进行排序，身高高的人（
-
利用链表高效插入的特性：
- 使用
LinkedList来存储最终的队列，因为链表支持在任意位置插入元素，而这正是重建队列时所需要的。 - 遍历排序后的数组，对于每个人，根据其
k值（即p[1]），将其插入到链表的第k个位置。这里的k值实际上代表了在当前已排序且插入的人中，应有k个人的身高大于或等于当前人。
- 使用
2.2、正确写法1
class Solution {
public int[][] reconstructQueue(int[][] people) {
// 身高从大到小排（身高相同k小的站前面）
Arrays.sort(people, (a, b) -> {
if (a[0] == b[0])
return a[1] - b[1];
return b[0] - a[0];
});
LinkedList<int[]> que = new LinkedList<>();
for (int[] p : people) {
// Linkedlist.add(index, value)
que.add(p[1], p);
}
return que.toArray(new int[people.length][]);
}
}
2.2.1、 如何理解上面这段代码
-
排序：首先，对数组
people进行排序。排序的规则是按照身高h降序排列，如果身高相同，则按照k值升序排列。这样做的目的是先处理身高较大的人。因为他们在排列时，其前面的人数k直接对应他们在队列中的位置，不会被身高更低的人影响。 -
队列重建：创建一个
LinkedList（链表）que用于存放最终的队列。遍历排序后的people数组，对于每一个人p，根据其k值将其插入到que的第k个位置。由于链表支持在任意位置高效插入元素，这里使用LinkedList而不是普通的ArrayList。 -
插入操作：对于
que.add(p[1], p);这个操作，p[1]是当前人的k值，表示他前面应有k个人身高大于等于他。由于前面已经按照身高降序排列，此时插入的位置就是这个人在最终队列中的准确位置。 -
返回结果：最后，将链表
que转换为二维数组形式并返回。
2.2.2、 如何理解 que.add(p[1], p)？
p[1]其实就是k。
在Java中，LinkedList提供了一个非常有用的方法add(int index, E element)，它允许你在链表的指定位置index插入元素element。这个特性在很多情况下非常有用，尤其是当你需要保持列表中元素的某种顺序时。
在这段代码que.add(p[1], p);中，que是一个LinkedList，用于存放按一定规则排序后的人。p是一个包含两个元素的数组，其中p[0]表示人的身高，p[1]表示在重建的队列中，该人前面应有的、身高大于等于该人身高的人数。
这里p[1]作为add方法的第一个参数，指定了p应该被插入que的位置。这意味着在p被插入后，它前面恰好有p[1]个人。这正好符合题目的要求，即每个人前面有k个身高大于等于他的人。
举个例子，假设某个人p的身高为160cm，p[1]值为2，这意呀着在重建的队列中，这个人前面应有2个身高大于等于160cm的人。当执行que.add(2, p);时，就是将这个人插入到链表的第3个位置（因为索引是从0开始的），从而确保他前面有2个人。
2.2.3、这段代码贪心在哪里呢？
-
排序策略：首先，通过对
people数组进行特定的排序，将身高从高到低排列，当身高相同时，按照k值（即前面应有的身高不低于当前人的人数）从小到大排列。这种排序策略是贪心策略的核心，因为它先处理了身高较高的人。处理这些人时，我们可以简单地根据他们的k值将他们放置在结果队列中的正确位置，因为他们是目前最高的，所以不需要担心后来的人会对他们的位置产生影响。 -
插入策略：在将人插入队列时，每个人根据其
k值（即p[1]），被直接插入到最终队列的第k个位置（考虑到链表索引从0开始，实际上是第k+1个位置）。这里的贪心思想在于假设在当前人之前的所有人都已经被正确放置，那么根据当前人的k值直接确定其位置就是最优的。这个假设是基于排序步骤确保的，即在当前人之前只会有身高等于或大于他的人，这样就满足了他的k值的要求。 -
总结：它总是寻找局部最优解（即在当前步骤中，根据已排序的顺序和
k值将每个人放置在可能的最终位置），并且通过这种局部最优解的连续选择，达到了全局最优解（即重建的队列满足题目条件）。通过排序使得问题简化，然后逐个按照k值插入到队列中的策略，保证了每一步都是在当前情况下的最优选择。
三、最少的箭引爆气球
452.原题链接
3.1、思路
说实话，没太想明白这一题，，，
主要就是需要处理气球间的重叠情况：
- 如果当前气球的起始坐标大于前一个气球的结束坐标，说明这两个气球不重叠，需要另外一支箭，因此箭的数量count加1。
- 如果当前气球与前一个气球重叠（即当前气球的起始坐标不大于前一个气球的结束坐标），则更新当前气球的结束坐标为两个气球结束坐标中较小的一个。这是为了最小化重叠区域的右边界，确保下一支箭能射中尽可能多的重叠气球。
贪心体现在哪里？
关键在于通过排序简化了问题，将其转化为了一个区间重叠问题，然后通过贪心的策略，每次尽可能在重叠区域射箭，以最小化所需的箭数。
3.2、正确写法1
class Solution {
public int findMinArrowShots(int[][] points) {
// 根据气球直径的开始坐标从小到大排序
Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));
int count = 1; // points 不为空至少需要一支箭
for (int i = 1; i < points.length; i++) {
// 气球的起始坐标大于前一个气球的结束坐标，说明不重叠
if (points[i][0] > points[i - 1][1]) {
count++; // 需要一支箭
} else { // 气球i和气球i-1挨着
// 需要更新重叠气球最小右边界
points[i][1] = Math.min(points[i][1], points[i - 1][1]);
}
}
return count;
}
}
总结
1.感想
- 【根据身高重建队列】和最【少的箭引爆气球】都不太会写，一边看题解一边抄的题解。。。
2.思维导图
本文思路引用自代码随想录，感谢代码随想录作者。-
