python題解LeetCode303區(qū)域和檢索示例詳解
題目描述
原題鏈接 :
給定一個整數(shù)數(shù)組 nums，處理以下類型的多個查詢:
- 計(jì)算索引 left 和 right （包含 left 和 right）之間的 nums 元素的 和 ，其中 left <= right
實(shí)現(xiàn) NumArray 類：
- NumArray(int[] nums) 使用數(shù)組 nums 初始化對象
- int sumRange(int i, int j) 返回?cái)?shù)組 nums 中索引 left 和 right 之間的元素的 總和 ，包含 left 和 right 兩點(diǎn)（也就是 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)用的話，那么便不能使用暴力求解的方式，因?yàn)闀r間復(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)文章
Python操作RabbitMQ服務(wù)器實(shí)現(xiàn)消息隊(duì)列的路由功能
RabbitMQ是一個消息隊(duì)列服務(wù)器,這里我們針對Python+Pika+RabbitMQ的服務(wù)器端環(huán)境,來看一下如何使用Python操作RabbitMQ服務(wù)器實(shí)現(xiàn)消息隊(duì)列的路由功能2016-06-06
Python進(jìn)階教程之創(chuàng)建本地PyPI倉庫
pypi是一個python包的倉庫,里面有很多別人寫好的python庫,你可以通過easy_install或者pip進(jìn)行安裝,下面這篇文章主要給大家介紹了關(guān)于Python進(jìn)階教程之創(chuàng)建本地PyPI倉庫的相關(guān)資料,需要的朋友可以參考下2021-10-10
Python處理JSON時的值報(bào)錯及編碼報(bào)錯的兩則解決實(shí)錄
這篇文章主要介紹了Python處理JSON時的值報(bào)錯及編碼報(bào)錯的兩則解決實(shí)錄,在這里還是想建議一下使用Python 3.x版本,Python 3默認(rèn)的Unicode編碼能在實(shí)際使用中為我們省去不少問題,需要的朋友可以參考下2016-06-06
pycharm 無法加載文件activate.ps1的原因分析及解決方法
這篇文章主要介紹了pycharm報(bào)錯提示：無法加載文件\venv\Scripts\activate.ps1，因?yàn)樵诖讼到y(tǒng)上禁止運(yùn)行腳本,解決方法終端輸入get-executionpolicy，回車返回Restricted即可，需要的朋友可以參考下2022-11-11
今天小編就為大家分享一篇用Python一鍵搭建Http服務(wù)器的方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-06-06
如何使用python數(shù)據(jù)處理解決數(shù)據(jù)沖突和樣本的選取
這篇文章主要介紹了如何使用python數(shù)據(jù)處理解決數(shù)據(jù)沖突和樣本的選取，其中主要包括 實(shí)際業(yè)務(wù)數(shù)據(jù)沖突、樣本選取問題、數(shù)據(jù)共線性等思路2021-08-08
在日常的文件操作和數(shù)據(jù)處理中,文件匹配是一個非常常見的任務(wù),本文將詳細(xì)介紹如何使用?Python?實(shí)現(xiàn)文件匹配,有需要的小伙伴可以參考下2024-12-12
Python 實(shí)現(xiàn)敏感目錄掃描的示例代碼
這篇文章主要介紹了Python 實(shí)現(xiàn)敏感目錄掃描的示例代碼,本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-05-05
這篇文章主要為大家詳細(xì)介紹了Python實(shí)現(xiàn)環(huán)形鏈表，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-05-05
Python實(shí)現(xiàn)在線暴力破解郵箱賬號密碼功能示例【測試可用】
這篇文章主要介紹了Python實(shí)現(xiàn)在線暴力破解郵箱賬號密碼功能,結(jié)合完整實(shí)例形式分析了Python讀取txt字典文件針對郵箱的相關(guān)驗(yàn)證破解操作技巧,需要的朋友可以參考下2017-09-09