力扣第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*)。