題目

  • 題目連結
  • 目標函式 : productExceptSelf(nums)
    • Input : nums: List[int]
    • Output : List[int]

解題概念

  • 題意 : 給定一整數陣列 nums，需要回傳一陣列 answer，使得 answer[i] 等於 nums 中除了 nums[i] 之外之所有元素的乘積
    • 其中時間複雜度需要為 $O(n)$，且不能使用除法

我的寫法

  • 想法 : 先從左右各自算出各自的乘積，最後再將兩個陣列相乘
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    def productExceptSelf(self, nums):
        
        left = [1 for _ in nums]
        right = [1 for _ in nums]

        for i in xrange(1, len(nums)):
            left[i] = left[i - 1] * nums[i - 1]
        
        for i in xrange(len(nums) - 2, -1, -1):
            right[i] = right[i + 1] * nums[i + 1]
        
        for i in xrange(len(nums)):
            left[i] *= right[i]
        return left
  • 成效 :
    • Time Complexity : $O(n)$
    • Runtime: 167 ms (faster than 68.59%)
    • Memory Usage: 19.9 MB (more than 93.61%)

解答 or 其他優秀寫法 - Dynamic Programming

  • 想法 : 應該使用 Dynamic Programming
    • 使用 dp[0] ~ dp[amount] 去紀錄從 0 到 amount 的最佳解
    • 然後使用雙重迴圈 : 先針對每個可能 amount 的值 i，再針對每個 coin
    • 若 i 比 coin 大，即更新 dp[i] (決定計不計算 coin，再取較小值 min(dp[i], dp[i - coin] + 1))
    • 若最後發現 dp[amount] == max_value，代表 amount 無解，則回傳 -1
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    def productExceptSelf(self, nums):
        
        left = [1 for _ in nums]
        right = [1 for _ in nums]

        for i in xrange(1, len(nums)):
            left[i] = left[i - 1] * nums[i - 1]
        
        temp_right = 1
        for i in xrange(len(nums) - 1, -1, -1):
            left[i] *= temp_right
            temp_right *= nums[i]
        
        return left
  • 成效 :
    • Time Complexity : $O(n)$
    • Runtime: 166 ms (faster than 71.36%)
    • Memory Usage: 19.1 MB (more than 96.88%)