tags: leetcode
https://leetcode.com/problems/product-of-array-except-self/description/
題目 LeetCode 238
思路
- 我們要把除了
nums[i]以外的數乘起來，並且對每個 i 都做一次這件事情 - 最直覺的方法：阿就做阿，每個 i 都做一次嘛，沒什麼大不了
- 哭阿，在題目就講了要 $O(n)$，如果用這個方法會是 $O(n^2)$
- 我先把整個nums乘起來，然後再分別除以
nums[i]就好了，這樣就 $O(n)$ 了 - 可是這樣會有兩個疑慮: (1) 如果
nums[i]是 0 怎麼辦 (2) 哭阿，題目又講了不能用除法…走頭無路了 - 重新思考一下這個題目，其實有很多乘法會重複做，比如說如果
$$nums = [a, b, c, d]$$
那 output會是:
$$[b\times c \times d, a\times c \times d, a\times b \times d, a\times b \times c]$$ - 既然速度要快，那我們就 拿空間換取時間 ，來到本題的核心精神： 想辦法把會重複計算到的東西都存下來，要用的時候再拿出來就好，不要再重複計算一次
- 撞破可愛的小腦袋後，我們可以發現一個事實：對每個數字而言，都可以分成左翼和右翼 (比如對b而言，左翼是 [a], 右翼是 [c, d])，而每個位置要放的數字都是
$$左翼 \times 右翼$$ - 所以我們可以把 全部可能的左翼乘積 和 全部可能的右翼乘積 都存起來，像下圖
- 上面那步很難想啦…想不到就算了，這樣對每個 i 而言，只要把
l2r[i-1]和r2l[i+1]乘起來就好了 - 我們可以寫出解法一
解法一
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
l2r = [1 for _ in range(n)]
r2l = [1 for _ in range(n)]
cur_val = 1
for i in range(n):
cur_val *= nums[i]
l2r[i] = cur_val
cur_val = 1
for i in range(n-1, -1, -1):
cur_val *= nums[i]
r2l[i] = cur_val
result = [1 for _ in range(n)]
for i in range(n):
if i == 0:
result[i] = r2l[i+1]
elif i == n-1:
result[i] = l2r[i-1]
else:
result[i] = l2r[i-1] * r2l[i+1]
return result筆記
- 在寫這題的時候會用到
for i in range ...的語法，很多人會疑惑到底該怎麼寫 n, n+1, n-1, …，這時只要切記一個口訣: 含頭不含尾! 含頭不含尾! 含頭不含尾!
l = ['g', 'r', 'a', 'n', 'd', 'm', 'a']
for i in range(1, 5):
print(l[i])
# 含頭 = 1，不含尾 = 5
# 所以 i 會從 1 到 4 : 1, 2, 3, 4
# output:
# r
# a
# n
# d同樣的
l = ['g', 'r', 'a', 'n', 'd', 'm', 'a']
print(l[1:5])
# 含頭 = 1，不含尾 = 5
# output:
# ['r', 'a', 'n', 'd']如果把一個list從後面iterate回來，要這樣寫
l = ['g', 'r', 'a', 'n', 'd', 'm', 'a']
for i in range(len(l) - 1, -1, -1):
print(l[i])
# 含頭: len(l) -1 所以是最後一個element
# 不含尾 = -1，所以最後一個數字會是 0，也就是第一個element
# output:
# a
# m
# d
# n
# a
# r
# g- 寫完後發現文章裡面沒有提到前綴和…之後再來介紹好了
- HackMD筆記: https://hackmd.io/@ga642381/BJ_EOUwti
