發表文章

322. Coin Change (Medium) and Dynamic Programming

322. Coin Change Medium 4777 147 Add to List Share You are given coins of different denominations and a total amount of money  amount . Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return  -1 . Example 1: Input: coins = [1, 2, 5] , amount = 11 Output: 3 Explanation: 11 = 5 + 5 + 1 Example 2: Input: coins = [2] , amount = 3 Output: -1 Note : You may assume that you have an infinite number of each kind of coin. 答案使用O(nk)時間，其中n是金額，k是硬幣總類數量。 方法是，假設我們早已得知amount=9的最少硬幣數量是3個，那麼amount=10的硬幣數量要嘛就是amount=10-1=9的數量3加1，或者是amount=10-2=8的數量3加1，或者是amount=10-5的數量1加1，是3者的最少數值。 換一個角度： amount=10數值與9，8，5有關 amount=9數值與8，7，4有關 amount=8數值與7，6，3有關 amount=5數值與4，3，0有關 amount=2數值與1，0，-3有關 amount=1數值與0，-1，-4有關 amount=0數值與-1，-2，-5有關 amount=-1數值與-2，-3，-6有關 由於求最少值因此使用其相反的最大值math.inf表示無法湊合金額。其中比較特比的是，預設amount負數的數值使用math.inf去表示好像很合理，但是從負數到整數的計算會一直得到math.inf，因此演算過程中需要設定一個起點不為math...
張貼留言
閱讀完整內容

560. Subarray Sum Equals K (Medium) and Prefix Sum

Youtube 帳號 JAVAAID的一個關於PrefixSum的影片當中使用了這個例子： a = [6, 3, -2, 4, -1, 0, -5] A = list(itertoools.accumulate(a)) A = [6, 9, 7, 11, 10, 10, 5] 忽略首2個數字，那麼尾5個的subarray[-2, 4, -1, 0, -5]，對應的就是A[2]直到A[6]包括前後，問你總和是多少？假設A[i, j]表示subarray的總和，答案是A[2,6] = A[0,6] - A[0,1] = 5 - 9 = -4，查表相減2個數字就知道，不用針對5個數字每個計算，得到Formula: A[i,j] = A[0,j] - A[0,i-1] = A[j] - A[i-1]。由此可得，走完整個array一次之後，查詢任意大小的subarray總和，只需要將2個數字相減，不必理會subarray大小。 因此，如果邊走邊計算PrefixSum的話，從0開始數到目前的j，就可以知道目前的PrefixSum A[j]（舉例A[j] = 10，k=3），使用formula，k = A[j] - A[i-1]或者A[i-1] = A[j]-k，問題問的是這條等式出現的總次數，即是要知道過去有多少個PrefixSum的數值等於A[j]-k = 7，換句話說，要知道過去PrefixSum等於7的次數。 對於任何一個array，它的每一個Subarray都有起點i以及終點j，那麼紀錄一下有多少個起點i構造的subarrray的和是k就好了。舉例目前PrefixSum是100，k是7，那就是說如果在此之前，任何在目前終點j的subarray sum等於100-7=93的話，都是需要計算的。因此如果在此之前我們曾經紀錄過subarray sum的出現次數的話，那麼在此我們就可以知道這個需要計算的數字了。 代碼如下 answer = 0 prefixSum = 0 counts = {} for x in nums:     prefixSum += x     answer += counts.get(prefixSum-k, 0)     counts[prefixSum] = counts.get(prefi...
張貼留言
閱讀完整內容

4. Median of Two Sorted Array (Hard) TBC

 Consider 2 sorted arrays A 1,2,3 B 7,8,9 The median is the (3 + 7) / 2. The mid index is 3.5. This is the case when the A max < B min. When A max < B min, it indicates the 2 arrays has no overlapped range. A 1 3 5 7 9 B 2 2 3 4 5 The median of the sorted 1 2 2 3 3 4 5 5 7 9 is related to 3 and 4 and is 3.5. We can quickly find the median of 5 in A and median of 3 in B. A median means that there are equal amount of numbers on both sides. For 2 medians, 
張貼留言
閱讀完整內容