很多剛開(kāi)始刷?？偷耐瑢W(xué)都會(huì)卡在“集合類(lèi)”和“Map”這兩節(jié)說(shuō)實(shí)話(huà)這不怪大家。前面學(xué)的變量、循環(huán)、數(shù)組都是“單打獨(dú)斗”到了集合和Map這兒突然冒出來(lái)一堆接口、實(shí)現(xiàn)類(lèi)、方法名光是ArrayList和LinkedList怎么選就夠糾結(jié)半天。這篇文章我就以帶刷第42、43題為例把集合類(lèi)和Map的考點(diǎn)、底層邏輯、常用方法一次講透讓零基礎(chǔ)的同學(xué)也能直接上手寫(xiě)題。如果你是那種“數(shù)組還沒(méi)玩明白就被扔到HashMap源碼里”的初學(xué)者或者你正在刷?？偷腏ava入門(mén)題看到“集合類(lèi)”“Map”這兩個(gè)標(biāo)題就頭大那這篇文章就是給你準(zhǔn)備的。我會(huì)用最直白的話(huà)拆解底層原理再帶著你一行一行把題目代碼寫(xiě)出來(lái)。文章里所有的代碼都是我按實(shí)際刷題場(chǎng)景寫(xiě)的調(diào)試過(guò)、能跑你直接跟著敲就行。1. 為什么集合類(lèi)和Map是刷題路上的分水嶺數(shù)組能存一組數(shù)但數(shù)組的長(zhǎng)度一旦確定就不能變了。日常寫(xiě)代碼的時(shí)候你根本不知道用戶(hù)會(huì)輸入多少條數(shù)據(jù)這時(shí)候就必須用集合。集合類(lèi)的出現(xiàn)本質(zhì)上就是解決“數(shù)量不確定”和“操作復(fù)雜”這兩個(gè)痛點(diǎn)。而Map解決的是另一個(gè)問(wèn)題——“按名字找東西”。數(shù)組按下標(biāo)找Map按key找這兩種查找模型幾乎是所有后續(xù)編程的基石。?？桶鸭项?lèi)和Map放在第42、43題位置非常講究。前面的題讓你用數(shù)組、循環(huán)、字符串把語(yǔ)法基礎(chǔ)打牢到這里就開(kāi)始考驗(yàn)?zāi)恪坝檬裁慈萜餮b數(shù)據(jù)”的抽象能力。這兩題過(guò)了你才能無(wú)障礙地去看后面各種算法題因?yàn)樗惴}里幾乎無(wú)處不在地用集合和Map做輔助。所以這兩題刷明白意義不只是過(guò)了兩道題而是你從“寫(xiě)代碼”跨越到“設(shè)計(jì)代碼”的起點(diǎn)。另外這兩題也特別適合用來(lái)熟悉IDE的自動(dòng)補(bǔ)全和API查找。我自己帶學(xué)生的時(shí)候發(fā)現(xiàn)很多人寫(xiě)集合類(lèi)代碼方法名全靠背背不住就卡住。實(shí)際上集合類(lèi)的方法名非常規(guī)律比如“添加”是add“刪除”是remove“判斷有沒(méi)有”是contains“拿長(zhǎng)度”是size你只要記住這一套規(guī)律再用IDE補(bǔ)全一提示基本就能順下來(lái)。刷這兩題的價(jià)值就是把這一套規(guī)律刻進(jìn)肌肉記憶。提示牛客這類(lèi)平臺(tái)刷題時(shí)環(huán)境不帶IDE自動(dòng)補(bǔ)全有的帶有的不帶所以方法名最好在本地IDE里練熟再去平臺(tái)提交。2. 動(dòng)手寫(xiě)題之前先把集合框架的地圖鋪開(kāi)2.1 List家族ArrayList和LinkedList別選錯(cuò)List是一個(gè)接口它的語(yǔ)義是“有序、可重復(fù)”的序列。所謂有序就是元素按插入順序排列你放進(jìn)a、b、c取出來(lái)就是a、b、c?？芍貜?fù)就是說(shuō)同一個(gè)元素可以出現(xiàn)兩次比如存兩個(gè)“hello”沒(méi)問(wèn)題。List最常見(jiàn)的兩個(gè)實(shí)現(xiàn)是ArrayList和LinkedList。ArrayList底層是數(shù)組查詢(xún)快、改也快但是中間插入和刪除慢因?yàn)橐嵋坪竺娴脑?。LinkedList底層是雙向鏈表兩頭操作特別快但中間查找慢。刷入門(mén)題的時(shí)候你只需要記住一個(gè)默認(rèn)選擇拿不準(zhǔn)就用ArrayList因?yàn)榇蟛糠謭?chǎng)景下數(shù)組搬移的開(kāi)銷(xiāo)可以忽略而鏈表每次get某個(gè)下標(biāo)都要從頭遍歷寫(xiě)起來(lái)還容易迷糊。import java.util.ArrayList; import java.util.List; public class ListDemo { public static void main(String[] args) { ListString list new ArrayList(); list.add(Java); // 尾部添加 list.add(集合); list.add(Map); System.out.println(list.size()); // 3 System.out.println(list.get(0)); // Java數(shù)組按下標(biāo)拿快 list.remove(1); // 刪除下標(biāo)1的“集合” System.out.println(list.contains(Map)); // true遍歷找 } }這段代碼里的size()、get()、remove()、contains()是你刷題時(shí)最常用的方法。注意list.remove(1)和list.remove(Java)不一樣一個(gè)是按下標(biāo)刪一個(gè)是按元素刪。初學(xué)者最容易在這里踩坑后面我會(huì)專(zhuān)門(mén)說(shuō)。2.2 Set家族去重這件事底層是哈希Set的語(yǔ)義只有一句話(huà)不允許重復(fù)元素。為什么不允許重復(fù)因?yàn)樗讓泳褪荕ap你沒(méi)看錯(cuò)HashSet本質(zhì)就是一個(gè)HashMap的殼元素被放進(jìn)Set時(shí)是被當(dāng)作Map的key存進(jìn)去的。Map的key天然不能重復(fù)所以Set也就不能重復(fù)了。判斷重復(fù)的標(biāo)準(zhǔn)是hashCode和equals先算hashCode定位到桶如果桶里有元素再用equals逐個(gè)比較。你如果自己定義了一個(gè)類(lèi)放進(jìn)HashSet卻不重寫(xiě)hashCode和equals那兩個(gè)“內(nèi)容一樣”的對(duì)象也會(huì)被當(dāng)成不同元素。這是后面SE階段的重難點(diǎn)刷?？皖}階段通常用不到自定義對(duì)象但原理你得知道不然看到“HashSet為何去重失敗”的討論會(huì)一頭霧水。Set有三個(gè)常用實(shí)現(xiàn)HashSet無(wú)序去重最快LinkedHashSet按插入順序去重TreeSet按自然順序或比較器排序去重刷題場(chǎng)景里如果你要“去重排序”一個(gè)TreeSet直接搞定如果你只想去重不在意順序HashSet就夠了。2.3 Map的核心邏輯key-value的查找表Map不是Collection體系的一員它有自己獨(dú)立的接口體系。Collection存單個(gè)元素Map存的是“鍵值對(duì)”。你可以把Map想成一本字典key是詞條value是釋義。查的時(shí)候你給一個(gè)key它直接告訴你value是多少。這個(gè)查找過(guò)程如果底層是HashMap那平均就是O(1)級(jí)別的非?？臁ashMap的底層是數(shù)組鏈表紅黑樹(shù)。put一個(gè)鍵值對(duì)時(shí)先算key的hashCode再經(jīng)過(guò)擾動(dòng)函數(shù)散列到數(shù)組下標(biāo)該位置為空就直接放不為空就掛在鏈表后面鏈表太長(zhǎng)超過(guò)8且數(shù)組長(zhǎng)度夠超過(guò)64就轉(zhuǎn)成紅黑樹(shù)。get的時(shí)候同樣算hash找到桶然后在鏈表或紅黑樹(shù)里用equals找key。刷基礎(chǔ)題階段你不需要把紅黑樹(shù)背下來(lái)但你必須理解一個(gè)核心點(diǎn)Map是拿key來(lái)找value。所以如果你的需求是“統(tǒng)計(jì)每個(gè)字符出現(xiàn)了幾次”字符是key、次數(shù)是value這個(gè)模型瞬間就清晰了。如果你要“記錄學(xué)號(hào)和姓名”學(xué)號(hào)是key、姓名是value也是一樣的道理。Map常用的實(shí)現(xiàn)有HashMap、LinkedHashMap、TreeMap、Hashtable。刷題最常用的是HashMap默認(rèn)無(wú)序、查得快需要按key排序時(shí)用TreeMap需要按插入順序遍歷時(shí)用LinkedHashMap。Hashtable是老古董線(xiàn)程安全但是慢而且不允許null鍵null值不用管它。3. 第42題手把手拆解集合類(lèi)操作與去重排序3.1 題面考點(diǎn)分析我?guī)⒌臅r(shí)候拿到的題目版本大概是這樣的從鍵盤(pán)輸入若干個(gè)整數(shù)以某個(gè)結(jié)束符結(jié)束要求用集合類(lèi)完成“去重 升序輸出”。這道題的核心考點(diǎn)有三個(gè)集合類(lèi)的選擇、輸入處理、集合遍歷輸出。很多初學(xué)者一上來(lái)就數(shù)組硬剛先數(shù)有幾個(gè)數(shù)再建數(shù)組再去重再排序……可以是可以但代碼量非常大而且容易出錯(cuò)。這道題就是逼你轉(zhuǎn)換思維容器不是只能選數(shù)組Set本身就能去重TreeSet順便還能排序你只需要把元素往里面一丟所有臟活累活它都替你干了。這就是刷題的意義——見(jiàn)識(shí)到工具本身的力量。3.2 我寫(xiě)的參考代碼import java.util.Scanner; import java.util.TreeSet; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); TreeSetInteger set new TreeSet(); while (sc.hasNextInt()) { int num sc.nextInt(); set.add(num); } for (Integer val : set) { System.out.print(val ); } sc.close(); } }你沒(méi)看錯(cuò)核心代碼就這么幾行。樹(shù)結(jié)構(gòu)幫你排序Set語(yǔ)義幫你去重遍歷輸出就完事了。讀數(shù)據(jù)用的是hasNextInt()也就是“只要還有整數(shù)就一直讀”這不依賴(lài)你事先知道有多少個(gè)數(shù)也不依賴(lài)結(jié)束符自動(dòng)化判題程序會(huì)自動(dòng)幫你模擬輸入結(jié)束。3.3 關(guān)鍵方法逐行詳解先說(shuō)TreeSet的add()方法。前面說(shuō)了TreeSet底層是TreeMap而TreeMap底層是一棵紅黑樹(shù)。每次add時(shí)元素會(huì)被插入到樹(shù)中合適的位置樹(shù)的中序遍歷本身就是有序的。所以add完所有元素后你直接用foreach遍歷拿到的就是升序序列。TreeSet內(nèi)部會(huì)自動(dòng)調(diào)用元素的compareTo方法比較大小Integer已經(jīng)實(shí)現(xiàn)了這個(gè)接口所以不用你手動(dòng)寫(xiě)比較器。hasNextInt()是Scanner里一個(gè)非常實(shí)用的方法。它的工作方式是先阻塞等待輸入有數(shù)據(jù)時(shí)返回true沒(méi)數(shù)據(jù)時(shí)返回false。在?？瓦@種自動(dòng)判題環(huán)境里輸入管道關(guān)閉后hasNextInt()會(huì)自動(dòng)返回false循環(huán)自動(dòng)退出不需要你寫(xiě)什么“輸入0結(jié)束”之類(lèi)的邏輯。這個(gè)細(xì)節(jié)很多新手不知道以為循環(huán)會(huì)卡住實(shí)際不會(huì)。foreach循環(huán)本質(zhì)上是編譯器幫你調(diào)用了迭代器。TreeSet的迭代器按照紅黑樹(shù)的中序遍歷順序返回元素所以輸出天然有序。這里要注意一個(gè)細(xì)節(jié)foreach里你不能remove元素否則會(huì)拋ConcurrentModificationException。如果你要在遍歷時(shí)刪除元素得用迭代器自己的remove方法。不過(guò)這種去重排序場(chǎng)景用不到刪除知道有這么回事就行。3.4 新手最容易寫(xiě)錯(cuò)的兩個(gè)地方第一個(gè)坑是類(lèi)型寫(xiě)錯(cuò)。有人寫(xiě)TreeSet 這是語(yǔ)法錯(cuò)誤。Java泛型不支持基本類(lèi)型必須用包裝類(lèi)Integer。int和Integer之間會(huì)自動(dòng)裝箱拆箱add(num)里num是int自動(dòng)變成Integer對(duì)象取出來(lái)的時(shí)候foreach里的val是Integer還能直接參與運(yùn)算。這個(gè)過(guò)程看起來(lái)“透明”但你要知道背后發(fā)生了裝箱拆箱不然遇到null時(shí)你根本不知道為什么會(huì)空指針。第二個(gè)坑是錯(cuò)用HashSet。HashSet也能去重但它是無(wú)序的如果你直接用HashSet存完就輸出順序是亂的。加上排序還得再Collections.sort(new ArrayList(set))白折騰一圈。所以遇到“去重排序”這種題腦子里的第一反應(yīng)應(yīng)該是TreeSet而不是HashSet。這個(gè)直覺(jué)很重要刷題多了你會(huì)發(fā)現(xiàn)很多題目考的就是你對(duì)“哪個(gè)容器最適合當(dāng)前場(chǎng)景”的判斷力。注意TreeSet存儲(chǔ)自定義對(duì)象時(shí)如果沒(méi)實(shí)現(xiàn)Comparable接口add方法直接拋ClassCastException。所以以后你用TreeSet裝自己的類(lèi)時(shí)記得要么實(shí)現(xiàn)Comparable要么在new TreeSet時(shí)傳一個(gè)比較器Comparator。4. 第43題手把手拆解Map的統(tǒng)計(jì)與遍歷4.1 為什么一看到“統(tǒng)計(jì)次數(shù)”就應(yīng)該是Map如果題目說(shuō)“統(tǒng)計(jì)一串字符中每個(gè)字符出現(xiàn)的次數(shù)”80%的正確答案都要用到Map。原因很簡(jiǎn)單統(tǒng)計(jì)次數(shù)的本質(zhì)是建立“字符-次數(shù)”的映射關(guān)系。你來(lái)一個(gè)字符我就得去查一下“這個(gè)字符之前出現(xiàn)過(guò)沒(méi)”出現(xiàn)過(guò)就把次數(shù)加一沒(méi)出現(xiàn)過(guò)就放進(jìn)Map并初始化成1。這不正是Map的key查value的應(yīng)用場(chǎng)景嗎有人可能會(huì)想用兩個(gè)數(shù)組一個(gè)存字符一個(gè)存次數(shù)也能做啊。能是可以但數(shù)組的index是整數(shù)字符不能直接當(dāng)下標(biāo)你得先想辦法把每個(gè)字符映射成一個(gè)唯一的整數(shù)還得處理范圍問(wèn)題。Map直接幫你把key定為字符類(lèi)型value定為Integer比兩個(gè)數(shù)組的做法簡(jiǎn)潔得多也更不容易寫(xiě)出邊界bug。這就是為什么我總說(shuō)Map不是高級(jí)技巧它是你腦子里該有的第一反應(yīng)。4.2 完整參考代碼字符計(jì)數(shù)import java.util.HashMap; import java.util.Map; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); String line sc.nextLine(); MapCharacter, Integer map new HashMap(); for (int i 0; i line.length(); i) { char c line.charAt(i); if (c ) { continue; // 跳過(guò)空格題目一般只統(tǒng)計(jì)可見(jiàn)字符 } map.put(c, map.getOrDefault(c, 0) 1); } for (Map.EntryCharacter, Integer entry : map.entrySet()) { System.out.println(entry.getKey() entry.getValue()); } } }核心就是map.put(c, map.getOrDefault(c, 0) 1)這一行。它的邏輯如果c已經(jīng)在Map里getOrDefault返回當(dāng)前次數(shù)加一后覆蓋回去如果c不在Map里getOrDefault返回默認(rèn)值0加一變成1put進(jìn)去。一句話(huà)完成“判斷存在與否 更新計(jì)數(shù)”這就是Map處理統(tǒng)計(jì)問(wèn)題最舒服的姿勢(shì)。4.3 getOrDefault、put、entrySet這些方法都在干嘛put()是所有Map實(shí)現(xiàn)都必須有的核心方法。調(diào)用put(key, value)時(shí)HashMap先算key的hashCode定位到數(shù)組下標(biāo)然后執(zhí)行“插入或覆蓋”的操作如果下標(biāo)處沒(méi)有元素直接放入如果有元素且key相等equals判斷就用新value覆蓋舊value并返回舊value如果有元素但key不等說(shuō)明哈希碰撞了就掛到鏈表后面或插入紅黑樹(shù)。getOrDefault(key, defaultVal)是一個(gè)看起來(lái)簡(jiǎn)單但極其實(shí)用的方法。它的語(yǔ)義是如果Map里有這個(gè)key返回對(duì)應(yīng)的value沒(méi)有返回defaultVal。這個(gè)方法在刷題里簡(jiǎn)直是無(wú)價(jià)之寶因?yàn)榻y(tǒng)計(jì)場(chǎng)景里“沒(méi)有出現(xiàn)過(guò)0次”這件事太常見(jiàn)了沒(méi)有它你就得先containsKey判斷再get再put要寫(xiě)三行代碼。有它一行搞定。entrySet()返回的是Map.Entry對(duì)象的Set視圖。每個(gè)Map.Entry代表一個(gè)鍵值對(duì)有g(shù)etKey()和getValue()兩個(gè)方法。用foreach遍歷entrySet是遍歷Map最常用的方式因?yàn)樗瑫r(shí)拿到key和value不需要再多查一次。如果你只需要key可以遍歷keySet()只遍歷value就用values()。這三個(gè)方法組合起來(lái)基本覆蓋了Map遍歷的所有場(chǎng)景。4.4 遍歷Map的幾種姿勢(shì)對(duì)比我直接給你一個(gè)表格對(duì)比你自己感受一下差異遍歷方式寫(xiě)法適合場(chǎng)景注意事項(xiàng)entrySet()for (Map.EntryK,V e : map.entrySet())同時(shí)需要key和value最常用性能也好keySet() get()for (K k : map.keySet())只需要key或者要按key取valuevalue在循環(huán)里單獨(dú)查一次多一次hashvalues()for (V v : map.values())只需要value拿不到keyforEach(Java 8)map.forEach((k, v) - {...})函數(shù)式風(fēng)格需要lambda基礎(chǔ)我的建議是前三種你必須手寫(xiě)熟練因?yàn)橛行┟嬖嚬P試環(huán)境不讓你用太新的語(yǔ)法而且手寫(xiě)一遍能強(qiáng)化你對(duì)Map結(jié)構(gòu)的記憶。forEach留到你學(xué)完lambda再用初期不要強(qiáng)行秀操作。另外如果你遍歷TreeMap這三種方式返回的順序都會(huì)按key的自然順序排好版這點(diǎn)和HashMap不一樣判斷“要不要輸出順序”時(shí)選對(duì)實(shí)現(xiàn)類(lèi)就行。5. 刷這兩題最容易踩的坑我?guī)湍闾崆芭诺?.1 泛型基礎(chǔ)類(lèi)型寫(xiě)錯(cuò)的崩潰瞬間我見(jiàn)過(guò)太多次這個(gè)報(bào)錯(cuò)Type argument cannot be of primitive type。就是你寫(xiě)了ArrayList 或者HashMapchar, Integer。Java泛型必須是引用類(lèi)型int要寫(xiě)成Integerchar要寫(xiě)成Character。初學(xué)者經(jīng)常抱怨“為什么這么設(shè)計(jì)”很簡(jiǎn)單泛型要支持Object的方法基本類(lèi)型不是Object沒(méi)法統(tǒng)一處理。后面你會(huì)接觸到基本類(lèi)型專(zhuān)用集合比如IntList但現(xiàn)在你只需要記住集合和Map一律用包裝類(lèi)。在你寫(xiě)完代碼后最好主動(dòng)檢查一遍所有尖括號(hào)里的類(lèi)型是不是包裝類(lèi)這個(gè)習(xí)慣能省很多編譯錯(cuò)誤。5.2 remove方法的重載歧義List的remove有兩個(gè)重載remove(int index)和remove(Object o)。當(dāng)你寫(xiě)list.remove(2)時(shí)編譯器會(huì)優(yōu)先匹配remove(int)所以它刪的是下標(biāo)為2的元素而不是值為2的元素。如果你有一個(gè)List 想刪掉值為2的元素你必須寫(xiě)list.remove(Integer.valueOf(2))。這是Java API設(shè)計(jì)里一個(gè)著名的坑?？驮u(píng)論區(qū)幾乎每過(guò)幾期就有人問(wèn)。刷題的時(shí)候如果發(fā)現(xiàn)“刪錯(cuò)了”先往這個(gè)方向想。5.3 遍歷時(shí)刪除元素導(dǎo)致并發(fā)修改異常剛才提過(guò)foreach遍歷集合時(shí)刪除元素會(huì)拋ConcurrentModificationException。原理是集合內(nèi)部有個(gè)modCount修改次數(shù)計(jì)數(shù)器迭代器在創(chuàng)建時(shí)會(huì)記住這個(gè)值每次next()之前都會(huì)檢查當(dāng)前modCount和預(yù)期值是否一致不一致就拋異常。你可能會(huì)問(wèn)那我真要在遍歷時(shí)刪除怎么辦答案是使用迭代器Iterator自己IteratorInteger it list.iterator(); while (it.hasNext()) { Integer val it.next(); if (val 3) { it.remove(); // 安全刪除它會(huì)把modCount同步一致 } }這個(gè)方法在后面的算法題里會(huì)頻繁碰到比如“刪除鏈表中所有等于某個(gè)值的節(jié)點(diǎn)”。提前把這套規(guī)則理解透會(huì)少掉很多頭發(fā)。5.4 HashMap和Hashtable別搞混面試八股文里有一道經(jīng)典題HashMap和Hashtable的區(qū)別。刷題階段你只需要記住HashMap允許key和value為nullHashtable不允許HashMap是線(xiàn)程不安全的但性能好單線(xiàn)程刷題沒(méi)問(wèn)題Hashtable是線(xiàn)程安全的但方法都加了鎖性能差現(xiàn)在基本被淘汰了。選擇題如果看到“線(xiàn)程安全且效率高”這種選項(xiàng)那是在釣魚(yú)因?yàn)樾屎途€(xiàn)程安全往往是矛盾的?，F(xiàn)在的官方推薦是如果需要線(xiàn)程安全用ConcurrentHashMap而不是Hashtable。5.5 輸出格式要求?？偷呐蓄}系統(tǒng)對(duì)輸出格式有嚴(yán)格檢查尤其是“多余空格”。比如要求輸出“1 2 3”你輸出“1 2 3 ”末尾多一個(gè)空格有些判題系統(tǒng)能過(guò)有些判題系統(tǒng)就判錯(cuò)。我建議你養(yǎng)成一個(gè)好習(xí)慣用StringBuilder或一個(gè)標(biāo)志位來(lái)控制空格不要無(wú)腦在循環(huán)里拼“元素空格”。這是我刷題踩過(guò)很多次后的經(jīng)驗(yàn)看起來(lái)是小問(wèn)題實(shí)際浪費(fèi)的時(shí)間非常多。StringBuilder sb new StringBuilder(); for (Integer val : set) { if (sb.length() 0) { sb.append( ); } sb.append(val); } System.out.println(sb);這種寫(xiě)法不會(huì)有多余空格也方便你在拼完字符串后進(jìn)一步處理比直接在循環(huán)里打印要靈活得多。6. 刷完這兩題以后我建議你這樣繼續(xù)練6.1 動(dòng)手把每個(gè)實(shí)現(xiàn)類(lèi)都跑一遍你剛學(xué)的TreeSet、HashMap最好別只在?？蜕嫌?。我建議你回到本地IDE新建一個(gè)測(cè)試類(lèi)把ArrayList、LinkedList、HashSet、TreeSet、HashMap、TreeMap這六個(gè)類(lèi)全部new一遍。每個(gè)類(lèi)都執(zhí)行一遍添加、刪除、查詢(xún)、遍歷用debug模式看一眼里面的結(jié)構(gòu)。尤其是HashMap你把斷點(diǎn)打在put方法上能看到它怎么計(jì)算hash、怎么找桶、怎么掛鏈表這個(gè)印象比讀十遍文章都深刻。6.2 做兩道綜合題鞏固一下?？蜕嫌胁簧倬C合題比如“統(tǒng)計(jì)一個(gè)英文句子中不同單詞的數(shù)量”或“尋找數(shù)組中出現(xiàn)次數(shù)超過(guò)一半的數(shù)字”。前者用Set和Map結(jié)合后者只用Map就能解。這些題目會(huì)逼著你把集合類(lèi)和Map串起來(lái)用比孤立刷題效果更好。做的時(shí)候先停下來(lái)想一想“這道題我應(yīng)該用List還是Set還是Map”想對(duì)容器再動(dòng)手這是最重要的解題步驟。6.3 看一遍集合類(lèi)的繼承結(jié)構(gòu)圖不需要背但你要能畫(huà)出這樣一條鏈路Iterable - Collection - List/Set/Queue然后List下面有ArrayList/LinkedList/VectorSet下面有HashSet/LinkedHashSet/TreeSetMap是獨(dú)立接口下面有HashMap/LinkedHashMap/TreeMap。這張圖能幫你建立“接口-實(shí)現(xiàn)類(lèi)”的坐標(biāo)系以后看到任何一個(gè)類(lèi)你都能立刻說(shuō)出它屬于哪個(gè)陣營(yíng)、有什么特點(diǎn)。說(shuō)白了集合框架的重點(diǎn)不是背方法而是建立坐標(biāo)系方法的使用反而水到渠成。6.4 形成一個(gè)自己的“容器選擇清單”根據(jù)我自己的經(jīng)驗(yàn)等你做過(guò)的題足夠多你會(huì)自然形成一套“選容器”的條件反射。我在這分享我的版本給你參考需要存一串元素且允許重復(fù)ArrayList需要頻繁在頭部或中間增刪LinkedList雖然筆試很少考這個(gè)不允許重復(fù)且不管順序HashSet不允許重復(fù)且要排序TreeSet不允許重復(fù)但要保持插入順序LinkedHashSet需要鍵值映射、不在意順序HashMap需要鍵值映射、按鍵排序TreeMap需要鍵值映射、按插入順序遍歷LinkedHashMap這套清單不是標(biāo)準(zhǔn)答案但它能幫你在看到題目需求的第一時(shí)間下意識(shí)地選到合適的容器。有了這個(gè)慣性你后面刷各種算法題都會(huì)輕松很多。最后再分享一個(gè)帶刷過(guò)程中我反復(fù)跟學(xué)生強(qiáng)調(diào)的體會(huì)集合類(lèi)和Map這部分內(nèi)容初學(xué)的時(shí)候感覺(jué)像在背一堆API但其實(shí)它們背后全都是很樸素的數(shù)據(jù)結(jié)構(gòu)思想。數(shù)組、鏈表、哈希、樹(shù)這些聽(tīng)起來(lái)“高大上”的詞落到日常寫(xiě)代碼里就是“我該選哪個(gè)容器”。你只要親自把這些容器一個(gè)個(gè)new出來(lái)、調(diào)試、用debug看內(nèi)部變化很快就能建立屬于自己的手感。刷題這件事不怕慢就怕不親自動(dòng)手拆。希望這篇帶刷能幫你跨過(guò)這個(gè)坎繼續(xù)往后刷的時(shí)候你會(huì)發(fā)現(xiàn)自己寫(xiě)代碼的思路清晰了不止一個(gè)檔次。