此專欄文章是對力扣上算法題目各種方法的總結和歸納, 整理出最重要的思路和知識重點并以思維導圖形式呈現, 當然也會加上我對導圖的詳解.
目的是為了更友善快捷的記憶和回憶算法重點(不用每次都重複看題解), 畢竟算法不是做了一遍就能完全記住的. 是以本文适合已經知道解題思路和方法, 想進一步加強了解和記憶的朋友, 并不适合第一次接觸此題的朋友(可以根據題号先去力扣看看官方題解, 然後再看本文内容).
關于本專欄所有題目的目錄連結, 刷算法題目的順序/注意點/技巧, 以及思維導圖源檔案問題請點選此連結.
想進大廠, 刷算法是必不可少的, 歡迎和部落客一起打卡刷力扣算法, 部落客同步更新了算法視訊講解 和 其他文章/導圖講解, 更易于了解, 歡迎來看!
文章目錄
- 0.導圖整理
- 1.雙指針的思想來源
- 2.雙指針移動的條件
- 3.雙指針合理性的證明
- 4.兩個優化點
- 5.有趣評論
- 源碼
- Python:
- java:
題目連結: https://leetcode-cn.com/problems/container-with-most-water/solution/si-wei-dao-tu-zheng-li-shuang-zhi-zhen-d-tkx5/
0.導圖整理
1.雙指針的思想來源
說實話, 第一次看到這道題, 是真的很難想到 雙指針 的思想的, 看到一個比較有趣的評論: 所謂的解題思路, 就是你解題解的多了, 自然就有思路了. 對于刷算法而言, 真的是太真實了. 有些題目的思想不會就是不會, 根本不是再努力思考一下就能想到的問題. 是以我們隻管更多的刷題再對它們進行總結歸納, 題目刷的多了, 這些巧妙的思想我們自然就會了!
是以我們來總結一下這題的 雙指針 思想, 首先最重要的點: 雙指針大多都是對兩層循環的優化, 是以當暴力法涉及到兩層循環周遊的時候, 我們就應該有這種思想: 能不能用到雙指針的思想.
其次, 就是要有限制的滿足條件, 對于本題而言, 限制的滿足條件就是 每次移動數字較小的那個指針, 我們必須根據題目找到某個條件, 而這個條件就是雙指針的移動條件, 也是使用雙指針思想的基礎. 之後我們會通過大量題目的訓練來切實的掌握雙指針.
2.雙指針移動的條件
本題的一個難點就是 雙指針移動的條件, 要找到這個條件, 我們就需要從題目的定義出發, 也就是容納的水量的含義, 當左右指針分别指向數組的左右兩端, 那
容納的水量 = 兩個指針指向的數字中較小值 ∗ 指針之間的距離
.
接下來我們就隻要考慮移動雙指針後兩者的變化情況即可. 如果我們移動數字較大的那個指針, 那麼前者「兩個指針指向的數字中較小值」不會增加, 後者「指針之間的距離」會減小, 那麼這個乘積會減小, 是以, 我們移動 數字較小的那個指針, 這是從公式的變化角度來解釋如何移動指針的, 還是比較容易了解的, 隻是思想不太嚴謹, 如果想更嚴格的證明, 可以看下面的講解.
3.雙指針合理性的證明
在證明之前先來了解雙指針所代表的含義:
之後就是定量的證明過程了, 過程并不複雜, 就不多解釋了:
4.兩個優化點
本題在上面 雙指針 思想的基礎上存在兩個小的優化點, 對代碼的運作速度還是有一定提升的. 思想都挺清晰的, 代碼上的實作也并不困難, 就不多解釋了:
除此之外就是代碼上的差別了: java中的 Math.max/min 對應于 Python中為 max/min, 因為在java中的這兩個函數屬于Math類下面的方法, 而在Python中這個函數屬于系統方法, 用法也是更加強大!
5.有趣評論
看題解的時候, 發現了幾條挺有趣的評論, 如果你還是不太了解雙指針的移動條件的話, 可以看下這些評論, 也許對你的了解很有幫助!
源碼
Python:
class Solution:
def maxArea(self, height: List[int]) -> int:
l, r = 0, len(height) - 1
ans = 0
while l < r:
area = min(height[l], height[r]) * (r - l)
ans = max(ans, area)
if height[l] <= height[r]: # 移動較小的那一端
l += 1
else:
r -= 1
return ans
java:
public class Solution {
public int maxArea(int[] height) {
int l = 0, r = height.length - 1;
int ans = 0;
while (l < r) {
int area = Math.min(height[l], height[r]) * (r - l);
ans = Math.max(ans, area);
if (height[l] <= height[r]) { // 移動較小的那一端
++l;
}
else {
--r;
}
}
return ans;
}
}
我的更多精彩文章連結, 歡迎檢視
各種電腦/軟體/生活/音樂/動漫/電影技巧彙總(你肯定能夠找到你需要的使用技巧)
力扣算法刷題 根據思維導圖整理筆記快速記憶算法重點内容(歡迎和部落客一起打卡刷題哦)
計算機專業知識 思維導圖整理
最值得收藏的 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的性能情況和常見字尾的含義 思維導圖整理