杨乐乐
Never too late

Follow

Never too late

Follow

Day 34 贪心算法 - 柠檬水找零

杨乐乐's photo
杨乐乐
·Feb 17, 2023·

1 min read

Table of contents

  • 860. 柠檬水找零
  • 406. 根据身高重建队列
  • 452. 用最少数量的箭引爆气球

860. 柠檬水找零

function lemonadeChange(bills: number[]): boolean {
    let five = 0;
    let ten = 0;

    for (let i = 0; i < bills.length; i++) {
        if (bills[i] === 5) {
            five++;
        } else if (bills[i] === 10) {
            five--;
            ten++;
        } else if (ten > 0) {
            ten--;
            five--;
        } else {
            five -= 3;
        }

        if (five < 0) {
            return false;
        }
    }

    return true;
};

406. 根据身高重建队列

function reconstructQueue(people: number[][]): number[][] {
    let queue = [];

    people.sort((a, b ) => {
        if(b[0] !== a[0]) {
            return b[0] - a[0]
        } else {
            return a[1] - b[1]
        }
    })

    for(let i = 0; i < people.length; i++) {
        queue.splice(people[i][1], 0, people[i])
    }

    return queue;
};

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

function findMinArrowShots(points: number[][]): number {
    points.sort((a, b) => {
        return a[0] - b[0];
    })

    let result = 1;
    for(let i = 1; i < points.length; i++) {
        if(points[i][0] > points[i - 1][1]) {
            result++;
        } else {
            points[i][1] = Math.min(points[i - 1][1], points[i][1]);
        }
    } 

    return result;
};
 
Share this