java试图理解Leetcode的时间复杂性
我试图理解时间复杂性/如何编写更高效的算法
有人能解释为什么第一个硬币兑换问题的解决方案比第二个更快吗?代码一开始比较干净,但是什么让它更快呢?它是否因为代码行数较少而变得更快? (如果这很明显,请原谅——我只是在学习时间复杂性,我的理解基本上只是:嵌套for循环是指数型的,正则循环是线性的,基本逻辑是常数时间…)
Here's a link如果你不熟悉这个问题,请回答
更好的解决方案-在18毫秒内运行
public int coinChange(int[] coins, int amount) {
if (amount < 1) return 0;
int[] dp = new int[amount + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int coin : coins) {
for (int i = coin; i <= amount; i++) {
if (dp[i - coin] != Integer.MAX_VALUE) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}
更差的解决方案-在26毫秒内运行
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount+1];
Arrays.fill(dp, Integer.MAX_VALUE-1);
dp[0] = 0;
if(amount == 0){
return 0;
}
for(int j=0; j<coins.length; j++){
for(int i=1; i<=amount; i++){
//only continue if coin is less than sum at i
if(i >= coins[j]){
//if there is a smaller sum +1 less than current sum
if(dp[i - coins[j]] +1 < dp[i]){
dp[i] = 1 + dp[i-coins[j]];
}
}
}
}
if(dp[amount] == Integer.MAX_VALUE-1){
return -1;
} else{
return dp[amount];
}
}
共 (0) 个答案