返回信息流322. 零钱兑换
高效的版本是这样的，跑完时间是1560ms：
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [-1] * (amount + 1)
dp[0] = 0
for coin in coins:
for i in range(amount + 1):
if i - coin >= 0 and dp[i - coin] != -1:
dp[i] = dp[i - coin] + 1 if dp[i] == -1 else min(dp[i], dp[i - coin] + 1)
return dp[amount]
如果把循环先后替换城这样，时间大概是2100ms:
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [-1] * (amount + 1)
dp[0] = 0
for i in range(amount + 1):
for coin in coins:
if i - coin >= 0 and dp[i - coin] != -1:
dp[i] = dp[i - coin] + 1 if dp[i] == -1 else min(dp[i], dp[i - coin] + 1)
return dp[amount]
请问大佬，这是为什么呢？
这是一条镜像帖。来源：北邮人论坛 / python / #25266同步于 2020/8/31
该镜像源已超过 30 天没有更新，可能在源站已被删除。
Python机器人发帖
一题leetcode的效率问题
Libertas
2020/8/31镜像同步6 回复
订阅后，新回复会通过你的通知中心匿名送达。
6 条回复
1. 多跑几次取平均，Leetcode的计时没有你想象的那么准确；
2. Testcases也有可能不一样，我用的是你的第二种方式，同一份代码在一年前的时候用了16ms，现在用了76ms；
3. 常数在算法题里的重要程度是0，在工业领域的重要程度接近0，纠结这个等于浪费生命。
这个是稳定复现的，我在想是不是和cache有关
【 在 Zelda 的大作中提到: 】
: 1. 多跑几次取平均，Leetcode的计时没有你想象的那么准确；
: 2. Testcases也有可能不一样，我用的是你的第二种方式，同一份代码在一年前的时候用了16ms，现在用了76ms；
: 3. 常数在算法题里的重要程度是0，在工业领域的重要程度接近0，纠结这个等于浪费生命。
我也猜是这样，但是还是想弄清楚为啥
【 在 xxpxxxxp 的大作中提到: 】
: 稳定复现的话盲猜cache miss
: 不过确实在大多数领域并不重要
LeetCode时间不准的，有时候还会受到网络的影响。其实不用在乎这些，主要还是看时间复杂度是否能达到最优就可以了，都是n^2，面试官也关注这个，如果考上原题应该是100% ac的