引子

為什么我要刷leetcode？換作業？不是！那是？玩！巴菲特的雙目標清單系統，基本方法是列兩個清單，一個是職業生涯最重要的目標（不超過5個），另一個是比較重要的目標，對于比較重要的目標，要像躲避瘟疫一樣的去躲避它們，不投入任何的時間和精力，把這些資源花在最重要的目標上，這個雙目標清單系統以方法的形式說明三件事：

1，目標很重要

2，專注很有力量

3，比起「有所為」、「有所不為」更為關鍵

所以當我想做一件事情，但是想不到這件事情能給我帶來實在的收益時，我就定義為「玩」，就像看電影、喝奶茶一樣，我只是去做這件事，在有閑暇的時候占用一些時間，并不占用精力， 我作業十二年，技術一直不好，雖然對一部分人來說還算可以，在美團作業、百余項技術發明專利、kubernetes原始碼貢獻者，但是即使在名聲每況愈下的母校同屆同專業畢業生中，也算是菜的，原來我之前一直定義為沒有天賦，在畢業的第一家公司，被作為技術招進來，但是因為語言學的太好做的是翻譯的作業，一年過日語1級，參加任何和日語相關的比賽，只要我參加，第一名肯定是我的，沒別人什么事兒，別人說這是天賦，我那時候沒想過這個問題，只是不由自主的把精力都花在了這上面，而對于作業，只是完成任務，對于技術，只是用到才去學，很久之后我才說服自己：我的沒有天賦只是沒投入精力而已，在一件事上有多少天賦取決于在這上面成功的渴望有多強烈，所以現在，我有了一個重心：做好作業中需要的技術，其他想做的事情，就不要投入什么精力，保持專注，實際上刷leetcode對我是有好處的，

1，我不去面試，但是我有可能面試別人，別人在寫演算法的時候，我需要有思考才不至于用來面試別人的時間對自己沒有成長，也是對面試者的負責，

2，刷leetcode，我用的是go語言，作業中暫時還沒用，但是我是做容器的，遲早是要用的，提前熟悉起來，

3，算是對之前包括大學四年的一個回顧總結，將之前的一些知識體系化

以下是我刷了14道平均難度在簡單級別的演算法之后，做的梳理，

結果

leetcode有些測驗用例不全，比如下面「最大子序和」一題中，測驗用例就沒包含陣列中陣列全為負數的情況，這個不重要，重要的是玩也要玩的有方法論指導，做個總結復盤，能做到這一點，就算自己沒考上211、985，也能影響下一代，在拼娃的競爭中獲得成功，
先看梳理一下整體考察點，因為刷題少，只是做出一個最小骨架，后續如果有時間再做題，直接加節點即可，算是一個MVP（最小可行產品，詳見《精益創業》），

資料結構就不提了，從下面具體事例中可以看到雙指標的題目占比大，原因是演算法主要解決時空最優的問題，而雙指標在基本不增加空間開銷的基礎上在很多情況下可以將時間復雜度減少到1/n，
下面展示一下最大公約數演算法的效果：

程序

1，兩數之和

題目大意

給定一個目標值，要在一個給定陣列中找到兩個數，它們的和為目標值，

解題思路

使用map的資料結構，遍歷程序中找到從map中取出值為目標值減去當前值的數，

詳情可參考：

https://leetcode-cn.com/problems/two-sum/solution/liang-shu-zhi-he-gojie-fa-by-xie-xiao-jing/

知識點

資料結構->哈希表

2，整數回文數

題目大意

判斷一個整數是回文數是指從左到右和從右到左讀到的內容是一致的

解題思路

將整數轉為陣列，利用陣列，將整數分為一個byte陣列，遍歷陣列的一半，從左開始的和從右開始的相對位置一樣的數字都應該是一樣就是回文數，否則就不是回文數，

詳情可參考：

https://leetcode-cn.com/problems/palindrome-number/solution/hui-wen-shu-gojie-fa-by-xie-xiao-jing/

知識點

資料結構->陣列

3，羅馬數字轉為整數

題目大意

因為了解羅馬數字也是一種知識，所以我把完整的題目寫下來，

羅馬數字包含以下七種字符: I， V， X， L，C，D 和 M，

字符          數值

I             1

V             5

X             10

L             50

C             100

D             500

M             1000

例如， 羅馬數字 2 寫做 II ，即為兩個并列的 1，12 寫做 XII ，即為 X + II ，27 寫做  XXVII, 即為 XX + V + II ，

通常情況下，羅馬數字中小的數字在大的數字的右邊，但也存在特例，例如 4 不寫做 IIII，而是 IV，數字 1 在數字 5 的左邊，所表示的數等于大數 5 減小數 1 得到的數值 4 ，同樣地，數字 9 表示為 IX，這個特殊的規則只適用于以下六種情況：

I 可以放在 V (5) 和 X (10) 的左邊，來表示 4 和 9，

X 可以放在 L (50) 和 C (100) 的左邊，來表示 40 和 90， 

C 可以放在 D (500) 和 M (1000) 的左邊，來表示 400 和 900，

給定一個羅馬數字，將其轉換成整數，輸入確保在 1 到 3999 的范圍內，

解題思路

將所有字母的組合存入哈希表，遍歷時先判斷是否是雙字母的，不是再判斷是否是單字母的，

詳情可參考：

https://leetcode-cn.com/problems/roman-to-integer/solution/luo-ma-shu-zi-zhuan-zheng-shu-gojie-fa-by-xie-xiao/

知識點

資料結構->哈希表

4，最后一個單詞的長度

題目大意

給定一個僅包含大小寫字母和空格 ' ' 的字串，回傳其最后一個單詞的長度，

解題思路

這道題對于經常寫業務代碼的同學來說可能很簡單，因為看懂題了，運用類別庫就做出來了，這道題可以歸結為字串陣列的使用，

詳情可參考：

https://leetcode-cn.com/problems/length-of-last-word/solution/zui-hou-yi-ge-dan-ci-de-chang-du-gojie-fa-by-xie-x/

知識點

資料結構->陣列

5，報數

題目大意

報數序列是一個整數序列，按照其中的整數的順序進行報數，得到下一個數，

解題思路

使用兩個陣列，一個存放當前的整數序列中所有的數值，另一個存放每個字符出現的個數，列印的時候列印一個陣列，再列印對應的個數就得到一個新數，如果還有下一個，重復此程序，

詳情可參考：

https://leetcode-cn.com/problems/count-and-say/solution/bao-shu-gojie-fa-by-xie-xiao-jing/

知識點

資料結構->陣列

6，整數轉羅馬數字

題目大意

與題目「羅馬數字轉為整數」相反，給定一個整數，將其轉為羅馬數字，輸入確保在 1 到 3999 的范圍內，

解題思路

貪心演算法，每次選擇區域最優

詳情可參考：

https://leetcode-cn.com/problems/integer-to-roman/solution/zheng-shu-zhuan-luo-ma-shu-zi-goliang-chong-jie-fa/

知識點

基礎演算法->貪心演算法

7，最長公共前綴

題目大意

撰寫一個函式來查找字串陣列中的最長公共前綴，如果不存在公共前綴，回傳空字串 “"

解題思路

可以將這個字串陣列轉成單個字符的二維陣列遍歷，也可以采用分治法，直到分解成兩個字串比較，

詳情可參考：

https://leetcode-cn.com/problems/longest-common-prefix/solution/zui-chang-gong-gong-qian-zhui-goliang-chong-jie-fa/

知識點

資料結構->二維陣列

基礎演算法->分治法

8，字串的最大公因子

題目大意

給定兩個字串A和B，求最大公因子

解題思路

最大公因子存在的充要條件A+B=B+A，判斷存在公因子，則公因子的長度不大于（A長度-B長度絕對值，為新的A）與B長度的最小值，回圈直到A的長度等于B的長度，

知識點

基礎演算法->最大公約數演算法

詳情可參考：

https://leetcode-cn.com/problems/greatest-common-divisor-of-strings/solution/zi-fu-chuan-de-zui-da-gong-yin-zi-gojie-fa-by-xie-/

9，洗掉排序陣列中的重復項

題目大意

給定一個排序陣列，你需要在原地洗掉重復出現的元素，使得每個元素只出現一次，回傳移除后陣列的新長度，

解題思路

放置兩個指標 slow和 fast，其中slow是慢指標，而fast是快指標，只要 nums[slow]等于nums[fast]，就洗掉此元素，否則讓slow=fast繼續遍歷，

詳情可參考：

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/solution/shan-chu-pai-xu-shu-zu-zhong-de-zhong-fu-xiang-goj/

知識點

基礎演算法->雙指標法

10，壓縮字串

題目大意

給定一組字符，使用原地演算法將其壓縮，壓縮后的長度必須始終小于或等于原陣列長度，陣列的每個元素應該是長度為1 的字符（不是 int 整數型別），在完成原地修改輸入陣列后，回傳陣列的新長度，

解題思路

設立一個寫指標，初始為第1個字符，一個讀指標，初始為第2個字符，讀指標讀到與寫指標相同的數則直接加1，不同的數，則它們的距離就是這個寫指標對應字符出現的次數，然后讓寫指標等于讀指標重復此程序到結束，

詳情可參考：

https://leetcode-cn.com/problems/string-compression/solution/ya-suo-zi-fu-chuan-gojie-fa-by-xie-xiao-jing/

知識點

基礎演算法->雙指標法

11，移除元素

題目大意

給定一個陣列 nums 和一個值 val，你需要原地移除所有數值等于 val 的元素，回傳移除后陣列的新長度，

解題思路

使用一個指標A遍歷，另一個指標指向不重復的新陣列位置B（這個新陣列是邏輯上的，可以使用原地演算法覆寫原陣列），遍歷到一個不為val的元素，則B加1.

詳情可參考：
https://leetcode-cn.com/problems/remove-element/solution/yi-chu-yuan-su-goliang-chong-jie-fa-by-xie-xiao-ji/

知識點

基礎演算法->雙指標

12，合并兩個有序陣列

題目大意

給定兩個有序整數陣列 nums1 和 nums2，將 nums2 合并到 nums1 中，使得 num1 成為一個有序陣列，其中nums1長度是num1有效資料長度加上nums2的和，

解題思路

保存兩個指標，一個是遍歷nums1的指標，一個是遍歷nums2的指標，從后向前遍歷大小，從后面開始的原因是可以使用原地演算法，直接將最后面的數直接放到nums1的后面，同時已經放好的陣列不需要再次移動，

詳情可參考：

https://leetcode-cn.com/problems/merge-sorted-array/solution/he-bing-liang-ge-you-xu-shu-zu-gojie-fa-by-xie-xia/

知識點

基礎演算法->雙指標

13，最大子序和

題目大意

給定一個整數陣列，找到一個具有最大和的連續子陣列（子陣列最少包含一個元素），回傳其最大和，

解題思路

保存兩個數，一個是當前為止的最大和A，一個是從這個最大和的子陣列的開始位置到最大和的連續子陣列B，遍歷陣列，如果B加上當前值的和C大于A，則A等于C，如果C小于0，則B等于0重新開始計數，否則B等于C，實際上是動態規劃的思想，

詳情可參考：

https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-gojie-fa-by-xie-xiao-jing/

知識點

基礎演算法->動態規劃

14，買股票的最佳時機

題目大意

給定一個陣列，它的第 i 個元素是一支給定股票第 i 天的價格，

如果你最多只允許完成一筆交易（即買入和賣出一支股票），設計一個演算法來計算你所能獲取的最大利潤，

解題思路

買賣股票的最佳時機抽象一下就是找到一個子序列尾和首的差最大，保存兩個數，一個是當前為止的尾和首的差最大A，另外是計算這個最佳值的開始位置，如果當前位置的值減去最佳值開始位置比A還要佳，則替換A，否則如果<0，則當前位置為最低谷，也是動態規劃的思想，

詳情可參考：

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/mai-mai-gu-piao-de-zui-jia-shi-ji-gojie-fa-by-xie-/

知識點

基礎演算法->動態規劃

總結

    我作業十二年了都在刷leetcode，最重要的原因是于想要理解，理解周圍的人：年輕人、領導、同事都一樣，設身處地做別人做的事情，理解別人的想法、思路，更好的溝通，

標籤：Go

上一篇：Go中http超時問題的排查

下一篇：GO基礎之流程控制陳述句