先從數(shù)組系類開(kāi)始吧(1-20)
1.two sum 2017.9.20-2017.9.21
two sum
思索:第一想法就是用排序毛嫉，二分或者set來(lái)做糙俗，復(fù)雜度O(nlgn).但后來(lái)發(fā)現(xiàn)題目中沒(méi)有說(shuō)數(shù)組中沒(méi)有存在重復(fù)數(shù)字，target也可以用兩個(gè)相同的數(shù)組成，由于本題需要統(tǒng)計(jì)原來(lái)數(shù)組下標(biāo)伐割，所以用multimap來(lái)寫休偶。
類似multiset/set换途，map/multimap之類的容器還是比手寫的排序快一點(diǎn)的咬荷，雖然可能沒(méi)有手寫的其他數(shù)據(jù)結(jié)構(gòu)快，但也夠用迷捧。
常見(jiàn)用法:http://blog.csdn.net/cws1214/article/details/8211881
代碼：https://pastebin.com/m6HceqCS
第二種想法:可以使用雙指針的方法织咧，為了記錄下標(biāo)和方便排序，可以使用stl中的pair來(lái)存儲(chǔ)(pair排序先按first排党涕，相同再按second排),排序后烦感，使用雙指針的算法，從兩邊向中間靠膛堤。復(fù)雜度O(n).
代碼：https://pastebin.com/kHugDChb
2.Median of Two Sorted Arrays 2017.9.21-
Median of Two Sorted Arrays
兩個(gè)排好序的數(shù)組找中位數(shù)手趣，復(fù)雜度要求O(lg(m+n))
3.Container With Most Water 2017.9.21-9.21
Container With Most Water
面積取決于兩塊板之間的長(zhǎng)度和兩塊板中的小的那一塊，現(xiàn)在板子的位置固定了肥荔，暴力的做法绿渣，O(n^2)，但也存在更快的O(n)的做法燕耿。
示例
腦補(bǔ)一下中符，1和5的邊作比較，5比1小誉帅，那么可以直接放棄5邊與其他邊的組合淀散，無(wú)論怎么組右莱，都不可能大于1和5的組合，同理档插，當(dāng)1和4比較的時(shí)候慢蜓，放棄1邊繼續(xù)比較，因?yàn)殚L(zhǎng)度始終在減小郭膛，這個(gè)剪枝是合理存在的晨抡。我們可以在O(n)的復(fù)雜度下，計(jì)算出最大面積则剃≡胖可以用雙指針的方法。
那么如果兩個(gè)邊相等呢棍现？該怎么辦调煎？
答案當(dāng)然是都放棄了。己肮。汛蝙。
代碼:https://pastebin.com/pEtKuZsN
