Leetcode 探索之?dāng)?shù)組和字符串
[toc]
數(shù)據(jù)和字符串小結(jié)
- 數(shù)組可以簡單的分為一維數(shù)組和多維數(shù)組盆色。其中账千，字符串可以看作是字符組成的數(shù)組敦第。
- 數(shù)組中的元素在內(nèi)存中的分配是連續(xù)的苇经， 因此可以根據(jù)索引快速的讀取數(shù)組中的元素案淋，隨機訪問的時間復(fù)雜度為O(1), 插入和刪除操作由于需要移動其他的元素，時間復(fù)雜度為O(n)介陶。
- 對于查找數(shù)組中的元素腹备，遍歷的時間復(fù)雜度為O(n)，二分查找的時間復(fù)雜度為O(log n),因此當(dāng)題目中提到有序時考慮二分查找斤蔓。
做題小結(jié)
- 注意題目中恒定不變的量，例如數(shù)組的總和（見724）镀岛，利用這些信息可以方便的計算出某些需要的值弦牡。
- 字符串在某些語言中是不可變的友驮，如Java，Python驾锰，在另外一些語言中是可變的卸留，如C++。
如果你確實希望你的字符串是可變的椭豫，則可以使用
toCharArray將其轉(zhuǎn)換為字符數(shù)組耻瑟。
如果你經(jīng)常必須連接字符串，最好使用一些其他的數(shù)據(jù)結(jié)構(gòu)赏酥，如StringBuilder喳整。
- 雙指針技巧。情景一：兩邊迭代裸扶。情景二：快慢指針框都。
- 若涉及到操作次數(shù)盡量少，則考慮雙指針交換的問題呵晨。如移動0.（283）
KMP算法（28 實現(xiàn) strStr()）
主要分為構(gòu)造next數(shù)組和字符串匹配兩個步驟魏保。
題目索引
724尋找數(shù)組的中心索引（easy）
此題要求左邊的和與右邊的和，應(yīng)該注意到不變的量摸屠。即左邊的和加上索引元素再加上右邊的和的總和是固定不變的谓罗，因此可以先求出總和，從而在遍歷的過程中即可判斷左和與右和季二。
35搜索插入位置（easy）
有序檩咱，二分
56合并區(qū)間（medium）
注意到端點左值小于端點右值。
498對角線遍歷（medium）
二維矩陣主要是注意處理的順序及邊界值戒傻。
14最長公共前綴（easy）
橫向掃描税手，縱向掃描，分治需纳，二分芦倒。
5最長回文子串（medium）
掌握動態(tài)規(guī)劃和中心擴散。有一種專門的馬拉車算法處理此問題不翩，時間復(fù)雜度為O（n）兵扬，利用了動態(tài)規(guī)劃和中心擴散的思想。
151翻轉(zhuǎn)字符串里的單詞（medium）
涉及trim口蝠，split器钟，reverse，join等操作妙蔗。
344反轉(zhuǎn)字符串（easy）
561數(shù)組拆分 I（easy）
167兩數(shù)之和 II - 輸入有序數(shù)組（easy）
根據(jù)兩個指針的和移動指針傲霸。
27移除元素
485最大連續(xù)1的個數(shù)（easy）
209長度最小的子數(shù)組（medium）
滑動窗口
283移動零（easy)
操作次數(shù)最少，考慮交換。
