day35 代码回想录 柠檬水找零&根据身高重建队列&用最少数量的箭引爆气球

大纲

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

860.柠檬水找零

题目：860.柠檬水找零
钱只有5、10、20的面值，一个柠檬水需要5个面值的钱。判断能否正确找零
思路是遍历bills顾客给的面值，用map记录5、10、20面值的数量，判断当前i处的面值能否使用之前的零钱找零。

bool isFindZero(vector& bills) {
    map moneyMap{ make_pair(5,0), make_pair(10,0), make_pair(20,0) };
    for (int i = 0; i < bills.size(); ++i) {
        if (bills[i] == 10) {
            if (moneyMap[5] <= 0) {
                return false;
            } else {
                moneyMap[5] -= 1;
            }
        }
        else if (bills[i] == 20) {
            if (moneyMap[10] > 0 && moneyMap[5] > 0) {
                moneyMap[10] -= 1;
                moneyMap[5] -= 1;
            }
            else if (moneyMap[5] >= 3) {
                moneyMap[5] -= 3;
            } else {
                return false;
            }
        }
        moneyMap[bills[i]] += 1;
    }
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

406.根据身高重建队列

题目：406.根据身高重建队列
这是一个拥有两个维度身高和体重的题目，需要固定一个维度，然后去考虑另一个维。本题使用的是固定身高，对身高重新排序，使用list来进行插入操作会比vector高效。

// 排序算法需要考虑到身高相同情况处理
// list插入操作函数需要注意使用方式

bool cmpPeople(vector& a, vector& b) {
    if (a[0] == b[0]) return a[1] < b[1];
    return a[0] > b[0];
}
vector> resortPeoplePropety(vector>& people) {
    sort(people.begin(), people.end(), cmpPeople);

    // 按照位置插入
    list> que;
    for (int i = 0; i < people.size(); ++i) {
        int index = people[i][1];
        auto it = que.begin();
        while (index-- > 0) {
            it++;
        }
        que.insert(it, people[i]);
    }
    return vector>(que.begin(), que.end());
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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

题目：452. 用最少数量的箭引爆气球
用最少的箭射爆气球，对区间进行按照开始部分进行排序，如果区间不重叠，那么就需要一只箭，如果重叠，那么就更新当前i的右边范围为区间最小范围

bool _arrowsCmp(vector& a, vector& b) {
    return a[0] < b[0];
}
int minBrustBallonArrows(vector>& points) {
    //
    if (points.size() == 0) return 0;
    sort(points.begin(), points.end(), _arrowsCmp);
    int arrows = 1; // 最少需要一只箭
    for (int i = 1;i < points.size(); ++i) {
        if (points[i - 1][1] < points[i][0]) {
            arrows++;
        }
        else {
            // 更新i当前的最小区间
            points[i][1] = min(points[i - 1][1], points[i][1]);
        }
    }
    return arrows;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19