很久以前被第四題：Median of Two Sorted Arrays卡住了，而且discuss看不明白也沒耐心去看，導(dǎo)致信心受挫LeetCode一直沒去刷。感覺這是我一直以來的軟肋：缺乏勇氣。在我看到?？偷耐瑢W(xué)們都刷了不少LeetCode，而自己春招筆試6中3之后，騰訊一面手撕非常簡單的代碼都出錯（感覺這是除了項目不對口外掛掉的最大原因），感覺得面對現(xiàn)實了，現(xiàn)在，重新開始。
——2018/05/25
目前大概是自己先折騰，然后看討論區(qū)，高票答案都是有其精妙之處的。這篇博客就記錄題解的大致思路，包含了較為詳細(xì)注釋的代碼就放在github上了。
https://github.com/BewareMyPower/AtOffer/tree/master/leetcode
001 Two Sum
無序數(shù)組，找出和為target的兩個數(shù)，用hashmap存儲遍歷的數(shù)x及其下標(biāo)，若target-x在hashmap中，即找出一組解。
two_sum.cc
002 Add Two Numbers
用鏈表模擬大數(shù)加法的問題，用carry表示是否進(jìn)位，注意每次判斷2個鏈表對應(yīng)節(jié)點相加時，大于10時需要把carry置為1，小于10時把carry置為0，不要漏掉其中一個else，否則carry會被默認(rèn)為之前的值。
add_two_numbers.cc
003 Longest Substring Without Repeating Characters
雙指針法，記錄子串s[start..i)，start為起始位置，i為當(dāng)前位置，用哈希表記錄字符和字符最近一次出現(xiàn)的位置。這里由于字符是char，可以用vector<int> hash(256, -1);來取代unordered_map，當(dāng)然，前提是下標(biāo)用int表示不會溢出。
longest_substring_without_repeating_characters.cc
004 Median of Two Sorted Arrays
中位數(shù)的蛋疼之處在于元素數(shù)量是奇數(shù)還是偶數(shù)，這題有個非常巧妙的解決方法，使用割的概念，參考【分步詳解】兩個有序數(shù)組中的中位數(shù)和Top K問題。
median_of_two_sorted_arrays.cc
005 Longest Palindromic Substring
這題一開始我按照類似最大回文子序列的思路做了，然后求s和reverse(s)的最大公共子串長度，然后發(fā)現(xiàn)不對，因為需要s和reverse(s)的公共子串對應(yīng)位置相同。比如s1長度為6，s2為s1的轉(zhuǎn)置。則子串s1[0..2]對應(yīng)的是子串s2[3..5]，這樣才有意義。
后來發(fā)現(xiàn)這種做法把問題想復(fù)雜了，其實只需要依次從位置0~n-1構(gòu)造回文串的中心（比如abcxxcba的中心為xx），盡可能構(gòu)造足夠長的回文串即可。注意迭代終止條件加上一個優(yōu)化條件start + maxlen/2 < len。
longest_palindromic_substring.cc
006 ZigZag Conversion
讀懂題意后很簡單，之所以medium難度大概是考驗細(xì)心程度吧。
zigzag_conversion.cc
007 Reverse Integer
注意溢出判斷，在乘以10之前和INT_MAX/10比較即可。特殊情況，INT_MIN的絕對值比INT_MAX大1，因此無法通過負(fù)號運算轉(zhuǎn)換成正數(shù)。至于用long long來防止溢出，個人覺得沒意思。
reverse_integer.cc
008 String to Integer (atoi)
注意題意規(guī)定，這題用C直接操作字符指針寫起來更方便。正負(fù)號的判斷比較巧妙（參考源碼）。關(guān)鍵還是溢出的判斷，不同于007 Reverse Integer，這里要考慮乘以10之前和INT_MAX/10相等的情況，再進(jìn)一步通過正負(fù)號和最低位數(shù)字判斷。注意不要寫INT_MIN % 10這種代碼，因為C/C++的負(fù)數(shù)求余仍然是負(fù)數(shù)。
009 Palindrome Number
首先負(fù)數(shù)肯定是不行的，然后分位數(shù)為奇偶的情況討論（迭代收斂條件是分離出的第一個數(shù)<=第二個數(shù)）：
1221->{1221/10=122, 0*10+1=1}->{122/10=12, 1*10+2=12}->12==12,true!
121->{121/10=12, 0*10+1=1}->{12/10=1, 1*10+2=12}->1==12/10,true!
但是有陷阱，按這種算法，對10而言會被判斷為true，過程如下
10->{1,0}->{1,1}->1==1,true!
究其原因是0*10并未從1位數(shù)變成2位數(shù)。如果判斷個位為0時返回false，那么又有特殊情況0，所以這題雖然是easy難度，但是陷阱不少！
panlindrome_number.cc
010 Regular Expression Matching
劍指offer原題，但是書上給出的遞歸解法在LeetCode上效率低下，動態(tài)規(guī)劃的思路容易想到，但不容易想清楚，尤其是關(guān)于*匹配1次以上的情況下，隱含有s[i - 1] == p[j - 2]（其中p[j - 1]為模式串的新字符且為*），否則*必然只能匹配0次。
不知為什么這個DP思路想起來總有點不順，對我來說確實Hard難度。
regular_expression_matching.cc
011 Container With Most Water
看懂題意后還算簡單，初始寬度最大，然后慢慢縮小寬度，只能增大高度min(x[lo], x[hi])。嚴(yán)格的證明參考https://segmentfault.com/a/1190000008824222
container_with_most_water.cc
012 Integer to Roman
羅馬文字規(guī)則是按位數(shù)，0-9的表示和10~90的表示僅僅是把IVX換成了XLC。
| 數(shù)值 | 5k | 5k+1 | 5k+2 | 5k+3 | 5k+4 |
|---|---|---|---|---|---|
| 0~4 | I | II | III | IV | |
| 5~9 | V | VI | VII | VIII | IX |
前4列，第2行比第1行多了V，不過表達(dá)第5列稍微麻煩了點。簡單直接的做法是直接把這10個對應(yīng)關(guān)系記錄到表格中，然后從十進(jìn)制高位到低位，一個個查表。
integer_to_roman.cc
013 Roman to Integer
這題之所以easy難度，在于規(guī)律，若前一位小于后一位，則必然是IV、IX這種，否則直接加上該位表示的數(shù)就行。
roman_to_integer.cc
014 Longest Common Prefix
easy難度，注意邊界條件，在判斷第i個字符相等之前判斷i是否越界。
longest_common_prefix.cc
015 3Sum
思路一開始就是先定下1個元素，然后變成twoSum問題，但是這里要查找所有解，還要去重。所以關(guān)鍵是先排序，這樣首先避免了重復(fù)元素的查找，比如-2,-2,-1,-1,-1,0,1,1,1,1,2就只需要在每個區(qū)間內(nèi)查找。twoSum問題也和一般的twoSum問題求解方式不同，因為要找到所有解，所以用從最低和最高從外向內(nèi)逼近的的思想，如果用二分法反而復(fù)雜度更高。
3sum.cc
016 3Sum Closest
和上一題思路一致，不同在于，從外向內(nèi)逼近時，sum < target時lo++，sum > target時hi--，并且每次都比較abs(sum - target)是否小于當(dāng)前diff，若diff == 0則無需繼續(xù)查找。
PS：之前把nums[i] != nums[i - 1]寫成了nums[i] == nums[i - 1]導(dǎo)致測試用例只通過了113/125。
3sum_closest.cc
