此專欄文章是對力扣上算法題目各種方法的總結和歸納, 整理出最重要的思路和知識重點并以思維導圖形式呈現, 當然也會加上我對導圖的詳解.
目的是為了更友善快捷的記憶和回憶算法重點(不用每次都重複看題解), 畢竟算法不是做了一遍就能完全記住的. 是以本文适合已經知道解題思路和方法, 想進一步加強了解和記憶的朋友, 并不适合第一次接觸此題的朋友(可以根據題号先去力扣看看官方題解, 然後再看本文内容).
關于本專欄所有題目的目錄連結, 刷算法題目的順序/注意點/技巧, 以及思維導圖源檔案問題請點選此連結.
想進大廠, 刷算法是必不可少的, 歡迎和部落客一起打卡刷力扣算法, 部落客同步更新了算法視訊講解 和 其他文章/導圖講解, 更易于了解, 歡迎來看!
關注部落客獲得題解更新的最新消息!!!
文章目錄
- 0.導圖整理
- 1.和股票I的動态規劃差別
- 2.貪心法的思想
- 源碼
- Python:
- java:
題目連結: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/solution/si-wei-dao-tu-zheng-li-gu-piao-wen-ti-ii-7bmc/
0.導圖整理
1.和股票I的動态規劃差別
大家在看此題之前, 推薦先看 股票I買賣一次 的題解分析, 因為本題的動态規劃方法和它隻有一處不同, 其他的思路和代碼是一模一樣的, 這也是為什麼我在上題中一定要仔細講解動态規劃方法的原因.
看完上一題的題解後你就會發現, 本題和上題唯一不同的地方, 就是推導have[i]的第二種情況的時候: 第i天買入股票的情況是不同的, 因為在上題中股票全程隻能買賣一次, 是以如果買入股票, 那麼第i天持有股票即have[i]一定就是 -prices[i], 而本題中, 因為一隻股票可以買賣多次, 是以當第i天買入股票的時候, 所持有的現金可能有之前買賣過的利潤, 是以have[i]=no[i-1]-prices[i]. 這就是兩題唯一不同的地方了, 其他地方都是一模一樣了!
當然, 在代碼中也隻需要更改這一小處地方就可以了!
2.貪心法的思想
在上一題中, 我們講解了使用貪心法的思想, 因為全程隻能買賣一次, 是以貪心的思想很自然就是取最左最小值, 取最右最大值, 那麼得到的內插補點就是最大利潤.
而在本題中, 由于不限制交易次數, 是以隻要今天股價比昨天高, 就交易. 将整個區間劃分為長度為1的n個區間, 找到所有利潤為正值的區間(上升區間)相加即可. 思想還是比較簡單的, 代碼實作也不複雜!
這裡有個值得注意的點: 貪心算法隻能用于計算最大利潤, 計算的過程并不是實際的交易過程.
最後來欣賞一下python的一行代碼解決, 因為文法的特性, 可以使python在一行中完成很多指令, 其他語言還是很難做到這點的.
源碼
Python:
# 動态規劃
class Solution:
def maxProfit(self, prices: List[int]) -> int:
length = len(prices)
if len == 0:
return 0
have = [0] * length # 表示第i天持有股票所得最多現金
no = [0] * length # 表示第i天不持有股票所得最多現金
have[0] = -prices[0] # 此時的持有股票就一定是買入股票了
no[0] = 0 # 不持有股票那麼現金就是0
for i in range(1, length):
have[i] = max(have[i-1], no[i-1] - prices[i]) # 唯一不同之處
no[i] = max(no[i-1], prices[i] + have[i-1])
return no[-1] # 不持有股票狀态所得金錢一定比持有股票狀态得到的多
# 貪心法
class Solution:
def maxProfit(self, prices: List[int]) -> int:
return sum([prices[i+1]-prices[i] for i in range(len(prices)-1) if prices[i+1]-prices[i] > 0])
java:
// 動态規劃
public class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
if (len < 2) {
return 0;
}
int[] have = new int[len]; // 表示第i天持有股票所得最多現金
int[] no = new int[len]; // 表示第i天不持有股票所得最多現金
have[0] = -prices[0]; // 此時的持有股票就一定是買入股票了
no[0] = 0; // 不持有股票那麼現金就是0
for (int i = 1; i < len; i++) {
have[i] = Math.max(have[i-1], no[i-1] - prices[i]); // 唯一不同之處
no[i] = Math.max(no[i-1], prices[i] + have[i-1]);
}
return no[len - 1];
}
}
// 貪心法
class Solution {
public int maxProfit(int[] prices) {
int ans = 0;
int n = prices.length;
for (int i = 1; i < n; ++i) {
ans += Math.max(0, prices[i] - prices[i - 1]);
}
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的性能情況和常見字尾的含義 思維導圖整理