代码随想录算法训练营第二十八天 | leetcode:柠檬水找零,根据身高重建队列,用最少数量的箭引爆气球

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. 根据身高重建队列

注意的问题

  1. 数组array_splice解法中,注意题目给定的是二维数值,重新排序插入的是数组,所以在第四个参数要加上中括号[],否则最后变成插入n个元素的一维数组。
  2. 与分糖果题型一样,两个维度的问题,需要先处理一个维度,再处理另一个维度。

解题方法

  1. 先从身高h维度处理数组,用usort函数按身高从大到小,排序二维数组。
  2. 再从排前面人数k维度处理数组,当存在k时,把当前元素,放入新数组k的位置。因为已经按身高从大到小排序了,所以k之前的身高肯定比k高。
    代码随想录算法训练营第二十八天 | leetcode:柠檬水找零,根据身高重建队列,用最少数量的箭引爆气球
  3. 处理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. 用最少数量的箭引爆气球

解题方法

  1. 此题把气球转换成与x轴平行的线段,射出的箭为与y轴平行的线段,相交则代表可以引爆气球。
    代码随想录算法训练营第二十八天 | leetcode:柠檬水找零,根据身高重建队列,用最少数量的箭引爆气球
  2. 按气球的左边界,从小到大排序后。判断重叠区间,如果存在重叠区间则可以一起引爆。那么如何判断元素时间是否存在重叠区间呢?从i=1开始遍历数组(因为需要两两对比(i-1,i)从0开始会越界),如果i的左边界大于i-1的右边界,则相互无重叠,反之这存在重叠区间。那么如何判断三个气球之前是否重叠区间?这是题目一大关键点!需要从前两个重叠区间的右边界做文章。如果当前循环到相互重叠(a,b)的下一位元素k,如果元素k的左边界小于等于上一个重叠区间的右边界,则表示当前k与(a,b)三个元素存在重叠区间!也就是说,如果循环中存在重叠区间,则需要更新当前i的右边界为重叠区间的有边界,在下次循环时就会变成(i-1)的有边界与当前i的左边界再次做判断,形成闭环。
    代码随想录算法训练营第二十八天 | leetcode:柠檬水找零,根据身高重建队列,用最少数量的箭引爆气球

复杂度

时间复杂度

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 协议》,转载必须注明作者和本文链接
《L05 电商实战》
从零开发一个电商项目,功能包括电商后台、商品 & SKU 管理、购物车、订单管理、支付宝支付、微信支付、订单退款流程、优惠券等
《L03 构架 API 服务器》
你将学到如 RESTFul 设计风格、PostMan 的使用、OAuth 流程,JWT 概念及使用 和 API 开发相关的进阶知识。
讨论数量: 2

大佬厉害呀,居然写了这么许多 :+1:

2个月前 评论
_zzh (楼主) 2个月前

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!