python題解LeetCode303區(qū)域和檢索示例詳解
題目描述
原題鏈接 :
給定一個整數(shù)數(shù)組 nums,處理以下類型的多個查詢:
- 計算索引 left 和 right (包含 left 和 right)之間的 nums 元素的 和 ,其中 left <= right
實現(xiàn) NumArray 類:
- NumArray(int[] nums) 使用數(shù)組 nums 初始化對象
- int sumRange(int i, int j) 返回數(shù)組 nums 中索引 left 和 right 之間的元素的 總和 ,包含 left 和 right 兩點(也就是 nums[left] + nums[left + 1] + ... + nums[right] )
示例 1:
輸入: ["NumArray", "sumRange", "sumRange", "sumRange"] [[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]] 輸出: [null, 1, -1, -3] 解釋: NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]); numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3) numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1)) numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))
提示:
1 <= nums.length <= 10^4
-10^5 <= nums[i] <= 10^5
0 <= i <= j < nums.length
最多調(diào)用 10^4 次 sumRange 方法
思路分析
如果sumRange方法只調(diào)用一次的話,很簡單,使用暴力求解的方式,時間復(fù)雜度為O(n),如果sumRange方法被多次調(diào)用的話,那么便不能使用暴力求解的方式,因為時間復(fù)雜度會達(dá)到O(n^2),使用動態(tài)規(guī)劃的方式進(jìn)行求解。
建立一個數(shù)組dp, 用于存儲前面所有數(shù)到當(dāng)前數(shù)字的和,例如數(shù)組為[1, 2, 3, 4],則dp = [1, 3, 6, 10];
在sumRange函數(shù)中定義求解方式。以[1, 2, 3, 4]數(shù)組為例,如果[I, j] = [0, 2], 則要求的結(jié)果為res = 6 = 1 + 2 + 3,而對應(yīng)于dp中的數(shù),res = dp[2] – 0,若[I, j ] = [1, 3], 則res = 9 = 2 + 3 + 4 = dp[3] – dp[0] = 10 – 1 = 9, 因此可以由此推斷出求解公式: res = dp[j], if i =0 ; res = dp[j] - dp[i-1], if i > 0
AC 代碼
class NumArray: def __init__(self, nums: List[int]): self.dp = [] if len(nums) == 0: return self.dp.append(nums[0]) for i in range(1, len(nums)): self.dp.append(self.dp[i-1] + nums[i]) def sumRange(self, i: int, j: int) -> int: if i == 0: return self.dp[j] else: return self.dp[j] - self.dp[i - 1] # Your NumArray object will be instantiated and called as such: # obj = NumArray(nums) # param_1 = obj.sumRange(i,j)
以上就是python題解LeetCode303區(qū)域和檢索示例詳解的詳細(xì)內(nèi)容,更多關(guān)于python題解區(qū)域檢索的資料請關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
關(guān)于Python中異常(Exception)的匯總
異常是指程序中的例外,違例情況。異常機(jī)制是指程序出現(xiàn)錯誤后,程序的處理方法。當(dāng)出現(xiàn)錯誤后,程序的執(zhí)行流程發(fā)生改變,程序的控制權(quán)轉(zhuǎn)移到異常處理。下面這篇文章主要匯總了關(guān)于Python中異常(Exception)的相關(guān)資料,需要的朋友可以參考下。2017-01-01Python實現(xiàn)將內(nèi)容轉(zhuǎn)為base64編碼與解碼
這篇文章主要為大家詳細(xì)介紹了Python實現(xiàn)將內(nèi)容轉(zhuǎn)為base64編碼與解碼的示例代碼,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以了解一下2023-02-02python中的PywebIO模塊制作一個數(shù)據(jù)大屏
這篇文章主要介紹了python中的PywebIO模塊制作一個數(shù)據(jù)大屏,一個制作數(shù)據(jù)大屏的工具,非常的好用,100行的Python代碼就可以制作出來一個完整的數(shù)據(jù)大屏,并且代碼的邏輯非常容易理解,需要的朋友可以參考一下2022-03-03在Python中獲取兩數(shù)相除的商和余數(shù)方法
今天小編就為大家分享一篇在Python中獲取兩數(shù)相除的商和余數(shù)方法,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧2018-11-11用TensorFlow實現(xiàn)多類支持向量機(jī)的示例代碼
這篇文章主要介紹了用TensorFlow實現(xiàn)多類支持向量機(jī)的示例代碼,小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧2018-04-04