亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

為了賬號安全,請及時綁定郵箱和手機立即綁定
已解決430363個問題,去搜搜看,總會有你想問的

LeetCode 的硬幣兌換問題超過了時間限制

LeetCode 的硬幣兌換問題超過了時間限制

肥皂起泡泡 2021-07-19 20:23:57
我正在嘗試解決LeetCode 上的Coin Change 問題:我想出了我認為與解決方案中提到的自下而上的動態編程方法相同的方法:import mathclass Solution:    def coinChange(self, coins, amount):        fewest = [0] * (amount + 1)        for i in range(1, amount + 1):            fewest[i] = 1 + min(                (fewest[i - coin] for coin in                    [c for c in coins if i - c >= 0]),                default=math.inf)        return fewest[amount] if fewest[amount] < math.inf else -1以下是pytest我用來驗證解決方案的一些測試用例:def test_1():    assert Solution().coinChange([1, 2, 5], 1) == 1def test_2():    assert Solution().coinChange([1, 2, 5], 2) == 1def test_3():    assert Solution().coinChange([1, 2, 5], 3) == 2def test_4():    assert Solution().coinChange([1, 2, 5], 4) == 2def test_5():    assert Solution().coinChange([1, 2, 5], 5) == 1def test_67():    assert Solution().coinChange([1, 2, 5], 6) == 2    assert Solution().coinChange([1, 2, 5], 7) == 2def test_8():    assert Solution().coinChange([1, 2, 5], 8) == 3def test_11():    assert Solution().coinChange([1, 2, 5], 11) == 3def test_no_way():    assert Solution().coinChange([2], 3) == -1問題是我收到“超出時間限制”錯誤:但是,如果我復制這個測試用例并在本地運行它,我發現該算法只需要0.02s:import pytestdef test_time_limit_exceeded():    Solution().coinChange(        [205, 37, 253, 463, 441, 129, 156, 429, 101, 423, 311],        6653)if __name__ == "__main__":    pytest.main([__file__, '--duration', '1'])導致以下輸出:============================= test session starts ==============================platform darwin -- Python 3.6.6, pytest-3.8.1, py-1.6.0, pluggy-0.7.1rootdir: /Users/kurtpeek/GoogleDrive/CodeRust, inifile:collected 11 itemscoin_changing_leetcode2.py ...........                                   [100%]=========================== slowest 1 test durations ===========================0.02s call     coin_changing_leetcode2.py::test_time_limit_exceeded========================== 11 passed in 0.07 seconds ===========================知道為什么 LeetCode 無法實現此實現嗎?
查看完整描述

2 回答

?
PIPIONE

TA貢獻1829條經驗 獲得超9個贊

似乎這件作品:

  fewest[i] = 1 + min(
            (fewest[i - coin] for coin in
                [c for c in coins if i - c >= 0]),
            default=math.inf)

檢查所有硬幣,過濾適當的硬幣。

但是您可以對硬幣名義值進行排序,并且僅針對給定的 i 遍歷足夠小的名義值。


查看完整回答
反對 回復 2021-07-28
  • 2 回答
  • 0 關注
  • 222 瀏覽
慕課專欄
更多

添加回答

舉報

0/150
提交
取消
微信客服

購課補貼
聯系客服咨詢優惠詳情

幫助反饋 APP下載

慕課網APP
您的移動學習伙伴

公眾號

掃描二維碼
關注慕課網微信公眾號