860.檸檬水找零

- LeetCode

思路： 這個問題比較簡單， 用一個字典bill_dict記錄已經收到的錢已經錢的數量， 然后如果收到五元， 字典中的 bill_dict[5] += 1。?收到10元?bill_dict[5] -= 1?bill_dict[10] += 1 。 麻煩的是收到20元， 這時候我們應該優先找 一個10元和一個5元， 沒有10元的時候， 找三個五元。 然后疊加判斷沒辦法找零的條件就可以了。

難點： 無

class Solution:def lemonadeChange(self, bills: List[int]) -> bool:collected_bills = defaultdict(int)for bill in bills:if bill == 5:collected_bills[5] += 1elif bill == 10: # give out 5 billscollected_bills[10] += 1collected_bills[5] -= 1if collected_bills[5] < 0:return Falseelse: # give out 15 billsif collected_bills[5] > 0 and collected_bills[10] > 0:collected_bills[20] += 1collected_bills[5] -= 1collected_bills[10] -= 1elif collected_bills[5] > 2:collected_bills[5] -= 3else:return Falsereturn True

406.根據身高重建隊列?

- LeetCode

思路： 這個問題有點難卡了，我好幾天。。。 一開始的思路是先對 k 排序， 然后對 h 排序， 那么k=0 的時候等于已經排好了，然后對 k=1 的時候， 往前找到一個比它的h大一個的數字insert進去就行了。 但是這樣代碼運行的很慢。 然后發現其實先對 h 倒序排列然后在對k順序排列要簡單很多， 因為當loop 一個 h 的時候可以保證前面的h都是大于這個元素的 h的。?

難點： 排序的方式比較難想到。?

class Solution:def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:people.sort(key=lambda x: [-x[0], x[1]])i, n = 0, len(people)while i < n:k = people[i][1]if k >= i:i += 1continueelse:tmp = people.pop(i)people.insert(k, tmp)i += 1return people

452. 用最少數量的箭引爆氣球?

思路： 這個題是求重疊的區間的問題的。 首先對數組排序，如果發現下一個point 的end 大于前一個point 的start， 就丟掉這兩個point 轉而insert 一個新的point， 這個新的point 表示兩者的重疊區間。 最后看看還剩幾個point 就可以了。

?難點： 第一次提交失敗了，因為重疊區間的定義出了邏輯bug， 重疊區間的 end 應該是兩個區間end的最小值。?

class Solution:def findMinArrowShots(self, points: List[List[int]]) -> int:points.sort()points = points[1:] + [points[0]]i, n = 0, len(points)while i < n-1:point = points.pop(0)if point[0] <= points[-1][1]:last_point = points.pop()points.append([max(point[0], last_point[0]), min(point[1], last_point[1])])else:points.append(point)i += 1return len(points)