Algorithm
本周选择的算法题是：Coin Change。
规则
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
Return 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.
You may assume that you have an infinite number of each kind of coin.
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
Example 3:
Input: coins = [1], amount = 0
Output: 0
Example 4:
Input: coins = [1], amount = 1
Output: 1
Example 5:
Input: coins = [1], amount = 2
Output: 2
Constraints:
1 <= coins.length <= 121 <= coins[i] <= 231 - 10 <= amount <= 104
Solution
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
if amount == 0: return 0
ans = [0] + [float('inf')] * amount
for coin in coins:
for i in range(coin, amount + 1):
ans[i] = min(ans[i], ans[i - coin] + 1)
return ans[-1] if ans[-1] != float('inf') else -1
Review
NanoID 在社区的热度上已经超过了 UUID，GitHub Stars 数量也更多，相比 UUID，NanoID 有如下优势:
- 更短
- 更安全
- 更快、更紧凑
- 支持字母自定义
- 没有三方依赖
Tip
本周花了较多的时间学习如何利用 OKR 对齐团队、个人的目标，应用的好确实是一大利器。