力扣第860题-柠檬水找零1.本题分为如下三种情况1收5元不需要找零。5元数量1。2收10元需要找零5元。5元数量-110元数量1。3收20元需要找零15元。因为10元只能给20元找零所以要优先使用10元数量和5元数量各-1若没有10元再考虑只用5元找零5元数量-3。在过程中只要出现5元或10元的数量减到负数的情况则返回false。2.基于以上思想可写出完整代码如下1. bool lemonadeChange(int* bills, int billsSize) { 2. // five5元零钱数量ten10元零钱数量 3. int five 0; 4. int ten 0; 5. 6. for (int i 0; i billsSize; i){ 7. switch(bills[i]){ 8. case 5: 9. // 收到5元无需找零 10. five; 11. break; 12. 13. case 10: 14. // 收到10元必须找一张5元 15. if (five 1) return false; 16. five--; 17. ten; 18. break; 19. 20. case 20: 21. // 收到20元【贪心优先策略】优先 105其次三张5 22. if (five 0 ten 0){ 23. five--; 24. ten--; 25. } else if (five 3){ 26. five - 3; 27. } else { 28. // 无法凑出15元零钱 29. return false; 30. } 31. break; 32. } 33. } 34. 35. return true; 36. }该算法时间复杂度为O(n)空间复杂度为O(1)。力扣第406题-根据身高重建队列1.本题刚拿到之后没有任何思路看了题解之后才知道该怎么做。本题使用的核心思想是“矮个子相对于高个子是‘隐形’的”即矮个子插入到高个子前面比高个子高的数量不变。2.先将数组进行排序如果身高不一样则按照身高进行降序排序如果一样则按照k值进行升序排序。之后遍历数组将遍历到的元素按照它的k值插入到对应位置就会发现矮个子对高个子无影响数组排列成功。3.基于以上思想可写出完整代码如下1. /** 2. * Return an array of arrays of size *returnSize. 3. * The sizes of the arrays are returned as *returnColumnSizes array. 4. * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free(). 5. */ 6. // 排序比较函数按身高h降序h相等时按k升序 7. int cmp(const void* a, const void* b){ 8. int* p1 *(int**)a; 9. int* p2 *(int**)b; 10. 11. if (p1[0] ! p2[0]){ 12. return p2[0] - p1[0]; // h大的放前面 13. } else { 14. return p1[1] - p2[1]; // h相同k小的放前面 15. } 16. } 17. 18. int** reconstructQueue(int** people, int peopleSize, int* peopleColSize, int* returnSize, int** returnColumnSizes) { 19. // 排序身高降序同身高k升序 20. qsort(people, peopleSize, sizeof(int*), cmp); 21. 22. // 分配结果二维数组每个人占int[2] 23. int** res (int**)malloc(sizeof(int*) * peopleSize); 24. for (int i 0; i peopleSize; i){ 25. res[i] (int*)malloc(sizeof(int) * 2); 26. } 27. // 分配每一行的列数数组 28. *returnColumnSizes (int*)malloc(sizeof(int) * peopleSize); 29. 30. // 逐个插入把当前people[i]插入下标 idx people[i][1] 的位置 31. for (int i 0; i peopleSize; i){ 32. int idx people[i][1]; 33. // 将 [idx, i 1] 整体向后挪一位腾出idx位置 34. for (int j i; j idx; j--){ 35. res[j][0] res[j - 1][0]; 36. res[j][1] res[j - 1][1]; 37. } 38. // 在idx位置放入当前人的信息 39. res[idx][0] people[i][0]; 40. res[idx][1] people[i][1]; 41. } 42. 43. *returnSize peopleSize; 44. // 每个人的数组都是2列 45. for (int i 0; i peopleSize; i) { 46. (*returnColumnSizes)[i] 2; 47. } 48. return res; 49. }该算法时间复杂度为O(n2)空间复杂度为O(logn)。4.本题的cmp和qsort有一些特殊这里单独提一下。1. int cmp(const void* a, const void* b) { 2. // 1. 灵魂转换剥开泛型指针的伪装 3. int* p1 *(int**)a; 4. int* p2 *(int**)b; 5. 6. // 2. 规则一身高不同按身高降序高个子在前 7. if (p1[0] ! p2[0]) { 8. return p2[0] - p1[0]; 9. } 10. // 3. 规则二身高相同按 k 升序k 小的在前 11. else { 12. return p1[1] - p2[1]; 13. } 14. }1int* p1 *(int**)a这种写法是因为传进来的是数组元素的指针而本次使用的数组是二维数组people所以要用**a强制类型转换后再进行取值就能取到二维数组中的单一元素了。2比较两个元素的时候优先比较身高身高高的就会被排前面若不成立再比较k值小的会被排前面。3因为qsort是使用的二维数组的一维数组元素来进行比较所以元素类型为int*第三个参数就要使用sizeof(int*)。