很久以前被第四題：Median of Two Sorted Arrays卡住了垛贤，而且discuss看不明白也沒耐心去看璧亚，導致信心受挫LeetCode一直沒去刷摸屠。感覺這是我一直以來的軟肋：缺乏勇氣帆吻。在我看到耪乖耍客的同學們都刷了不少LeetCode您访，而自己春招筆試6中3之后铅忿，騰訊一面手撕非常簡單的代碼都出錯（感覺這是除了項目不對口外掛掉的最大原因），感覺得面對現(xiàn)實了灵汪，現(xiàn)在檀训，重新開始柑潦。
——2018/05/25
目前大概是自己先折騰，然后看討論區(qū)峻凫，高票答案都是有其精妙之處的渗鬼。這篇博客就記錄題解的大致思路，包含了較為詳細注釋的代碼就放在github上了荧琼。
https://github.com/BewareMyPower/AtOffer/tree/master/leetcode
001 Two Sum
無序數(shù)組譬胎，找出和為target的兩個數(shù)，用hashmap存儲遍歷的數(shù)x及其下標命锄，若target-x在hashmap中堰乔，即找出一組解。
two_sum.cc
002 Add Two Numbers
用鏈表模擬大數(shù)加法的問題脐恩，用carry表示是否進位镐侯，注意每次判斷2個鏈表對應節(jié)點相加時，大于10時需要把carry置為1驶冒，小于10時把carry置為0苟翻，不要漏掉其中一個else，否則carry會被默認為之前的值骗污。
add_two_numbers.cc
003 Longest Substring Without Repeating Characters
雙指針法袜瞬，記錄子串s[start..i)，start為起始位置身堡，i為當前位置邓尤，用哈希表記錄字符和字符最近一次出現(xiàn)的位置。這里由于字符是char贴谎，可以用vector<int> hash(256, -1);來取代unordered_map汞扎，當然，前提是下標用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)的公共子串對應位置相同。比如s1長度為6玫坛，s2為s1的轉置结笨。則子串s1[0..2]對應的是子串s2[3..5]，這樣才有意義。
后來發(fā)現(xiàn)這種做法把問題想復雜了炕吸，其實只需要依次從位置0~n-1構造回文串的中心（比如abcxxcba的中心為xx）伐憾，盡可能構造足夠長的回文串即可。注意迭代終止條件加上一個優(yōu)化條件start + maxlen/2 < len赫模。
longest_palindromic_substring.cc
006 ZigZag Conversion
讀懂題意后很簡單树肃，之所以medium難度大概是考驗細心程度吧。
zigzag_conversion.cc
007 Reverse Integer
注意溢出判斷瀑罗，在乘以10之前和INT_MAX/10比較即可扫外。特殊情況，INT_MIN的絕對值比INT_MAX大1廓脆，因此無法通過負號運算轉換成正數(shù)筛谚。至于用long long來防止溢出，個人覺得沒意思停忿。
reverse_integer.cc
008 String to Integer (atoi)
注意題意規(guī)定驾讲，這題用C直接操作字符指針寫起來更方便。正負號的判斷比較巧妙（參考源碼）席赂。關鍵還是溢出的判斷吮铭，不同于007 Reverse Integer，這里要考慮乘以10之前和INT_MAX/10相等的情況颅停，再進一步通過正負號和最低位數(shù)字判斷谓晌。注意不要寫INT_MIN % 10這種代碼，因為C/C++的負數(shù)求余仍然是負數(shù)癞揉。
009 Palindrome Number
首先負數(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ī)劃的思路容易想到弃理，但不容易想清楚溃论，尤其是關于*匹配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])乎婿。嚴格的證明參考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，不過表達第5列稍微麻煩了點沐旨。簡單直接的做法是直接把這10個對應關系記錄到表格中森逮，然后從十進制高位到低位，一個個查表磁携。
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問題，但是這里要查找所有解啄寡，還要去重移怯。所以關鍵是先排序，這樣首先避免了重復元素的查找这难，比如-2,-2,-1,-1,-1,0,1,1,1,1,2就只需要在每個區(qū)間內查找舟误。twoSum問題也和一般的twoSum問題求解方式不同，因為要找到所有解姻乓，所以用從最低和最高從外向內逼近的的思想嵌溢，如果用二分法反而復雜度更高。
3sum.cc
016 3Sum Closest
和上一題思路一致蹋岩，不同在于赖草，從外向內逼近時，sum < target時lo++剪个，sum > target時hi--秧骑，并且每次都比較abs(sum - target)是否小于當前diff，若diff == 0則無需繼續(xù)查找。
PS：之前把nums[i] != nums[i - 1]寫成了nums[i] == nums[i - 1]導致測試用例只通過了113/125乎折。
3sum_closest.cc
