代码随想录第三十天（一刷&&C语言）|柠檬水找零&&根据身高重建队列&&用最少数量的箭引爆气球

创作目的：为了方便自己后续复习重点，以及养成写博客的习惯。

一、柠檬水找零

思路：参考carl文档

? ? ? ? 首先明确情况，账单是5，直接收下。账单是10，消耗一个5，增加一个10账单是20，优先消耗一个10和一个5，如果不够，再消耗三个5。情况一与情况二，都是固定策略，而唯一不确定的其实在情况三。情况三有贪心策略，要优先消耗一个10和一个5，因为10美元只能给账单20找零，而5美元可以给账单10和账单20找零，美元5更通用。

ledcode题目：https://leetcode.cn/problems/lemonade-change/description/

AC代码：

bool lemonadeChange(int* bills, int billsSize){
    // 分别记录五元、十元的数量（二十元不用记录，因为不会用到20元找零）
    int fiveCount = 0; int tenCount = 0; 

    int i;
    for(i = 0; i < billsSize; ++i) {
        // 分情况讨论每位顾客的付款
        switch(bills[i]) {
            // 情况一：直接收款五元
            case 5:
                fiveCount++;
                break;
            // 情况二：收款十元
            case 10:
                // 若没有五元找零，返回false
                if(fiveCount == 0)
                    return false;
                // 收款十元并找零五元
                fiveCount--;
                tenCount++;
                break;
            // 情况三：收款二十元
            case 20:
                // 若可以，优先用十元和五元找零（因为十元只能找零20，所以需要尽量用掉。而5元能找零十元和二十元）
                if(fiveCount > 0 && tenCount > 0) {
                    fiveCount--;
                    tenCount--;
                } 
                // 若没有十元，但是有三张五元。用三张五元找零
                else if(fiveCount >= 3) 
                    fiveCount-=3;
                // 无法找开，返回false
                else
                    return false;
                break;
        }
    }
    // 全部可以找开，返回true
    return true;
}

二、根据身高重建队列

思路：参考carl文档

????????有两个维度h和k，先确定一个维度，然后再按照另一个维度重新排列。明确策略为身高按从大到小排（身高相同的话则k小的站前面），让高个子在前面。按身高排序后，优先按身高高的people的k来插入，后续插入节点也不会影响前面已插入的节点。

lecode题目：https://leetcode.cn/problems/queue-reconstruction-by-height/

AC代码：

int cmp(const void *p1, const void *p2) {
    int *pp1 = *(int**)p1;
    int *pp2 = *(int**)p2;
    // 若身高相同，则按照k从小到大排列
    // 若身高不同，按身高从大到小排列
    return pp1[0] == pp2[0] ? pp1[1] - pp2[1] : pp2[0] - pp1[0];
}

// 将start与end中间的元素都后移一位
// start为将要新插入元素的位置
void moveBack(int **people, int peopleSize, int start, int end) {
    int i;
    for(i = end; i > start; i--) {
        people[i] = people[i-1];
    }
}

int** reconstructQueue(int** people, int peopleSize, int* peopleColSize, int* returnSize, int** returnColumnSizes){
    int i;
    // 将people按身高从大到小排列（若身高相同，按k从小到大排列）
    qsort(people, peopleSize, sizeof(int*), cmp);

    for(i = 0; i < peopleSize; ++i) {
        // people[i]要插入的位置
        int position = people[i][1];
        int *temp = people[i];
        // 将position到i中间的元素后移一位
        // 注：因为已经排好序，position不会比i大。(举例：排序后people最后一位元素最小，其可能的k最大值为peopleSize-2，小于此时的i)
        moveBack(people, peopleSize, position, i);
        // 将temp放置到position处
        people[position] = temp;

    }
    

    // 设置返回二维数组的大小以及里面每个一维数组的长度
    *returnSize = peopleSize;
    *returnColumnSizes = (int*)malloc(sizeof(int) * peopleSize);
    for(i = 0; i < peopleSize; ++i) {
        (*returnColumnSizes)[i] = 2;
    }
    return people;
}

三、用最少数量的箭引爆气球

思路：参考carl文档

? ? ? ?考虑到会有气球重叠的情况。局部最优：当气球出现重叠，一起射，所用弓箭最少。全局最优：把所有气球射爆所用弓箭最少。在数组中做标记来模拟气球射爆的过程。为了让气球尽可能的重叠，需要对数组进行排序。若气球重叠了，重叠气球中右边边界的最小值之前的区间一定需要一个弓箭。

ledcode题目：https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/description/

AC代码：

int cmp(const void *a,const void *b)
{
    return ((*((int**)a))[0] > (*((int**)b))[0]);
} 

int findMinArrowShots(int** points, int pointsSize, int* pointsColSize){
    //将points数组作升序排序
    qsort(points, pointsSize, sizeof(points[0]),cmp);
    
    int arrowNum = 1;
    int i = 1;
    for(i = 1; i < pointsSize; i++) {
        //若前一个气球与当前气球不重叠，证明需要增加箭的数量
        if(points[i][0] > points[i-1][1])
            arrowNum++;
        else
            //若前一个气球与当前气球重叠，判断并更新最小的x_end
            points[i][1] = points[i][1] > points[i-1][1] ? points[i-1][1] : points[i][1];
    }
    return arrowNum;
}

全篇后记：

? ? ? ? const void*的技巧在使用的时候进行强制类型转换的方法可以借鉴一下，做题主要是要模拟过程发现规律再变无序为有序，最后使用代码实现。