此專欄文章是對力扣上演算法題目各種方法的總結和歸納, 整理出最重要的思路和知識重點并以思維導圖形式呈現, 當然也會加上我對導圖的詳解.
目的是為了更方便快捷的記憶和回憶演算法重點(不用每次都重復看題解), 畢竟演算法不是做了一遍就能完全記住的. 所以本文適合已經知道解題思路和方法, 想進一步加強理解和記憶的朋友, 并不適合第一次接觸此題的朋友(可以根據題號先去力扣看看官方題解, 然后再看本文內容).
關于本專欄所有題目的目錄鏈接, 刷演算法題目的順序/注意點/技巧, 以及思維導圖源檔案問題請點擊此鏈接.
想進大廠, 刷演算法是必不可少的, 歡迎和博主一起打卡刷力扣演算法, 博主同步更新了演算法視頻講解 和 其他文章/導圖講解, 更易于理解, 歡迎來看!
文章目錄
- 0.導圖整理
- 1.動態規劃的空間優化
- 2.貪心法的思想
- 3.分治法: 線段樹
- 3.1 分治法的意義
- 3.2 分治法的思想
- 3.3 java改Python易錯點
- 原始碼
- Python:
- java:
題目鏈接: https://leetcode-cn.com/problems/maximum-subarray/solution/si-wei-dao-tu-zheng-li-3chong-fang-fa-ch-zxih/
0.導圖整理
1.動態規劃的空間優化
這題是典型的動態規劃題目, 最困難的點在于 dp陣列的定義及下標含義: 用ai代表nums[i], 用f(i)代表以第i個數結尾的「連續子陣列的最大和」, 網上也有很多文章介紹了是如何一步步分析來獲得定義的程序的, 但我感覺對于新手來說, 可能還是多見一些類似的題目, 獲得大量的經驗, 這樣比較有效果吧, 畢竟想研究動態規劃的理論基礎還是挺有難度的.
動態規劃最重要的思想就是利用上一個狀態, 對于本題而言就是: 到底要不要加上上一個狀態f(i-1)的資訊, 這完全取決于f(i-1)的正負情況, 這樣我們就能得出了動態規劃的遞推公式: f(i)=max{f(i?1)+ai,ai}
得到了遞推公式后就可以撰寫代碼了, 代碼中的一個技巧就是對于空間復雜度的優化. 當使用動態規劃只需要一個數(并不需要整個dp陣列)時, 我們就沒必要將整個dp陣列都保存下來, 我們只需用變數來記錄下我們需要的某個量即可, 這個優化方法在動態規劃中還是非常常用的方法, 具體的實作參考代碼.
2.貪心法的思想
本題還可以利用貪心法來實作, 貪心的思想是: 從左向右迭代, 一個個數字加過去如果sum<0, 那說明加上它只會變得越來越小, 所以我們將sum置零后重新開始找子序串.
在迭代的程序中要注意, 我們需要用result來不斷維持當前的最大子序和, 因為sum的值是在不斷更新的, 所以我們要及時記錄下它的最大值.
有一個注意點是: 有的朋友可能覺得當陣列全是負數的時候可能會出現問題, 其實是沒有問題的. 因為在sum不斷遍歷的程序中, 早已將最大值不斷傳給result, 即使sum一直是負數被不斷置零也不用擔心, result還是會記錄下最大的那個負數.
3.分治法: 線段樹
3.1 分治法的意義
首先說明一點, 對于這道題而言, 分治法是不如上面的兩種演算法的, 在時間復雜度相同的情況下, 分治法還具有更高的空間復雜度. 分治法的意義如下圖所示, 這里講解它, 主要是為了讓大家先了解一下 線段樹 這種資料結構, 它還是有很廣泛的應用場景的, 畢竟我們刷演算法也是學習的程序, 早晚也都會接觸到它的.
3.2 分治法的思想
大家直接看官方題解的思想可能會一頭霧水, 根本不知道這些要維護的變數是怎么來的, 我找到了另外一篇文章詳細介紹了整個思想的流程, 說明了變數是如何一步一步獲得的, 講解的還是挺清楚的, 如果還是感覺不太懂, 可以看看我錄制的配套視頻, 根據圖片更詳細的說明了整個推導程序.
理解了推導程序后, 再來看官方的題解就比較清晰了, 也能明白每個變數的由來了. 下面是我整理的官方題解的思路:
3.3 java改Python易錯點
在理解演算法思想后, 演算法還是比較容易理解的, 但是官方只提供了java的版本, 我在自己轉化為Python語言的時候, 還是遇到了不少問題的, 因為它涉及到了類的各種相關操作, 差別還是很大的, 如果不使用Python語言的話, 這部分就可以跳過了.
-
定義類時用class, 第一引數是self(沒引數也可以), 定義方法用def, 第一個引數必須是self.
-
定義類的實體屬性, 比如lSum, 定義時必須進行賦值, 比如lSum = 0, 不進行賦值是會報錯的.
-
呼叫方法的時候, 第一個引數必須是self, 這個和java是完全不同的, 不加這個引數就會提醒你少了個引數. 呼叫類的時候,若定義類時沒有引數,不用加self.
-
若你看到出現某某方法還未定義的錯誤, 那說明你定義的幾個方法不是平級的關系, 在java中似乎是沒有區別的, 但是在Python中, 你必須要將被用到的方法放入此方法里面, 也就是縮進一級, 具體操作看兩者代碼的不同.
這些就是我在改代碼時遇到的比較嚴重的錯誤, 可以先了解一下, 說不定以后你也會遇到呢!
原始碼
Python:
# 動態規劃
class Solution{
public int maxSubAray(int[] nums){
//類似尋找最大最小值的題目,初始值一定要定義成理論上的最小最大值
int result = Integer.MIN_VALUE;
int numsSize = nums.length;
int sum = 0;
for (int i = 0; i < numsSize; i++){
sum += nums[i];
result = Math.max(result, sum);
//如果sum < 0,重新開始找子序串
if (sum < 0){
sum = 0;
}
}
return result;
}
}
# 貪心法
class Solution:
def maxSubAray(self, nums: List[int]) -> int:
# 類似尋找最大最小值的題目,初始值一定要定義成理論上的最小最大值
result = float("-inf")
numsSize = len(nums)
sum = 0
for i in range(numsSize):
sum += nums[i]
result = max(result, sum)
# 如果sum < 0,重新開始找子序串
if (sum < 0):
sum = 0
return result
# 分治法: 線段樹
class Solution :
def maxSubAray(self, nums: List[int]) -> int:
class wtevTree : # 線段樹
lSum = 0 # 以左區間為端點的最大子段和
rSum = 0 # 以右區間為端點的最大子段和
iSum = 0 # 區間所有數的和
mSum = 0 # 該區間的最大子段和
def __init__(self,l, r, i, m) : # 建構式
self.lSum = l
self.rSum = r
self.iSum = i
self.mSum = m
# 通過既有的屬性,計算上一層的屬性,一步步往上回傳,獲得線段樹
def pushUp(self, leftT: wtevTree, rightT: wtevTree) -> wtevTree:
# 新子段的lSum等于左區間的lSum或者左區間的 區間和 加上右區間的lSum
l = max(leftT.lSum, leftT.iSum + rightT.lSum)
# 新子段的rSum等于右區間的rSum或者右區間的 區間和 加上左區間的rSum
r = max(leftT.rSum + rightT.iSum, rightT.rSum)
# 新子段的區間和等于左右區間的區間和之和
i = leftT.iSum + rightT.iSum
# 新子段的最大子段和,其子段有可能穿過左右區間,或左區間,或右區間
m = max(leftT.rSum + rightT.lSum, max(leftT.mSum, rightT.mSum))
return wtevTree(l, r, i, m)
# 遞回建立和獲得輸入區間所有子段的結構
def getInfo(self, nums: List[int], left: int, right: int) -> wtevTree:
if (left == right): # 若區間長度為1,其四個子段均為其值
return wtevTree(nums[left], nums[left], nums[left], nums[left])
mid = (left + right) >> 1 # 獲得中間點mid,右移一位相當于除以2,運算更快
leftT = getInfo(self, nums, left, mid)
rightT = getInfo(self, nums, mid + 1, right) # mid+1,左右區間沒有交集，
return pushUp(self, leftT, rightT) # 遞回結束后,做最后一次合并
if ( not nums or len(nums) <= 0): # 輸入校驗
return 0
lens = len(nums) # 獲取輸入長度
return getInfo(self, nums, 0, lens - 1).mSum
java:
// 動態規劃
class Solution {
public int maxSubAray(int[] nums) {
int pre = 0, maxAns = nums[0];
for (int x : nums) {
//pre來維護對于當前f(i)的f(i?1)的值是多少
pre = Math.max(pre + x, x);//判斷f(i-1)是否要加到當前數上
maxAns = Math.max(maxAns, pre);//獲取最大值
}
return maxAns;
}
}
// 貪心法
class Solution{
public int maxSubAray(int[] nums){
//類似尋找最大最小值的題目,初始值一定要定義成理論上的最小最大值
int result = Integer.MIN_VALUE;
int numsSize = nums.length;
int sum = 0;
for (int i = 0; i < numsSize; i++){
sum += nums[i];
result = Math.max(result, sum);
//如果sum < 0,重新開始找子序串
if (sum < 0){
sum = 0;
}
}
return result;
}
}
// 分治法: 線段樹
class Solution {
public int maxSubAray(int[] nums) {
if (nums == null || nums.length <= 0)// 輸入校驗
return 0;
int len = nums.length;// 獲取輸入長度
return getInfo(nums, 0, len - 1).mSum;
}
class wtevTree { //線段樹
int lSum;// 以左區間為端點的最大子段和
int rSum;// 以右區間為端點的最大子段和
int iSum;// 區間所有數的和
int mSum;// 該區間的最大子段和
wtevTree(int l, int r, int i, int m) { // 建構式
lSum = l;
rSum = r;
iSum = i;
mSum = m;
}
}
// 通過既有的屬性,計算上一層的屬性,一步步往上回傳,獲得線段樹
wtevTree pushUp(wtevTree leftT, wtevTree rightT) {
// 新子段的lSum等于左區間的lSum或者左區間的 區間和 加上右區間的lSum
int l = Math.max(leftT.lSum, leftT.iSum + rightT.lSum);
// 新子段的rSum等于右區間的rSum或者右區間的 區間和 加上左區間的rSum
int r = Math.max(leftT.rSum + rightT.iSum, rightT.rSum);
// 新子段的區間和等于左右區間的區間和之和
int i = leftT.iSum + rightT.iSum;
// 新子段的最大子段和,其子段有可能穿過左右區間,或左區間,或右區間
int m = Math.max(leftT.rSum + rightT.lSum, Math.max(leftT.mSum, rightT.mSum));
return new wtevTree(l, r, i, m);
}
// 遞回建立和獲得輸入區間所有子段的結構
wtevTree getInfo(int[] nums, int left, int right) {
if (left == right) // 若區間長度為1,其四個子段均為其值
return new wtevTree(nums[left], nums[left], nums[left], nums[left]);
int mid = (left + right) >> 1;// 獲得中間點mid,右移一位相當于除以2,運算更快
wtevTree leftT = getInfo(nums, left, mid);
wtevTree rightT = getInfo(nums, mid + 1, right);//mid+1,左右區間沒有交集，
return pushUp(leftT, rightT);//遞回結束后,做最后一次合并
}
}
我的更多精彩文章鏈接, 歡迎查看
各種電腦/軟體/生活/音樂/動漫/電影技巧匯總(你肯定能夠找到你需要的使用技巧)
力扣演算法刷題 根據思維導圖整理筆記快速記憶演算法重點內容(歡迎和博主一起打卡刷題哦)
計算機專業知識 思維導圖整理
最值得收藏的 Python 全部知識點思維導圖整理, 附帶常用代碼/方法/庫/資料結構/常見錯誤/經典思想(持續更新中)
最值得收藏的 C++ 全部知識點思維導圖整理(清華大學鄭莉版), 東南大學軟體工程初試906科目
最值得收藏的 計算機網路 全部知識點思維導圖整理(王道考研), 附帶經典5層結構中英對照和框架簡介
最值得收藏的 演算法分析與設計 全部知識點思維導圖整理(北大慕課課程)
最值得收藏的 資料結構 全部知識點思維導圖整理(王道考研), 附帶經典題型整理
最值得收藏的 人工智能導論 全部知識點思維導圖整理(王萬良慕課課程)
最值得收藏的 數值分析 全部知識點思維導圖整理(東北大學慕課課程)
最值得收藏的 數字影像處理 全部知識點思維導圖整理(武漢大學慕課課程)
紅黑樹 一張導圖解決紅黑樹全部插入和洗掉問題 包含詳細操作原理 情況對比
各種常見排序演算法的時間/空間復雜度 是否穩定 演算法選取的情況 改進 思維導圖整理
人工智能課件 演算法分析課件 Python課件 數值分析課件 機器學習課件 影像處理課件
考研相關科目 知識點 思維導圖整理
考研經驗–東南大學軟體學院軟體工程(這些基礎課和專業課的各種坑和復習技巧你應該知道)
東南大學 軟體工程 906 資料結構 C++ 歷年真題 思維導圖整理
東南大學 軟體工程 復試3門科目歷年真題 思維導圖整理
最值得收藏的 考研高等數學 全部知識點思維導圖整理(張宇, 湯家鳳), 附做題技巧/易錯點/知識點整理
最值得收藏的 考研線性代數 全部知識點思維導圖整理(張宇, 湯家鳳), 附帶慣用思維/做題技巧/易錯點整理
高等數學 中值定理 一張思維導圖解決中值定理所有題型
考研思修 知識點 做題技巧 同類比較 重要會議 1800易錯題 思維導圖整理
考研近代史 知識點 做題技巧 同類比較 重要會議 1800易錯題 思維導圖整理
考研馬原 知識點 做題技巧 同類比較 重要會議 1800易錯題 思維導圖整理
考研數學課程筆記 考研英語課程筆記 考研英語單詞詞根詞綴記憶 考研政治課程筆記
Python相關技術 知識點 思維導圖整理
Numpy常見用法全部OneNote筆記 全部筆記思維導圖整理
Pandas常見用法全部OneNote筆記 全部筆記思維導圖整理
Matplotlib常見用法全部OneNote筆記 全部筆記思維導圖整理
PyTorch常見用法全部OneNote筆記 全部筆記思維導圖整理
Scikit-Learn常見用法全部OneNote筆記 全部筆記思維導圖整理
Java相關技術/ssm框架全部筆記
Spring springmvc Mybatis jsp
科技相關 小米手機
小米 紅米 歷代手機型號大全 發布時間 發布價格
常見手機品牌的各種系列劃分及其特點
歷代CPU和GPU的性能情況和常見后綴的含義 思維導圖整理
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/302827.html
標籤：其他
上一篇：計算機網路練習題——一起肥學