學習目標：

學習內容：

11. 盛最多水的容器

網址

給你 n 個非負整數 a1，a2，…，an，每個數代表坐標中的一個點 (i, ai) ，在坐標內畫 n 條垂直線，垂直線 i 的兩個端點分別為 (i, ai) 和 (i, 0) ，找出其中的兩條線，使得它們與 x 軸共同構成的容器可以容納最多的水，

說明：你不能傾斜容器，

思考：這道題是一道使用雙指標的題目，思路大概是先使用指標start指向下標0，另一個指標end指向下標n-1，用f(0,n-1)來表示兩下標下的容量，容量計算公式f（i，j）=min（ai,aj）*（j-i），下面就方便說明了，用數學運算式的方式是最簡明的方式，

首先，計算f(0,n-1)，將計算出的結果存入max當中，

然后，比較a[0]和a[n-1]，較小的那個數值的下標往中心靠攏，反復計算f(start，end)，并與max進行比較取最大值，直到當start=end時即可結束，

最后，輸出max就可以獲得最大容器，

這道題的編程思想是雙指標，數學思想是排除法，為啥是數值較小端移動呢？當時，我也思考過這個問題，但后面畫下影像就很容易可以理解，如果移動大端，就無法排除以原大端為下標最大容器的可能；但是移動最小端，保留了以原大端為下標最大容器的可能，另外，以最小端為下標的最大容器的可能就是當前狀態，此時高度最大為最小端數值，底部此時為最長，另外，如果兩端相等的時候，也是一個道理，如果以這兩端下標為基準的容器，此時已經是最大容器的可能，因此可以任意移動一端即可，

12. 整數轉羅馬數字

網址

羅馬數字包含以下七種字符： 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 的范圍內，

思考：用的是分治法+暴力解題思想，將其拆分成一塊一塊的來進行分別表示，我得吐槽下，其實我最后想的也沒有說明思想，就是按照羅馬數字表達方式分別表達，而且這個題目，如果不懂羅馬數字的完全做不出來呀！例如，300，200，700，800，2000等數字，如果不了解的話估計還得瞎猜！300=CCC，400=CD…

代碼寫的最簡單，最快速，同時也是最安全的辦法是寫成多if，或者switch形式，空間，時間復雜度均為O(1)，對人腦損害是∞，(?ω?)

然后，稍微加點代碼功底和思考的話，就是找到這里面的內在關系，然后采取字符集編碼的方式，因為400，40其實就是使用了{C,D},{C,X}兩個不同的字符集，這個感覺沒暴力法簡單，

13.羅馬數字轉整數

網址

羅馬數字包含以下七種字符: 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 的范圍內，

思考：這道題不就是將12題反過來考嗎，窮舉法可以完成這道題目，不過為了加快查找速度，會用到哈希表，下次一定寫一個有關各種語言哈希表的構造，下次一定，，，，，

14. 最長公共前綴

網址

撰寫一個函式來查找字串陣列中的最長公共前綴，

如果不存在公共前綴，回傳空字串 “”，

思考：看到這種題，我就會覺得C太痛苦了，換上痛苦面具，如果是python，可以直接用in，find來判斷是否存在在這個陣列當中，

我的思路是簡單的來說，假設存在s1,s2,s3…sn這n個字符陣列，那么先從f(s1，s2)找到二者之間的公共前綴，然后把公共前綴用一個空間進行存盤，設為b1，然后再和s3進行對比，即b2=f(b1,s3)，依次計算，直到bi是一個空陣列或者便利完sn就結束，

我這個思路的空間復雜度為O(1)，但時間復雜度過高，最糟糕的情況就是全部相同，所以公共前綴就是本身，這時的時間復雜度為O（mn），其中m是字符長度，n為字符陣列數量，

貌似，也沒用到python的in，find，好像也就是字串的字符匹配，

15. 三數之和

網址

給你一個包含 n 個整數的陣列 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？請你找出所有和為 0 且不重復的三元組，

注意：答案中不可以包含重復的三元組，

這就是第一道題的翻版嗎，二數之和就是神，看了下評論，大多是吐槽超時的，額，我是個紙上談兵的人，先思考再動手吧，這道題我覺得完全按照二數之和的思路來寫，

1.將陣列nums進行排序，排序也不用寫的太復雜，就算時間復雜度為O(n^2)，

2.建立HASH表，或者python中的字典，存盤的數值為陣列nums的負數，空間復雜度為O（n），時間復雜度為O(1)，

3.然后問題就變成了任取兩位，看第三位是否在哈希表的問題，其時間復雜度為O（n^2），

4.分析：簡單的看第3步，任取兩位是找第三位確實可行，雖然會出現重復問題，但可以通過除以3的方式來解決；另外一個問題是元素重復問題，雖然我很希望這是數學題中的集合，但顯然這種想法過于天真，重復元素在集合當中是存在的情況，這就有可能出現{-3，-3，6}的情況，最后，就是取值順序的選擇，因為有些取值是毫無意義的，比如三個正數的相加或者三個負數的相加，但加判斷感覺也太過于愚蠢，

5.優化：主要是對遍歷方法的優化，一方面可以解決答案重復的問題，另一方面可以減少不必要的計算，我思考的遍歷方法是，指標L，R開始分別指向左右兩端，固定指標L，指標R向左移動，

當s[L]+s[R]能夠在哈希表上找到時，停止移動，并記錄此時三個數值；如果存在兩數相等的情況，則再進行一次判斷，判斷陣列中是否存在兩個該字符，

當s[L]+S[R]的范圍不在（-s[R],-S[L]）,則直接break回圈，因為我作的假設就是，第三值必須在兩者之間，以保證結果的唯一性，

若S[R]存在相等的情況，只計算一次，下一次直接再指向下一個下標，

當下標L，R相等的時候，則停止回圈，但顯然在之前就已經停止了，

回圈結束后，L前進一步，R復位到最右端，再進行新一輪回圈，直到s[L]+S[R]的范圍不在（-s[R],-S[L]）時，終止外輪回圈，

因為使用了兩輪回圈，其時間復雜度為O(n^2), 查找哈希表的時間為O（1）,排序時間最快為O（nlogn），但這個沒必要，因此最終時間復雜度為O(n^2)，

事后發現，這道題沒必要使用hash，甚至可以說1.兩數之和也沒必要用hash，這里考察的都是對雙指標的使用，

16. 最接近的三數之和

網址
有完沒完呀，又是這種題目，嗚嗚嗚！！！！

給定一個包括 n 個整數的陣列 nums 和 一個目標值 target，找出 nums 中的三個整數，使得它們的和與 target 最接近，回傳這三個數的和，假定每組輸入只存在唯一答案，

思考：這道題因為是算接近值，而不是確定值，想用hash查找是辦不到的，只能老老實實的的來計算，如果暴力解決，則復雜度為O(n^3)，這顯然會超時的，

突然覺得前面的算式不需要用哈希了，使用hash還需要考慮各種問題，
首先，對陣列進行排序，時間復雜度為O(nlogn)，

設定兩個指標L和R，進行一個i從0-length-2的回圈，L的初始值指向i+1，R的初始值指向最右端，

用sum來記錄三值的大小，在這里sum=s[i]+s[L]+s[R]，然后得到sum和target差值的絕對值，

如果這個差值絕對值小于原來的sum，則更新最接近三數，當sum值大于target時，則sum值為了減少要移動R左移；同理，小于時則時L右移，直到L=R時，這時移動n-i次，

接著按照這樣的道理進行n-2次回圈，最侄訓得最接近的三數，

這個演算法的數學證明可以參照11.承最多的水，使用的是數學排除法的思想，

17. 電話號碼的字母組合

網址
給定一個僅包含數字 2-9 的字串，回傳所有它能表示的字母組合，答案可以按 任意順序 回傳，

給出數字到字母的映射如下（與電話按鍵相同），注意 1 不對應任何字母，

思考：這題考察的是回溯法，題目是常考的題目，我下次一定要總結一下，因為時間復雜度是指數級，所以很容易超時，沒時間，我還有其他事要做，以后再自己總結下該題吧，