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

_zzh 的个人博客 / 33 / 2 / 创建于 1个月前 / 更新于 1个月前

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];
}