力扣第860題-檸檬水找零1.本題分為如下三種情況1收5元不需要找零。5元數(shù)量1。2收10元需要找零5元。5元數(shù)量-110元數(shù)量1。3收20元需要找零15元。因為10元只能給20元找零所以要優(yōu)先使用10元數(shù)量和5元數(shù)量各-1若沒有10元再考慮只用5元找零5元數(shù)量-3。在過程中只要出現(xiàn)5元或10元的數(shù)量減到負數(shù)的情況則返回false。2.基于以上思想可寫出完整代碼如下1. bool lemonadeChange(int* bills, int billsSize) { 2. // five5元零錢數(shù)量ten10元零錢數(shù)量 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元【貪心優(yōu)先策略】優(yōu)先 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題-根據(jù)身高重建隊列1.本題剛拿到之后沒有任何思路看了題解之后才知道該怎么做。本題使用的核心思想是“矮個子相對于高個子是‘隱形’的”即矮個子插入到高個子前面比高個子高的數(shù)量不變。2.先將數(shù)組進行排序如果身高不一樣則按照身高進行降序排序如果一樣則按照k值進行升序排序。之后遍歷數(shù)組將遍歷到的元素按照它的k值插入到對應位置就會發(fā)現(xiàn)矮個子對高個子無影響數(shù)組排列成功。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. // 排序比較函數(shù)按身高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. // 分配結果二維數(shù)組每個人占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. // 分配每一行的列數(shù)數(shù)組 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. // 每個人的數(shù)組都是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. 規(guī)則一身高不同按身高降序高個子在前 7. if (p1[0] ! p2[0]) { 8. return p2[0] - p1[0]; 9. } 10. // 3. 規(guī)則二身高相同按 k 升序k 小的在前 11. else { 12. return p1[1] - p2[1]; 13. } 14. }1int* p1 *(int**)a這種寫法是因為傳進來的是數(shù)組元素的指針而本次使用的數(shù)組是二維數(shù)組people所以要用**a強制類型轉換后再進行取值就能取到二維數(shù)組中的單一元素了。2比較兩個元素的時候優(yōu)先比較身高身高高的就會被排前面若不成立再比較k值小的會被排前面。3因為qsort是使用的二維數(shù)組的一維數(shù)組元素來進行比較所以元素類型為int*第三個參數(shù)就要使用sizeof(int*)。