We love coding - #2
更新於 發佈於 閱讀時間約 2 分鐘
Hi, I'm coding dog. We love coding.
Here's today's coding interview problem.
Q:
給定一個整數陣列，請回傳一個新的陣列，其中新陣列中的每個索引 i 的元素都是原始陣列中除了索引 i 的所有數字的乘積。
例如，如果我們的輸入是 [1, 2, 3, 4, 5]，則預期輸出為 [120, 60, 40, 30, 24]。如果我們的輸入是 [3, 2, 1]，則預期輸出為 [2, 3, 6]。不使用除法。
A:
解決這個問題，我們可以先計算出陣列中所有元素的乘積。然後，對於陣列中的每個元素，我們可以將總乘積除以該元素，以獲得其他元素的乘積。我們可以使用一個新的陣列來存儲這些乘積。
以下是這個方法的 Python 代碼：
def product_except_self(nums):product = 1for num in nums:product *= numresult = []for num in nums:result.append(product // num)return result
這個方法的時間複雜度為 O(n)，其中 n 是輸入陣列的長度。但是，如果輸入陣列中有零，就可能會出現除以零的問題。
要處理不能使用除法的情況，我們可以使用兩個陣列：一個用於存儲每個元素左側所有元素的乘積，另一個用於存儲每個元素右側所有元素的乘積。然後，我們可以結合這兩個陣列來獲得最終結果。
以下是這個方法的 Python 代碼：
def product_except_self(nums):n = len(nums)left_products = [1] * nright_products = [1] * nfor i in range(1, n):left_products[i] = left_products[i-1] * nums[i-1]for i in range(n-2, -1, -1):right_products[i] = right_products[i+1] * nums[i+1]result = [left_products[i] * right_products[i] for i in range(n)]return result
這個方法的時間複雜度為 O(n)，其中 n 是輸入陣列的長度。這個方法不會出現上一個方法中的除以零問題。
留言
留言分享你的想法！
你可能也想看
Google News 追蹤
川普2.0的關稅與貿易政策，表面看似反覆無常，實則圍繞著幾個核心目標：扭轉貿易不公、推動美國再工業化、確保戰略自主，以及貫徹「美國優先」原則。本文深入剖析其背後的一致性邏輯、長期戰略意義，以及對全球產業鏈的影響，並探討不同產業的贏家與輸家。
The Bruno Mathsson Prize 40 Years 展覽，顧名思義，就是源自家具設計師兼建築師布魯諾·馬特松 (Bruno Mathsson，1907-88 年) 所創造的獎項而設。但 Bruno 是誰？
題目敘述 Combination Sum II_Leetcode #40
給定一個整數陣列candidates 和 目標值target。
每個陣列元素只能選擇一次，請問有多少種組合方法，可以使得組合數總和 = target?
請把滿足組合數總和 = target的組合方法以陣列的形式返回答案
今天分享的繪本 “Clifford, We Love You” (Norman Bridwell)，是融合歌曲在朗讀裡，旋律超級洗腦，和小朋友共讀完後，他們還會不自覺地哼唱。
題目敘述 Combination Sum IV
給定一個輸入陣列nums，和目標值target，從nums裡面挑數字去湊出總和 = target，數字可以重複挑選。
請問有多少排列數可以湊出target？
註: 排列數的意思就是位置不同代表兩種不同的方法數。
她們有時很率性，她們有時也很脆弱。Goro的編曲，Wyman的文字，恰似是COLLAR的強心針，更是一種催化劑，讓這七位女生之間的凝聚力，大得連拖拉機也拉不開。
分享在網路上看到的陣列題目。通常 for...of 的 value 是陣列中的每個值，那如果我們在迭代中對陣列操作會發生什麼事？
題目來源：https://x.com/_jayphelps/status/1774640511158022335?s=20
[Verse 1]
I didn't think you'd understand me
我沒想到你會理解我
How could you ever even try?
你怎麼會試著理解呢？
I don't wanna tiptoe but I don't wanna hide
我不想偷偷
題目會給定一個陣列nums和一個目標值goal。計算子陣列總和=goal的數目有多少。演算法包含前綴和和字典的技巧，時間複雜度為O(n)，空間複雜度為O(n)。
題目敘述
題目會給我們一個參數k 和 目標值n。
請問我們從1~9內挑k個相異的數字，使得他們的總和為n 的組合數有多少？
挑選時，每個數字必須相異，而且每個數字只能選一次。
題目的原文敘述
測試範例
Example 1:
Input: k = 3, n = 7
Output: [
川普2.0的關稅與貿易政策，表面看似反覆無常，實則圍繞著幾個核心目標：扭轉貿易不公、推動美國再工業化、確保戰略自主，以及貫徹「美國優先」原則。本文深入剖析其背後的一致性邏輯、長期戰略意義，以及對全球產業鏈的影響，並探討不同產業的贏家與輸家。
The Bruno Mathsson Prize 40 Years 展覽，顧名思義，就是源自家具設計師兼建築師布魯諾·馬特松 (Bruno Mathsson，1907-88 年) 所創造的獎項而設。但 Bruno 是誰？
題目敘述 Combination Sum II_Leetcode #40
給定一個整數陣列candidates 和 目標值target。
每個陣列元素只能選擇一次，請問有多少種組合方法，可以使得組合數總和 = target?
請把滿足組合數總和 = target的組合方法以陣列的形式返回答案
今天分享的繪本 “Clifford, We Love You” (Norman Bridwell)，是融合歌曲在朗讀裡，旋律超級洗腦，和小朋友共讀完後，他們還會不自覺地哼唱。
題目敘述 Combination Sum IV
給定一個輸入陣列nums，和目標值target，從nums裡面挑數字去湊出總和 = target，數字可以重複挑選。
請問有多少排列數可以湊出target？
註: 排列數的意思就是位置不同代表兩種不同的方法數。
她們有時很率性，她們有時也很脆弱。Goro的編曲，Wyman的文字，恰似是COLLAR的強心針，更是一種催化劑，讓這七位女生之間的凝聚力，大得連拖拉機也拉不開。
分享在網路上看到的陣列題目。通常 for...of 的 value 是陣列中的每個值，那如果我們在迭代中對陣列操作會發生什麼事？
題目來源：https://x.com/_jayphelps/status/1774640511158022335?s=20
[Verse 1]
I didn't think you'd understand me
我沒想到你會理解我
How could you ever even try?
你怎麼會試著理解呢？
I don't wanna tiptoe but I don't wanna hide
我不想偷偷
題目會給定一個陣列nums和一個目標值goal。計算子陣列總和=goal的數目有多少。演算法包含前綴和和字典的技巧，時間複雜度為O(n)，空間複雜度為O(n)。
題目敘述
題目會給我們一個參數k 和 目標值n。
請問我們從1~9內挑k個相異的數字，使得他們的總和為n 的組合數有多少？
挑選時，每個數字必須相異，而且每個數字只能選一次。
題目的原文敘述
測試範例
Example 1:
Input: k = 3, n = 7
Output: [