題目出處
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 Solution | C++ Solution | Note | |
---|---|---|---|---|---|---|
⭐BFS 相關題型 ⭐ | ||||||
104 | Maximum Depth of Binary Tree | BFS (分層) | Python | |||
94 | Binary Tree Inorder Traversal | BFS (分層) | Tree | Python | 內含 處理 Tree 樹問題的重點 | |
102 | Binary Tree Level Order Traversal | BFS (分層) | Tree | Python | ||
103 | Binary Tree Zigzag Level Order Traversal | BFS (分層) | Tree | Python | ||
107 | Binary Tree Level Order Traversal II | BFS (分層) | Tree | Python | ||
133 | Clone Graph | BFS (分層) | Graph | Python | Graph 的基本操作 #重要題型 | |
127 | Word Ladder | BFS (分層), DFS | Graph | Python | ||
[Lint] 127 | Topological Sorting | BFS (拓撲) | Python | 內有 indegree, outdegree 介紹 #重要題型 | ||
207 | Course Schedule | BFS (拓樸) | Graph | Python | ||
210 | Course Schedule II | BFS (拓樸) | Graph | Python | ||
[Lint] 892 | Alien Dictionary | BFS (拓樸) | Graph | Python | ||
[Lint] 431 | Connected Component in Undirected Graph | BFS (連通塊) | Graph | Python | 內含 BFS 模板 #重要題型 | |
1091 | Shortest Path in Binary Matrix | BFS (最短路徑) | Matrix | Python | ||
⭐ B |