1. Algorithm
零钱兑换（中等）
描述：
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。
示例：
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
思路：
动态规划：dp[i] 表示总金额为 i 时至少需要的硬币个数，初始赋值 amount+1 表示不可能取到的值。注意总金额要不小于硬币面值，而且保证总金额可以被硬币凑出来。
class Sulution {
public int coinChange(int[] coins, int amount) {
if (coins == null || coins.length == 0) {
return -1;
}
int length = amount + 1;
int[] dp = new int[length];
Arrays.fill(dp, length);
dp[0] = 0;
for (int i = 0; i < dp.length; i++) {
for (int coin : coins) {
if (i >= coin) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] == length ? -1 : dp[amount];
}
}
分析：
- 时间复杂度：O(N * k)，k 为硬币个数
- 空间复杂度：O(N)
2. Review
Why you should totally switch to Kotlin 为什么你该完全切换到 Kotlin
介绍了 Kotlin 的特性，与 Java 互操作、类型推断、空安全、数据类等，Kotlin 是现代化的语言，其特性会令开发者喜欢。
3. Tip
遇到 crash 如何解决呢？分享一下我的经验。
首先查看 stack trace，找到报错的类型、信息、代码文件和行数，常见的异常有 NullPointerException、ClassCastException、IndexOutOfBoundException 等，根据信息就大概可以知道报错原因。如果之前没见过这种异常，把信息复制粘贴到谷歌搜索，排名靠前的搜索结果都来自 Stack Overflow，说不定前人也碰到了类似的错误，从问题回复中就能找到答案，这就要求英文阅读能力要过关。最后如果实在搜不到，那只能请教大佬了。
4. Share
分享两个网站，收录了 Windows 和 Mac 平台上的优质软件。
网友评论