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 是輸入陣列的長度。這個方法不會出現上一個方法中的除以零問題。
留言0
查看全部
你可能也想看
Google News 追蹤
嘿，大家新年快樂~ 新年大家都在做什麼呢？
跨年夜的我趕工製作某個外包設計案，在工作告一段落時趕上倒數。
然後和兩個小孩過了一個忙亂的元旦。在深夜時刻，看到朋友傳來的解籤網站，興致勃勃熬夜體驗了一下，覺得非常好玩，或許有人玩過了，但還是想寫上來分享紀錄一下~
題目敘述 Combination Sum II_Leetcode #40
給定一個整數陣列candidates 和 目標值target。
每個陣列元素只能選擇一次，請問有多少種組合方法，可以使得組合數總和 = target?
請把滿足組合數總和 = target的組合方法以陣列的形式返回答案
題目敘述 Combination Sum IV
給定一個輸入陣列nums，和目標值target，從nums裡面挑數字去湊出總和 = target，數字可以重複挑選。
請問有多少排列數可以湊出target？
註: 排列數的意思就是位置不同代表兩種不同的方法數。
分享在網路上看到的陣列題目。通常 for...of 的 value 是陣列中的每個值，那如果我們在迭代中對陣列操作會發生什麼事？
題目來源：https://x.com/_jayphelps/status/1774640511158022335?s=20
題目會給定一個陣列nums和一個目標值goal。計算子陣列總和=goal的數目有多少。演算法包含前綴和和字典的技巧，時間複雜度為O(n)，空間複雜度為O(n)。
題目敘述
題目會給定我們一個輸入陣列nums，要求我們掃描美個陣列元素nums[i]，計算除了nums[i]以外的陣列元素連乘積。
題目的原文敘述
測試範例
Example 1:
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
nums[0] 以
題目敘述
題目會給定我們兩個整數陣列作為輸入nums1, nums2，要求我們找出兩個陣列的差異值。
找出在nums1但是不在nums2的元素，以陣列的形式放在answer[0]輸出。
找出在nums2但是不在nums1的元素，以陣列的形式放在answer[1]輸出。
題目的原文敘述
題目敘述
題目會給我們一個參數k 和 目標值n。
請問我們從1~9內挑k個相異的數字，使得他們的總和為n 的組合數有多少？
挑選時，每個數字必須相異，而且每個數字只能選一次。
題目的原文敘述
測試範例
Example 1:
Input: k = 3, n = 7
Output: [
題目敘述
題目會給我們一個輸入陣列nums，和一個指定的k值。
請問，在輸入陣列nums中，有幾個子陣列的元素總合恰好為k ？
例如: nums = [1,2,3], k = 3
則有兩個子陣列的元素總合為3，分別是[1,2] 和 [3]
如果是第一次聽到或接觸前綴和prefix的同學
題目敘述
題目的情境是設計並且實現一個包含所有正整數的數據流，以set集合的方式存在。
數據流 = {1, 2, 3, 4, ..., ∞}
要求我們去實現定義好的function介面:
SmallestInfiniteSet()建構子，初始化這個包含所有正整數的數據流。
int po
題目敘述
題目會給我們一個整數陣列，裡面包含各種正整數，每回合可以消去兩個相同的數字，或者消去三個相同的數字。問最少需要幾次消去，才能讓陣列為空? 如果無解，則返回-1
詳細的題目可在這裡看到
測試範例
Example 1:
Input: nums = [2,3,3,2,2,4,2,3,
嘿，大家新年快樂~ 新年大家都在做什麼呢？
跨年夜的我趕工製作某個外包設計案，在工作告一段落時趕上倒數。
然後和兩個小孩過了一個忙亂的元旦。在深夜時刻，看到朋友傳來的解籤網站，興致勃勃熬夜體驗了一下，覺得非常好玩，或許有人玩過了，但還是想寫上來分享紀錄一下~
題目敘述 Combination Sum II_Leetcode #40
給定一個整數陣列candidates 和 目標值target。
每個陣列元素只能選擇一次，請問有多少種組合方法，可以使得組合數總和 = target?
請把滿足組合數總和 = target的組合方法以陣列的形式返回答案
題目敘述 Combination Sum IV
給定一個輸入陣列nums，和目標值target，從nums裡面挑數字去湊出總和 = target，數字可以重複挑選。
請問有多少排列數可以湊出target？
註: 排列數的意思就是位置不同代表兩種不同的方法數。
分享在網路上看到的陣列題目。通常 for...of 的 value 是陣列中的每個值，那如果我們在迭代中對陣列操作會發生什麼事？
題目來源：https://x.com/_jayphelps/status/1774640511158022335?s=20
題目會給定一個陣列nums和一個目標值goal。計算子陣列總和=goal的數目有多少。演算法包含前綴和和字典的技巧，時間複雜度為O(n)，空間複雜度為O(n)。
題目敘述
題目會給定我們一個輸入陣列nums，要求我們掃描美個陣列元素nums[i]，計算除了nums[i]以外的陣列元素連乘積。
題目的原文敘述
測試範例
Example 1:
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
nums[0] 以
題目敘述
題目會給定我們兩個整數陣列作為輸入nums1, nums2，要求我們找出兩個陣列的差異值。
找出在nums1但是不在nums2的元素，以陣列的形式放在answer[0]輸出。
找出在nums2但是不在nums1的元素，以陣列的形式放在answer[1]輸出。
題目的原文敘述
題目敘述
題目會給我們一個參數k 和 目標值n。
請問我們從1~9內挑k個相異的數字，使得他們的總和為n 的組合數有多少？
挑選時，每個數字必須相異，而且每個數字只能選一次。
題目的原文敘述
測試範例
Example 1:
Input: k = 3, n = 7
Output: [
題目敘述
題目會給我們一個輸入陣列nums，和一個指定的k值。
請問，在輸入陣列nums中，有幾個子陣列的元素總合恰好為k ？
例如: nums = [1,2,3], k = 3
則有兩個子陣列的元素總合為3，分別是[1,2] 和 [3]
如果是第一次聽到或接觸前綴和prefix的同學
題目敘述
題目的情境是設計並且實現一個包含所有正整數的數據流，以set集合的方式存在。
數據流 = {1, 2, 3, 4, ..., ∞}
要求我們去實現定義好的function介面:
SmallestInfiniteSet()建構子，初始化這個包含所有正整數的數據流。
int po
題目敘述
題目會給我們一個整數陣列，裡面包含各種正整數，每回合可以消去兩個相同的數字，或者消去三個相同的數字。問最少需要幾次消去，才能讓陣列為空? 如果無解，則返回-1
詳細的題目可在這裡看到
測試範例
Example 1:
Input: nums = [2,3,3,2,2,4,2,3,