代码随想录算法训练营第二十八天 | leetcode：柠檬水找零,根据身高重建队列,用最少数量的箭引爆气球
0 / 2 / 创建于 11个月前 /
_zzh 的个人博客
860. 柠檬水找零
解题方法
这题没啥技巧，纯纯的把每种情况罗列出来，然后判断剩余的数量是否够找零即可。
唯一的注意点是：在收取20元时，需要优先扣除10元，才能尽可能的多找零，因为5元可以对10找零，也可以对20找零。
- 情况一：账单是5，直接收下。
- 情况二：账单是10，消耗一个5，增加一个10
- 情况三：账单是20，优先消耗一个10和一个5，如果不够，再消耗三个5
复杂度
时间复杂度
O(n)
空间复杂度
O(1)
code
class Solution {
/**
* @param Integer[] $bills
* @return Boolean
*/
function lemonadeChange($bills) {
if($bills[0] > 5) return false;
$five = 0;//五元
$ten = 0;//十元
for($i = 0; $i < count($bills); $i++){
//收五元的情况
if($bills[$i] == 5){
$five++;
}
//收十元的情况
if($bills[$i] == 10){
if($five == 0) return false;
$ten++;
$five--;
}
//收二十元的情况
if($bills[$i] == 20){
//优先扣除10元
if($ten > 0 && $five > 0){
$ten--;
$five--;
}elseif($five >= 3){
$five -= 3;
}else{
return false;
}
}
}
return true;
}
}406. 根据身高重建队列
注意的问题
- 数组array_splice解法中，注意题目给定的是二维数值，重新排序插入的是数组，所以在第四个参数要加上中括号[],否则最后变成插入n个元素的一维数组。
- 与分糖果题型一样，两个维度的问题，需要先处理一个维度，再处理另一个维度。
解题方法
- 先从身高h维度处理数组，用usort函数按身高从大到小，排序二维数组。
- 再从排前面人数k维度处理数组，当存在k时，把当前元素，放入新数组k的位置。因为已经按身高从大到小排序了，所以k之前的身高肯定比k高。
- 处理k维度时，可以使用数组array_splice解题，array_splice方法可以实现在i位置插入元素，大于i的元素全部往后移的操作。或者SplDoublyLinkedList链表解题，因为链表插入元素的表现就是在i位置插入元素，大于i的元素全部往后移。
复杂度
时间复杂度
O(nlog n + n^2)
空间复杂度
O(n)
code
1. 数组array_splice解法，效率较低。
class Solution {
/**
* @param Integer[][] $people
* @return Integer[][]
*/
function reconstructQueue($people) {
usort($people, "compare");
$newPeople = [];
foreach($people as $key => $val){
array_splice($newPeople,$val[1], 0, [$val]);
}
return $newPeople;
}
}
function compare($a, $b){
if ($a[0] == $b[0]) {
// 如果高度相同，则排前面人数
return $a[1] - $b[1]; //正序排序
}
return $b[0] - $a[0]; //倒序排序
}2. SplDoublyLinkedList链表解法，效率较高。
class Solution {
/**
* @param Integer[][] $people
* @return Integer[][]
*/
function reconstructQueue($people) {
usort($people, "compare");
$list = new SplDoublyLinkedList;
for($i = 0; $i < count($people); $i++){
$list->add($people[$i][1], $people[$i]);
}
$newPeople = [];
foreach ($list as $key => $val){
$newPeople[] = $val;
}
return $newPeople;
}
}
function compare($a, $b){
if ($a[0] == $b[0]) {
// 如果高度相同，则排前面人数
return $a[1] - $b[1]; //正序排序
}
return $b[0] - $a[0]; //倒序排序
}
452. 用最少数量的箭引爆气球
解题方法
- 此题把气球转换成与x轴平行的线段，射出的箭为与y轴平行的线段，相交则代表可以引爆气球。
- 按气球的左边界，从小到大排序后。判断重叠区间，如果存在重叠区间则可以一起引爆。那么如何判断元素时间是否存在重叠区间呢？从i=1开始遍历数组（因为需要两两对比（i-1,i）从0开始会越界），如果i的左边界大于i-1的右边界,则相互无重叠，反之这存在重叠区间。那么如何判断三个气球之前是否重叠区间？这是题目一大关键点！需要从前两个重叠区间的右边界做文章。如果当前循环到相互重叠(a,b)的下一位元素k,如果元素k的左边界小于等于上一个重叠区间的右边界，则表示当前k与（a,b）三个元素存在重叠区间！也就是说，如果循环中存在重叠区间，则需要更新当前i的右边界为重叠区间的有边界，在下次循环时就会变成（i-1）的有边界与当前i的左边界再次做判断，形成闭环。
复杂度
时间复杂度
O(nlog n)
空间复杂度
O(n) 有一个快排，最差情况(倒序)时，需要n次递归调用。因此确实需要O(n)的栈空间
code
class Solution {
/**
* @param Integer[][] $points
* @return Integer
*/
function findMinArrowShots($points) {
usort($points,"compare");
$result = 1;
for($i = 1; $i < count($points); $i++){
//如果当前i的左边界大于i-1的有边界，则不存在重叠，result++;
if($points[$i][0] > $points[$i-1][1]){
$result++;
}else{
//更新右边界为重叠值的右边界，当进入下一次循环时，与上面的$points[$i-1][1]联动了
//也方便判断与下一次循环的气球是否重叠
$points[$i][1] = min($points[$i][1],$points[$i-1][1]);
}
}
return $result;
}
}
function compare($a, $b){
return $a[0] - $b[0];
}本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号
大佬厉害呀，居然写了这么许多 :+1: