項目 widget-area-1 尚未註冊或是沒有一個 view.php 檔案.
項目 widget-area-1 尚未註冊或是沒有一個 view.php 檔案.
項目 search-input 尚未註冊或是沒有一個 view.php 檔案.

【Leetcode】python – [238] Product of Array Except Self 個人解法筆記

題目出處

238. Product of Array Except Self

難度

medium

個人範例程式碼

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        if not nums:
            return []

        result = [1 for _ in range(len(nums))]

        prefix_product = 1
        for i in range(len(nums)):
            result[i] *= prefix_product # first *= 1
            prefix_product *= nums[i]                        

        postfix_product = 1
        for i in range(len(nums)-1, -1, -1):
            result[i] *= postfix_product # first *= 1
            postfix_product *= nums[i]   

        return result

算法說明

這題要 O(n^2) 時間做出來非常容易,但題目先是希望要求 O(n) 時間算完,
既然都要求這樣的時間,我們勢必要做一些特殊的處理。

這裡我們用到類似 prefixSum 的概念 (我們用的是 prefixProduct)
因為仔細觀察,我們會發現答案就等於「前面積*後面積」,而數字分布是「前面積、(該數字)、後面積」,
因此我們可以簡單的用一個數字紀錄答案。

同時我們也可以實現「 O(1) 空間」的題目追加要求

input handling

如果沒有 nums, 回傳 [] (題目沒特別要求)

Boundary conditions

用兩次 for 迴圈控制範圍

Reference

⭐ Leetcode 解題紀錄 ⭐題型資料結構Python SolutionC++ SolutionNote
⭐BFS 相關題型 ⭐
104Maximum Depth of Binary TreeBFS (分層)Python
94Binary Tree Inorder TraversalBFS (分層)TreePython 內含 處理 Tree 樹問題的重點
102Binary Tree Level Order TraversalBFS (分層)TreePython
103Binary Tree Zigzag Level Order TraversalBFS (分層)TreePython
107Binary Tree Level Order Traversal IIBFS (分層)TreePython
133Clone GraphBFS (分層)GraphPython Graph 的基本操作 #重要題型
127Word LadderBFS (分層), DFSGraphPython
[Lint] 127Topological SortingBFS (拓撲)Python
內有 indegree, outdegree 介紹 #重要題型
207Course ScheduleBFS (拓樸)GraphPython
210Course Schedule IIBFS (拓樸)GraphPython
[Lint] 892Alien DictionaryBFS (拓樸)GraphPython
[Lint] 431Connected Component in Undirected GraphBFS (連通塊)GraphPython 內含 BFS 模板 #重要題型
1091Shortest Path in Binary MatrixBFS (最短路徑)MatrixPython
⭐ B