所謂A(Algorithm)R(Review)T(Tips)S(Share):
. 每周至少做一個(gè) leetcode 的算法題
. 閱讀并點(diǎn)評(píng)至少一篇英文技術(shù)文章
. 學(xué)習(xí)至少一個(gè)技術(shù)技巧
. 分享一篇有觀點(diǎn)和思考的技術(shù)文章
3 week
Algorithm 算法
[121] 買賣股票的最佳時(shí)機(jī)
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/description/
Tags: algorithms amazon bloomberg facebook microsoft uber array dynamic-programming
Langs: c cpp csharp golang java javascript kotlin php python python3 ruby rust scala swift
* algorithms
* Easy (47.86%)
* Total Accepted: 44.7K
* Total Submissions: 90.3K
* Testcase Example: '[7,1,5,3,6,4]'
給定一個(gè)數(shù)組纳猫，它的第 i 個(gè)元素是一支給定股票第 i 天的價(jià)格但两。
如果你最多只允許完成一筆交易（即買入和賣出一支股票），設(shè)計(jì)一個(gè)算法來(lái)計(jì)算你所能獲取的最大利潤(rùn)。
注意你不能在買入股票前賣出股票。
示例 1:
輸入: [7,1,5,3,6,4]
輸出: 5
解釋: 在第 2 天（股票價(jià)格 = 1）的時(shí)候買入，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣出，最大利潤(rùn) = 6-1 = 5 。
注意利潤(rùn)不能是 7-1 = 6, 因?yàn)橘u出價(jià)格需要大于買入價(jià)格宏邮。
示例 2:
輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒(méi)有交易完成, 所以最大利潤(rùn)為 0。
# 動(dòng)態(tài)規(guī)劃背后的基本思想非常簡(jiǎn)單缸血。大致上蜜氨，若要解一個(gè)給定問(wèn)題，我們需要解其不同部分（即子問(wèn)題）
# 再根據(jù)子問(wèn)題的解以得出原問(wèn)題的解捎泻。
# 通常許多子問(wèn)題非常相似飒炎，為此動(dòng)態(tài)規(guī)劃法試圖僅僅解決每個(gè)子問(wèn)題一次，從而減少計(jì)算量：
# 一旦某個(gè)給定子問(wèn)題的解已經(jīng)算出笆豁，則將其記憶化存儲(chǔ)郎汪，以便下次需要同一個(gè)子問(wèn)題解之時(shí)直接查表赤赊。
# 這種做法在重復(fù)子問(wèn)題的數(shù)目關(guān)于輸入的規(guī)模呈指數(shù)增長(zhǎng)時(shí)特別有用。
# 動(dòng)態(tài)規(guī)劃算法的核心就是記住已經(jīng)解決過(guò)的子問(wèn)題的解
# 基本思路是對(duì)任意字符串煞赢，如果頭和尾相同抛计，那么它的最長(zhǎng)回文子串一定是去頭去尾之后的部分的最長(zhǎng)回文子串加上頭和尾。
# 如果頭和尾不同照筑，那么它的最長(zhǎng)回文子串是去頭的部分的最長(zhǎng)回文子串和去尾的部分的最長(zhǎng)回文子串的較長(zhǎng)的那一個(gè)吹截。
#根據(jù)回文的特性，一個(gè)大回文按比例縮小后的字符串也必定是回文凝危，比如ABCCBA波俄，那BCCB肯定也是回文。
#所以我們可以根據(jù)動(dòng)態(tài)規(guī)劃的兩個(gè)特點(diǎn)：
#（1）把大問(wèn)題拆解為小問(wèn)題
#（2）重復(fù)利用之前的計(jì)算結(jié)果
#這道題媒抠。如何劃分小問(wèn)題弟断，我們可以先把所有長(zhǎng)度最短為1的子字符串計(jì)算出來(lái)咏花，根據(jù)起始位置從左向右趴生，這些必定是回文。
#然后計(jì)算所有長(zhǎng)度為2的子字符串昏翰，再根據(jù)起始位置從左向右苍匆。到長(zhǎng)度為3的時(shí)候，我們就可以利用上次的計(jì)算結(jié)果：
#如果中心對(duì)稱的短字符串不是回文棚菊，那長(zhǎng)字符串也不是浸踩，如果短字符串是回文，那就要看長(zhǎng)字符串兩頭是否一樣统求。
#這樣检碗，一直到長(zhǎng)度最大的子字符串，我們就把整個(gè)字符串集窮舉完了码邻。
Review 英文技術(shù)文章
Go Modules 的使用方法
https://blog.golang.org/using-go-modules
https://studygolang.com/articles/19334
Tip 技術(shù)點(diǎn)
redis中的跳表
Share 分享文章
https://juejin.im/post/5cd945d6e51d453d022cb65f?utm_source=gold_browser_extension
https://juejin.im/post/5cd81a2ef265da037516bfec?utm_source=gold_browser_extension
