欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

python題解LeetCode303區(qū)域和檢索示例詳解

 更新時間:2022年12月30日 14:45:05   作者:劉09k11  
這篇文章主要為大家介紹了python題解LeetCode303區(qū)域和檢索示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪

題目描述

原題鏈接 :

303. 區(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)文章

  • python?print無法打印\r的問題及解決

    python?print無法打印\r的問題及解決

    這篇文章主要介紹了python?print無法打印\r的問題及解決方案,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教
    2023-08-08
  • python如何去除圖像中的框

    python如何去除圖像中的框

    最近在做圖像標(biāo)注,會出現(xiàn)帶框的圖片,需要去除其中的邊框,本文通過實例代碼給大家介紹python如何去除圖像中的框,感興趣的朋友跟隨小編一起看看吧
    2023-11-11
  • python爬蟲多次請求超時的幾種重試方法(6種)

    python爬蟲多次請求超時的幾種重試方法(6種)

    這篇文章主要介紹了python爬蟲多次請求超時的幾種重試方法,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2020-12-12
  • python?pytorch圖像識別基礎(chǔ)介紹

    python?pytorch圖像識別基礎(chǔ)介紹

    大家好,本篇文章主要講的是python?pytorch圖像識別基礎(chǔ)介紹,感興趣的同學(xué)趕快來看一看吧,對你有幫助的話記得收藏一下
    2022-02-02
  • Python關(guān)于OS文件目錄處理的實例分享

    Python關(guān)于OS文件目錄處理的實例分享

    在本篇文章里小編給大家整理的是一篇關(guān)于Python關(guān)于OS文件目錄處理的實例內(nèi)容,有興趣的朋友們可以學(xué)一下。
    2021-05-05
  • 關(guān)于Python中異常(Exception)的匯總

    關(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-01
  • Python實現(xiàn)將內(nèi)容轉(zhuǎn)為base64編碼與解碼

    Python實現(xiàn)將內(nèi)容轉(zhuǎn)為base64編碼與解碼

    這篇文章主要為大家詳細(xì)介紹了Python實現(xiàn)將內(nèi)容轉(zhuǎn)為base64編碼與解碼的示例代碼,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以了解一下
    2023-02-02
  • python中的PywebIO模塊制作一個數(shù)據(jù)大屏

    python中的PywebIO模塊制作一個數(shù)據(jù)大屏

    這篇文章主要介紹了python中的PywebIO模塊制作一個數(shù)據(jù)大屏,一個制作數(shù)據(jù)大屏的工具,非常的好用,100行的Python代碼就可以制作出來一個完整的數(shù)據(jù)大屏,并且代碼的邏輯非常容易理解,需要的朋友可以參考一下
    2022-03-03
  • 在Python中獲取兩數(shù)相除的商和余數(shù)方法

    在Python中獲取兩數(shù)相除的商和余數(shù)方法

    今天小編就為大家分享一篇在Python中獲取兩數(shù)相除的商和余數(shù)方法,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2018-11-11
  • 用TensorFlow實現(xiàn)多類支持向量機(jī)的示例代碼

    用TensorFlow實現(xiàn)多類支持向量機(jī)的示例代碼

    這篇文章主要介紹了用TensorFlow實現(xiàn)多類支持向量機(jī)的示例代碼,小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2018-04-04

最新評論