PAGE2PAGE2TableofContentsIntroduction介紹數(shù)組4SumRemoveDuplicatesfromSortedArrayRemoveElementValidSudoku鏈表MergeSortedListsMergekSortedListsSwapNodesinPairsReverseNodesink-Group查找SearchinRotatedSortedArraySearchforaRangeSearchInsertPosition棧和隊(duì)列ParenthesesLongestParentheses位運(yùn)算DivideTwoIntegers字符串ImplementstrStr()SubstringwithConcatenationofAllWords回溯LetterCombinationsofaPhoneNumberGenerateParenthesesSudokuSolver細(xì)節(jié)實(shí)現(xiàn)分支限界

貪心1.12數(shù)學(xué)1.13NextPermutation1.13.1大數(shù)據(jù)算法1.14topK1.14.1外排序1.14.2介紹介紹PAGE7PAGE7Introduction介紹算法與數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是為了滿足算法有效訪問(wèn)數(shù)據(jù)訪問(wèn)的要求。數(shù)學(xué)知識(shí)卡特蘭數(shù)基本運(yùn)算關(guān)于數(shù)的各種操作技巧得到整數(shù)的基（即十進(jìn)制位數(shù)）intintd=1;//與x同位數(shù)的整數(shù),如x=312,d=100intk=1;//x的位數(shù)，如x=321,k=3while(x/d>=10){d*=10;k++;}線性表鏈表分析第一反應(yīng)是遍歷鏈表，并用HashMap將訪問(wèn)過(guò)的節(jié)點(diǎn)記錄下來(lái)，如果出現(xiàn)重復(fù)訪問(wèn)，則說(shuō)明有環(huán)，這樣的時(shí)間復(fù)雜度是O(N),空間復(fù)雜度也是O(N)。另外一種方式就是設(shè)置快慢兩個(gè)指針，p1和p2,一開始都指向表頭，p1每次移動(dòng)一步，p2每次移動(dòng)兩步，如果p1和p2相遇，則說(shuō)明有環(huán)。代碼如下：樹圖排序算法的實(shí)際實(shí)現(xiàn)（Arrays.sort源碼分析）我們將使用迭代改進(jìn)的方式來(lái)描述現(xiàn)實(shí)中排序算法的實(shí)現(xiàn)，主要參考java中的Arrays.sort源碼。baseline是quicksort，然后在此基礎(chǔ)上，進(jìn)行迭代改進(jìn)。Out-of-Core算法排序、查找、join100億個(gè)數(shù)字中找出最大的1000個(gè)這是最基本問(wèn)題了，答案是用堆，但是用大根堆，還是小根堆，是有區(qū)別的。正確答案是用小根堆，首先讀取前1000個(gè)數(shù)，建立一個(gè)1000元素的小根堆，然后每次讀取一個(gè)新的數(shù)，將其與堆頂?shù)脑兀茨壳皰呙璧臄?shù)中最大的1000元素中最小的，即第1000大的）比較，如果新元素比堆頂元素大，則刪除堆頂元素，插入新元素，調(diào)整堆，否則什么也不做。相反，同理，如果是找出最小的1000，則采用大根堆。用2G內(nèi)存對(duì)10億數(shù)進(jìn)行排序這類大數(shù)據(jù)排序，或大數(shù)據(jù)統(tǒng)計(jì)（找出top-K，Middle-K）都要利用分治的思想，或空間搜索的思想一步步縮小搜索空間。大數(shù)據(jù)排序，基本上是利用歸并排序，先把文件分成很多塊，然后對(duì)每塊進(jìn)行排序，然后進(jìn)行歸并。InternalSortQuicksortTournamentSort利用找出40億個(gè)非負(fù)整數(shù)中出現(xiàn)兩次的數(shù)利用Bitmap來(lái)壓縮空間，32位無(wú)符號(hào)整數(shù)為0~4294967295,而0-3次可以用2個(gè)bit表示（因?yàn)橐髢纱危灾辽僖?,1,2,3四種狀態(tài)）。所以可以利用42949672952個(gè)比特位的空間，即(2^322)/8=1GB的內(nèi)存來(lái)完成運(yùn)算。找出100億中重復(fù)的URL利用hash函數(shù)的特性和divideandconquer算法，對(duì)于相同輸入，任何hash函數(shù)值也相同，反之不一定，（不過(guò)話說(shuō)所有函數(shù)都有這個(gè)特性吧？）?？梢詇ash函數(shù)吧URLdivide到各個(gè)比較小的文件，然后分而治之。找出100億個(gè)整數(shù)的中位數(shù)（或者進(jìn)行其他區(qū)間統(tǒng)計(jì)）利用桶排序，將數(shù)據(jù)按大小歸類，放到不同的桶中，然后找出中位數(shù)所在的那個(gè)桶，然后再對(duì)通過(guò)進(jìn)行進(jìn)一步的桶排序，當(dāng)剩余數(shù)小到一定時(shí)候，就可以選用內(nèi)存排序了。其實(shí)是一個(gè)逐步縮小搜索空間的過(guò)程。B-tree、B+tree、B-linktree動(dòng)態(tài)規(guī)劃找零錢換錢的最少貨幣數(shù)1.給一組不同面值的貨幣，一個(gè)金額M，求組成M的最少貨幣數(shù)，其中，每種面值的貨幣都可以使用任意張。2.給給一組各種面值的貨幣（里面可能有相同面值的貨幣），一個(gè)金額M，求組成M的最少貨幣數(shù)，其中，每個(gè)貨幣只能使用一次。換錢的方法數(shù)3.給一組不同面值的貨幣，一個(gè)金額M，求組成M的最少貨幣數(shù)，其中，每種面值的貨幣都可以使用任意張。0-1背包問(wèn)題找零錢和背包問(wèn)題有很多共同之處。動(dòng)態(tài)規(guī)劃的實(shí)際應(yīng)用joinoptimization字符串匹配KMP算法給定兩個(gè)字符串str和pattern,長(zhǎng)度分別為N,M。實(shí)現(xiàn)一個(gè)算法，如果字符串str中含有子串pattern,則返回pattern在str中的開始位置，不含則返回-1。簡(jiǎn)單KMP，時(shí)間復(fù)雜度為O(n),空間復(fù)雜度為O(M*A),A為字符的數(shù)目，英語(yǔ)為26。解法:首先，對(duì)pattern構(gòu)建一個(gè)自動(dòng)機(jī)，用26*M的數(shù)組來(lái)表示一個(gè)自動(dòng)機(jī)。構(gòu)建自動(dòng)機(jī)的步驟很巧妙，在構(gòu)造自動(dòng)機(jī)的過(guò)程中，利用目前的自動(dòng)機(jī)來(lái)構(gòu)造下一步自動(dòng)機(jī)。10.RegularExpressionMatching分析首先第一印象是采用遞歸的方式，首先匹配str[i]與exp[j]，然后再遞歸匹配str[i+1...]與exp[j+1...]。如果exp[j+1]是普通字符串或"."的話，上面的遞歸顯然是正確的。但如果exp[j+1]是"*"的話，上面的遞歸就不正確了。例如，str="aabc",exp="a*bc",結(jié)果應(yīng)該是true,但是按上面的遞歸會(huì)在i=0,j=0后,匹配str[1..]和exp[1...],顯然會(huì)返回錯(cuò)誤結(jié)果。因此我們要讀"*"特殊處理，"*"的特殊性在于，它會(huì)匹配或者叫消耗0或多個(gè)str[i]字符。因此當(dāng)exp[j+1]=="*",要采用backtracking的方式，對(duì)所有情況（"*"匹配0到n-i個(gè)）進(jìn)行嘗試，如果有一種情況能返回true,則整個(gè)匹配就返回true。因此，代碼如下：數(shù)組數(shù)組PAGE8PAGE8數(shù)組4Sum4SumPAGE11PAGE114Sum問(wèn)題描述GivenanarraySofnintegers,arethereelementsa,b,c,anddinSsuchthata+b+c+d=target?Findalluniquequadrupletsinthearraywhichgivesthesumoftarget.Note:Forexample,givenarrayS={10-10-22},andtarget=0.Asolutionsetis:Elementsinaquadruplet(a,b,c,d)mustbeinnon-descendingorder.(ie,a≤b≤c≤d)Thesolutionsetmustnotcontainduplicatequadruplets.Forexample,givenarrayS={10-10-22},andtarget=0.Asolutionsetis:(-1,0,0,1)(-2,-1,1,2)(-2,0,0,2)分析k-sum問(wèn)題都可以通過(guò)雙指針左右夾逼來(lái)解決，一般步驟是，先排序，然后外層做k-2層循環(huán)，最內(nèi)層循環(huán)采用雙指針左右夾逼。排序時(shí)間復(fù)雜度為O(nlgn),共有k-1層循環(huán)，所以時(shí)間復(fù)雜度為O(max{nlgn,n^k-1})。對(duì)于k>=4的情況，采用左右夾逼容易超時(shí)。因此可以采用預(yù)計(jì)算的方式，先緩存所有兩個(gè)數(shù)組合及他們的和，在最內(nèi)層循環(huán)時(shí)直接取出所有和等于target減去外面兩層和的組合。由于數(shù)組經(jīng)過(guò)排序，也可以采用剪枝的方式，首先在最外面層循環(huán)中去掉太大或太小的數(shù)，再把它轉(zhuǎn)為3Sum,再剪枝，再轉(zhuǎn)為2Sum。代碼實(shí)現(xiàn)cache版publicclassFourSum{publicList<List<Integer>>fourSum(int[]nums,inttarget){Arrays.sort(nums);Map<Integer,List<int[]>>cache=newHashMap<>();for(inti=0;i<nums.length-1;i++){for(intj=i+1;j<nums.length;j++){intsum=nums[i]+nums[j];if(cache.containsKey(sum)){List<int[]>list=cache.get(sum);list.add(newint[]{i,j});}else{List<int[]>list=newArrayList<>();list.add(newint[]{i,j});cache.put(sum,list);}}}Set<String>used=newHashSet<>();List<List<Integer>>result=newArrayList<>();for(inti=0;i<nums.length-3;i++){if(i>0&&nums[i]==nums[i-1])continue;for(intj=i+1;j<nums.length-2;j++){if(j>i+1&&nums[j]==nums[j-1])continue;intkey=target-nums[i]-nums[j];if(!cache.containsKey(key)){continue;]]};

}for(int[]ints:cache.get(key)){if(j>=ints[0])continue;Integer[]solution={nums[i],nums[j],nums[ints[0]],nums[ints[1if(!used.contains(Arrays.toString(solution))){used.add(Arrays.toString(solution));List<Integer>list=newArrayList<>(Arrays.asList(solution));result.add(list);}}}}returnresult;}pruning版，效率更高publicList<List<Integer>>fourSum(int[]nums,inttarget){List<List<Integer>>result=newArrayList<>();if(nums.length==0)returnresult;Arrays.sort(nums);intmax=nums[nums.length-1];intmin=nums[0];//去除太大或太小if(4*min>target||4*max<target)returnresult;for(inti=0;i<nums.length-3;i++){//去除太大if(4*nums[i]>target)returnresult;//去除重復(fù)if(i>0&&nums[i]==nums[i-1])continue;for(intj=i+1;j<nums.length-2;j++){//去除太大if((nums[i]+3*nums[j])>target)break;//去除重復(fù)if(j>i+1&&nums[j]==nums[j-1])continue;intp=j+1,q=nums.length-1;while(p<q){intsum=nums[i]+nums[j]+nums[p]+nums[q];if(sum==target){result.add(Arrays.asList(nums[i],nums[j],nums[p],nums[q]));p++;q--;//去除重復(fù)while(nums[q]==nums[q+1]&&p<q)q--;while(nums[p]==nums[p-1]&&p<q)p++;}elseif(sum>target){q--;//去除重復(fù)while(nums[q]==nums[q+1]&&p<q)q--;}else{//去除重復(fù)while(nums[p]==nums[p-1]&&p<q)p++;}}}}returnresult;}RemoveDuplicatesfromSortedArrayRemoveDuplicatesfromSortedArrayPAGE12PAGE12RemoveDuplicatesfromSortedArray問(wèn)題描述Givenasortedarray,removetheduplicatesinplacesuchthateachelementappearonlyonceandreturnthenewlength.Donotallocateextraspaceforanotherarray,youmustdothisinplacewithconstantmemory.Forexample,Giveninputarraynums=[1,1,2],Yourfunctionshouldreturnlength=2,withthefirsttwoelementsofnumsbeing1and2respectively.Itdoesn'tmatterwhatyouleavebeyondthenewlength.分析維護(hù)一個(gè)邊界，邊界左邊是已經(jīng)目前得到的不同的數(shù)，初始為num[0]。遍歷數(shù)組，將當(dāng)前值與上一個(gè)不同值即使邊界處的值比較，不同，則說(shuō)明又有一個(gè)不同的值，將插入邊界處，并擴(kuò)大邊界。代碼實(shí)現(xiàn)publicintpublicintremoveDuplicates(int[]nums){if(nums.length==0)return0;intid=1;for(inti=1;i<nums.length;i++){if(nums[i]!=nums[id-1]){nums[id++]=nums[i];}}returnid;}RemoveElementRemoveElementPAGE13PAGE13RemoveElementValidSudokuValidSudokuPAGE15PAGE15ValidSudokuDetermineifaSudokuisvalid,accordingto:SudokuPuzzles-TheRules.TheSudokuboardcouldbepartiallyfilled,whereemptycellsarefilledwiththecharacter'.'.Apartiallyfilledsudokuwhichisvalid.Note:AvalidSudokuboard(partiallyfilled)isnotnecessarilysolvable.Onlythefilledcellsneedtobevalidated.分析采用一個(gè)大小為9的數(shù)組做hashtable/symboltable記錄出現(xiàn)的元素，對(duì)于所有行，所有列以及9個(gè)3*3的subbox進(jìn)行驗(yàn)證.代碼如下publicbooleanisValidSudoku(char[][]board){boolean[]used=newboolean[9];for(inti=0;i<9;i++){fillFalse(used);for(intj=0;j<9;j++){chark=board[i][j];if(!check(used,k))returnfalse;}fillFalse(used);for(intj=0;j<9;j++){chark=board[j][i];if(!check(used,k))returnfalse;}}for(inti=0;i<3;i++){for(intj=0;j<3;j++){if(!checkSubbox(board,i,j))returnfalse;}}return true;}publicvoidfillFalse(boolean[]used){for(inti=0;i<used.length;i++){used[i]=false;}}publicbooleancheck(boolean[]used,charch){if(ch=='.')returntrue;if(used[ch-'1'])returnfalse;else{used[ch-'1']=true;returntrue;}}publicbooleancheckSubbox(char[][]board,inti,intj){boolean[]used=newboolean[9];for(intp=i*3;p<i*3+3;p++){for(intq=j*3;q<j*3+3;q++){chark=board[p][q];if(!check(used,k))returnfalse;}}returntrue;}PAGE16PAGE16鏈表鏈表MergeTwoSortedListsMergeTwoSortedListsPAGE18PAGE18MergeTwoSortedLists描述Mergetwosortedlinkedlistsandreturnitasanewlist.Thenewlistshouldbemadebysplicingtogetherthenodesofthefirsttwolists.分析設(shè)置兩個(gè)指針，分別指向兩個(gè)鏈表，比較元素大小，交替地把較小元素連接到返回鏈表的尾部。直到到某個(gè)鏈表的尾部，然后把剩下的那個(gè)鏈表鏈接到返回鏈表的尾部，結(jié)束。代碼實(shí)現(xiàn)publicclasspublicclassMergeTwoSortedLists{//Definitionforsingly-linkedlist.publicstaticclassListNode{intval;ListNodenext;ListNode(intx){val=x;}}publicListNodemergeTwoLists(ListNodel1,ListNodel2){if(l1==null||l2==null){returnl1!=null?l1:l2;}ListNodehead=newListNode(-1);ListNodecur=head;while(l1!=null&&l2!=null){if(l1.val<l2.val){cur.next=l1;cur=cur.next;l1=l1.next;}else{cur.next=l2;cur=cur.next;l2=l2.next;}}cur.next=l1!=null?l1:l2;returnhead.next;}MergekSortedListsMergekSortedListsPAGE21PAGE21MergekSortedLists問(wèn)題描述Mergeksortedlinkedlistsandreturnitasonesortedlist.Analyzeanddescribeitscomplexity.分析這個(gè)歸并排序的第二個(gè)步驟是一樣的，對(duì)k個(gè)鏈表進(jìn)行兩兩歸并，然后在對(duì)產(chǎn)生的k/2個(gè)鏈表再進(jìn)行兩兩歸并，直到最終歸并到一個(gè)鏈表。時(shí)間復(fù)雜度為(nlgk),n為鏈表的最大長(zhǎng)度或者維護(hù)一個(gè)k大小的小根堆，不斷地取走堆頂元素，并將該元素的next節(jié)點(diǎn)插入堆中，直至堆為空，即所有鏈表都遍歷完。時(shí)間復(fù)雜度為(nlgk),n為鏈表的最大長(zhǎng)度。代碼實(shí)現(xiàn)遞歸兩兩歸并版,比小根堆效率更高publicpublicListNodemergeKLists(ListNode[]lists){if(lists.length==0)returnnull;if(lists.length==1)returnlists[0];ListNode[]newLists=newListNode[(lists.length+1)/2];for(inti=0;i<lists.length/2;i++){ListNodenode=mergeTwoLists(lists[2*i],lists[2*i+1]);newLists[i]=node;}if(lists.length%2!=0)newLists[(lists.length+1)/2-1]=lists[lists.length-1];returnmergeKLists(newLists);}publicListNodemergeTwoLists(ListNodel1,ListNodel2){if(l1==null||l2==null){returnl1!=null?l1:l2;}ListNodehead=newListNode(-1);ListNodecur=head;while(l1!=null&&l2!=null){if(l1.val<l2.val){cur.next=l1;cur=cur.next;l1=l1.next;}else{cur.next=l2;cur=cur.next;l2=l2.next;}}cur.next=l1!=null?l1:l2;returnhead.next;}最小堆版publicListNodemergeKListsV2(ListNode[]lists){if(lists.length==0){publicListNodemergeKListsV2(ListNode[]lists){if(lists.length==0){returnnull;}PriorityQueue<ListNode>minHeap=newPriorityQueue<>(lists.length,newComparator<ListNode>(){@Overridepublicintcompare(ListNodeo1,ListNodeo2){if(o1.val<o2.val){return -1;}elseif(o1.val==o2.val){return0;}else{return1;}}});for(ListNodelist:lists){if(list!=null){minHeap.add(list);}}ListNodehead=newListNode(-1);ListNodetail=head;while(!minHeap.isEmpty()){tail.next=minHeap.poll();tail=tail.next;if(tail.next!=null)minHeap.add(tail.next);}returnhead.next;}SwapNodesinPairsSwapNodesinPairsPAGE22PAGE22SwapNodesinPairs分析同反轉(zhuǎn)鏈表等題目一樣，仔細(xì)分析，設(shè)置好指針的交換順序。這種題目一般都會(huì)有遞歸和迭代兩種解法。代碼實(shí)現(xiàn)publicpublicListNodeswapPairs(ListNodehead){ListNodedummy=newListNode(-1);dummy.next=head;ListNodeprev=dummy;ListNodefirst=dummy.next;while(first!=null&&first.next!=null){prev.next=first.next;first.next=first.next.next;prev.next.next=first;prev=first;first=first.next;}returndummy.next;}ReverseNodesink-GroupReverseNodesink-GroupPAGE24PAGE24ReverseNodesink-Group問(wèn)題描述Givenalinkedlist,reversethenodesofalinkedlistkatatimeandreturnitsmodifiedlist.Ifthenumberofnodesisnotamultipleofkthenleft-outnodesintheendshouldremainasitis.Youmaynotalterthevaluesinthenodes,onlynodesitselfmaybechanged.Onlyconstantmemoryisallowed.Forexample,Giventhislinkedlist:1->2->3->4->5Fork=2,youshouldreturn:2->1->4->3->5Fork=3,youshouldreturn:3->2->1->4->5分析有遞歸和迭代兩種解法，遞歸解法每次反轉(zhuǎn)k個(gè)節(jié)點(diǎn)的子鏈表，返回新子鏈表的頭部，遞歸是從后向前進(jìn)行的，迭代是從前向后進(jìn)行的。代碼實(shí)現(xiàn)迭代版publicpublicListNodereverseKGroup(ListNodehead,intk){if(head==null||head.next==null||k<2)returnhead;ListNodedummy=newListNode(-1);dummy.next=head;ListNodeprev=dummy;ListNodeend=prev;while(end!=null){for(inti=0;i<k&&end!=null;i++){end=end.next;}if(end==null){break;}prev=reverse(prev,prev.next,end);end=prev;}returndummy.next;}privateListNodereverse(ListNodeprev,ListNodebegin,ListNodeend){ListNode end_next=end.next;for(ListNodep=begin,cur=p.next,next=cur.next;cur!=end_next;p=cur,cur=next,next=next!=null?next.next:null){cur.next=p;}begin.next=end_next;prev.next=end;returnbegin;}遞歸版擴(kuò)展這種題目，考察的主要是控制結(jié)構(gòu)，這樣在復(fù)雜的控制流程中寫出正確，清晰的代碼。最主要的是要把控制流程的代碼和正常的業(yè)務(wù)邏輯代碼分開。首先要通過(guò)函數(shù)把不同的邏輯分開，其次要在代碼中，把復(fù)雜的控制邏輯寫在for中，而不是用while在一起。PAGE25PAGE25查找SearchinRotatedSortedArraySearchinRotatedSortedArrayPAGE27PAGE27SearchinRotatedSortedArray問(wèn)題描述Supposeasortedarrayisrotatedatsomepivotunknowntoyoubeforehand.(i.e.,0124567mightbecome4567012).Youaregivenatargetvaluetosearch.Iffoundinthearrayreturnitsindex,otherwisereturn-1.Youmayassumenoduplicateexistsinthearray.分析仍然采用二分搜索的方法，由于至少有一半的元素是有序的，因此，每次將數(shù)組重新劃分后，我們將low和mid比較，以此pivot是否落在左邊區(qū)間，然后對(duì)兩中情況分別處理。如果pivot不在左邊區(qū)間，則左邊是有序的，通過(guò)targetA[low&&targetA[mid判斷target的是否在左分區(qū)，如果是則hi=mid-1,如果不是，則lo=mid+1;如果pivot在左邊區(qū)間，則右邊是有序的，通過(guò)targetA[mid&&targetA[hi判斷target的是否在右分區(qū)，如果是則lomid1,如果不是，則himid1可見，該方法和二分搜索是類似的，只不過(guò)判斷target是在左分區(qū)還是在右分區(qū)，需要根據(jù)pivot是否在左邊做特殊處理。代碼實(shí)現(xiàn)publicintpublicintsearch(int[]nums,inttarget){intlo=0,hi=nums.length-1;while(lo<=hi){intmid=(lo+hi)/2;if(target==nums[mid])returnmid;if(nums[lo]<=nums[mid]){if(target>=nums[lo]&&target<nums[mid]){hi=mid-1;}else{lo=mid+1;}}else{if(target>nums[mid]&&target<=nums[hi]){lo=mid+1;}else{hi=mid-1;}}}return-1;}SearchforaRangeSearchforaRangePAGE30PAGE30SearchforaRange問(wèn)題描述Givenasortedarrayofintegers,findthestartingandendingpositionofagiventargetvalue.Youralgorithm'sruntimecomplexitymustbeintheorderofO(logn).Ifthetargetisnotfoundinthearray,return[-1,-1].Forexample,Given[5,7,7,8,8,10]andtargetvalue8,return[3,4].分析對(duì)數(shù)組做兩次二分搜索，分別找出上界和下界。代碼實(shí)現(xiàn)publicintpublicint[]searchRange(int[]nums,inttarget){intlo=0;inthi=nums.length-1;while(lo<hi){intmid=(lo+hi)/2;if(nums[mid]<target)lo=mid+1;//不停地向右移動(dòng)lo,直到nums[mid]>=targetelsehi=mid;//向左移動(dòng)hi,不加1是為了避免mid=left的情況。}intleft;if(nums[lo]!=target)returnnewint[]{-1,-1};elseleft=lo;hi=nums.length-1;while(lo<hi){intmid=(lo+hi)/2+1;//避免([2,2],2)這種情況時(shí)出現(xiàn)死循環(huán)。if(nums[mid]>target)hi=mid-1;elselo=mid;}returnnewint[]{left,lo};}擴(kuò)展mid=(low+high)/2和mid=low+(high-low)/2有何不同？前一種寫法在low和high都比較大時(shí)會(huì)造成low+high大于Integer.MAX_VALUE,從而溢出。關(guān)于二分搜索low和high指針移動(dòng)的問(wèn)題while(lo<hi){intmid=(lo+hi)/2;if(nums[mid]==target)while(lo<hi){intmid=(lo+hi)/2;if(nums[mid]==target){returnmid;}elseif(nums[mid]<target){lo=mid+1;}else{hi=mid-1;}}SearchInsertPositionSearchInsertPositionPAGE32PAGE32SearchInsertPosition問(wèn)題描述Givenasortedarrayandatargetvalue,returntheindexifthetargetisfound.Ifnot,returntheindexwhereitwouldbeifitwereinsertedinorder.Youmayassumenoduplicatesinthearray.Herearefewexamples.[1,3,5,6],5→2[1,3,5,6],2→1[1,3,5,6],7→4[1,3,5,6],0→0分析和searchforarange的解答類似，都是基于二分搜索的變形。對(duì)于這類問(wèn)題，都可以在二分搜索的基礎(chǔ)上，對(duì)于不同的情形采用不同的判斷條件和不同的移動(dòng)方式，從而得到適合問(wèn)題的解法。代碼實(shí)現(xiàn)ifif(target>nums[nums.length-1])returnnums.length;intlo=0,hi=nums.length-1;while(lo<hi){intmid=(lo+hi)/2;if(nums[mid]>=target){hi=mid;}else{lo=mid+1;}}return lo;擴(kuò)展[1,3,5,6],7→4和[1,3,5,6],0→0這兩個(gè)cornercase決定了必須使用>=的判斷條件，并對(duì)target>nums[nums.length-1]的情況做特殊處理。if(nums[mid]>=target)j=mid;相當(dāng)于用target值索引設(shè)立了一個(gè)邊界，能夠保證j不越過(guò)該邊界。PAGE33PAGE33棧和隊(duì)列棧和隊(duì)列ValidParenthesesValidParenthesesPAGE35PAGE35Parentheses問(wèn)題描述Givenastringcontainingjustthecharacters'(',')','{','}','['and']',determineiftheinputstringisvalid.Thebracketsmustcloseinthecorrectorder,"()"and"()[]{}"areallvalidbut"(]"and"([)]"arenot.分析利用棧，將輸入的字符依次入棧，發(fā)現(xiàn)對(duì)應(yīng)的括號(hào)就從棧中彈出一個(gè)元素，最后棧為空，則Parenthesesisvalid,否者invalid。實(shí)現(xiàn)復(fù)雜度為O(n),空間復(fù)雜度也為O(n)。代碼實(shí)現(xiàn)publicbooleanpublicbooleanisValid(Strings){char[]chars=s.toCharArray();Stack<Character>stack=newStack<>();for(charch:chars){if(!stack.isEmpty()&&isPair(stack.peek(),ch)){stack.pop();}else{stack.push(ch);}}returnstack.isEmpty();}publicbooleanisPair(charleft,charright){switch(left){case'(':returnright==')';case'{':returnright=='}';case'[':returnright==']';default:returnfalse;}}LongestValidParenthesesLongestValidParenthesesPAGE37PAGE37LongestValidParentheses問(wèn)題描述Givenastringcontainingjustthecharacters'('and')',findthelengthofthelongestvalid(well-formed)parenthesessubstring.For"(()",thelongestvalidparenthesessubstringis"()",whichhaslength=2.Anotherexampleis")()())",wherethelongestvalidparenthesessubstringis"()()",whichhaslength=4.分析遍歷字符串，并用棧記錄當(dāng)前索引，對(duì)于每個(gè)字符：如果當(dāng)前字符為'(',則將索引入棧。如果當(dāng)前字符為')',棧頂對(duì)應(yīng)的字符為')'，則將棧頂元素彈出，并用當(dāng)前索引減去棧頂索引，得到一個(gè)新的長(zhǎng)度curLen，將curLen如果當(dāng)前字符為')',棧為空，或棧頂對(duì)應(yīng)的字符為')',則將索引壓棧。代碼實(shí)現(xiàn)publicintpublicintlongestValidParentheses(Strings){if(s.length()==0){return0;}char[]chars=s.toCharArray();Stack<Integer>stack=newStack<>();intmaxLen=0;for(inti=0;i<chars.length;i++){if(chars[i]=='('){stack.push(i);}elseif(!stack.isEmpty()&&chars[stack.peek()]=='('){stack.pop();intcurLen=0;if(!stack.isEmpty()){curLen=i-stack.peek();}else{curLen=i+1;}maxLen=Math.max(maxLen,curLen);}else{stack.push(i);}}returnmaxLen;}位運(yùn)算位運(yùn)算PAGE39PAGE39位運(yùn)算Java位操作運(yùn)算符符號(hào)右移(">>")負(fù)數(shù)在最高位填充"1"，正數(shù)在最高位填充"0",右移一位相當(dāng)于除2,ArrayList中每次擴(kuò)容1.5倍，所使用的代碼就是：newCapacity=oldCapacity+(oldCapacity>>1);newCapacity=oldCapacity+(oldCapacity>>1);左移("<<")在最低位填充"0",左移一位相當(dāng)于乘2。無(wú)符號(hào)右移(">>>")在最高位填充"0"。位與("&")按位與運(yùn)算符，常見應(yīng)用是用來(lái)做bitmask運(yùn)算：intintbitmask=0x000F;intval=0x2222;val&bitmask==2位異或("^")"bitwiseexclusiveOR"，兩個(gè)操作數(shù)的第n位相同則結(jié)果第n位為0，不同即相異則結(jié)果第n位為1。位或("|")"bitwiseinclusiveOR"，兩個(gè)操作數(shù)的第n位有一個(gè)為1，則結(jié)果第n位為0，如果都為0則結(jié)果第n位為1。注意，如果用位運(yùn)算來(lái)進(jìn)行邏輯運(yùn)算的話，會(huì)導(dǎo)致兩邊的邏輯表達(dá)式都會(huì)被運(yùn)算，如下面所示：intintarray[]=newint[]{1,2,3};inti=0;//這里不會(huì)發(fā)生數(shù)組越界while(i<array.length&&array[i]!=4){i++;}i=0;//這里會(huì)發(fā)生數(shù)組越界while(i<array.length&array[i]!=4){i++;}因此，邏輯運(yùn)算符也叫做"short-circuit"布爾運(yùn)算符，位運(yùn)算符叫做"non-short-circuiting"運(yùn)算符。因?yàn)楫?dāng)左邊表達(dá)式就可以決定整個(gè)表達(dá)式的值時(shí)，右邊的就不會(huì)被計(jì)算。而為位運(yùn)算符總是計(jì)算左右兩個(gè)表達(dá)式。經(jīng)典算法對(duì)于整型變量a、b，如何不經(jīng)中間變量，來(lái)交換a與b的值？a=a^b;b=b^a;a=b^a;或者a=a+b;b=a-b;a=a-b;DivideTwoIntegersDivideTwoIntegersPAGE41PAGE41DivideTwoIntegers問(wèn)題描述Dividetwointegerswithoutusingmultiplication,divisionandmodoperator.Ifitisoverflow,returnMAX_INT.分析首先通過(guò)計(jì)算結(jié)果符號(hào)，把問(wèn)題reduce到兩個(gè)整數(shù)相除。然后把兩個(gè)數(shù)字轉(zhuǎn)為long型，以免溢出。最后把被除數(shù)減去除數(shù)，并通過(guò)將被除數(shù)每次加倍來(lái)加快速度。當(dāng)被除數(shù)大于剩余的除數(shù)時(shí)，再?gòu)某跏嫉某龜?shù)開始，重復(fù)以上步驟。代碼實(shí)現(xiàn)publicintpublicintdivide(intdividend,intdivisor){intsign=((dividend<0)^(divisor<0)) ?-1:longdvd=Math.abs((long)dividend);longdvs=Math.abs((long)divisor);longresult=0;while(dvd>dvs){longtemp=dvs;for(inti=0;dvd>=temp;i++,temp<<=1){dvd-=temp;result+=1<<i;}}result=sign*result>Integer.MAX_VALUE?Integer.MAX_VALUE:sign*result;return(int)result;}擴(kuò)展判斷兩個(gè)數(shù)a,b相除或相乘結(jié)果的符號(hào)？最直接寫法if((a>0&&b<0)||=""a<0=""&&=""b="">sign1elsesign1**sign(a0^(b0-11;位移加異或sign=(a^b)>>>31==0?1:-1;通過(guò)布爾邏輯sing=a<0!=b<0?-1:1;PAGE42PAGE42字符串字符串ImplementstrStr()ImplementstrStr()PAGE43PAGE43ImplementstrStr()問(wèn)題描述ImplementstrStr().Returnstheindexofthefirstoccurrenceofneedleinhaystack,or-1ifneedleisnotpartofhaystack.分析經(jīng)典的字符串搜索算法，有暴力搜索，KMP，、Boyer-Mooer和Rabin-Karp等。代碼實(shí)現(xiàn)暴力搜索SubstringwithConcatenationofAllWordsSubstringwithConcatenationofAllWordsPAGE45PAGE45SubstringwithConcatenationofAllWords問(wèn)題描述Youaregivenastring,s,andalistofwords,words,thatareallofthesamelength.Findallstartingindicesofsubstring(s)insthatisaconcatenationofeachwordinwordsexactlyonceandwithoutanyinterveningcharacters.Forexample,given:s:"barfoothefoobarman"words:["foo","bar"]Youshouldreturntheindices:[0,9].(orderdoesnotmatter).分析設(shè)置一個(gè)words.length*wordLen長(zhǎng)度的滑動(dòng)窗口，將窗口從左向右滑動(dòng)，并將窗口再劃分為長(zhǎng)度為wordlen的塊，依次檢查每個(gè)塊是否包含在words中，并且出現(xiàn)次數(shù)也是符合要求的。代碼實(shí)現(xiàn)publicpublicList<Integer>findSubstring(Strings,String[]words){List<Integer>result=newLinkedList<>();if(s.length()==0||words.length==0)returnresult;Map<String,Integer>wordCount=newHashMap<>();for(Stringword:words){wordCount.put(word,wordCount.getOrDefault(word,0)+1);}intwordLen=words[0].length();intwinSize=words.length*wordLen;for(inti=0;i<=s.length()-winSize;i++){Map<String,Integer>unused=newHashMap<>(wordCount);for(intj=0;j<winSize;j+=wordLen){Stringstr=s.substring(i+j,i+j+wordLen);intcount=unused.getOrDefault(str,-1);if(count==1){unused.remove(str);}elseif(count>1){unused.put(str,count-1);}else{break;}}if(unused.size()==0)result.add(i);}returnresult;}回溯回溯PAGE47PAGE47回溯概念回溯是一種類似枚舉的搜索嘗試方法，在搜索解的過(guò)程中，如果發(fā)現(xiàn)答案不正確或已到達(dá)邊界，就退回到上一步重新選擇。這種走不通就退回再走的技術(shù)稱為回溯法，而滿足回溯條件的某個(gè)狀態(tài)的被稱為“回溯點(diǎn)”?；舅枷雽?duì)于能用回溯解決的問(wèn)題，它的所有解構(gòu)成了一個(gè)解空間樹。回溯法采用深度優(yōu)先搜索(DFS)的策略，從根節(jié)點(diǎn)出發(fā)，評(píng)估每個(gè)節(jié)點(diǎn)是否屬于問(wèn)題的解，如果是，就繼續(xù)向下搜索，如果不是，則退回到父節(jié)點(diǎn)重新選擇搜索路徑。若用回溯法求問(wèn)題的所有解時(shí)，要回溯到根，且根結(jié)點(diǎn)的所有可行的子樹都要已被搜索遍才結(jié)束。而若使用回溯法求任一個(gè)解時(shí)，只要搜索到問(wèn)題的一個(gè)解就可以結(jié)束。一般步驟分析所給問(wèn)題，確定問(wèn)題的解空間制定節(jié)點(diǎn)的擴(kuò)展搜索規(guī)則采用DFS的方式搜索解空間，并注意使用剪枝函數(shù)避免無(wú)效搜索。算法框架回溯與遞歸的區(qū)別遞歸是指函數(shù)自己調(diào)用自己的一種形式?；厮莺虳FS,BFS,動(dòng)態(tài)規(guī)劃一樣是算法，可以用遞歸方式實(shí)現(xiàn)，也可以不用遞歸方式實(shí)現(xiàn)，而遞歸和循環(huán)，迭代一樣是一種方法。LetterCombinationsofaPhoneNumberLetterCombinationsofaPhoneNumberPAGE50PAGE5017.LetterCombinationsofaPhoneNumber問(wèn)題Givenadigitstring,returnallpossiblelettercombinationsthatthenumbercouldrepresent.Amappingofdigittoletters(justlikeonthetelephonebuttons)isgivenbelow.Input:Digitstring"23"Output:["ad","ae","af","bd","be","bf","cd","ce","cf"].Input:Digitstring"23"Output:["ad","ae","af","bd","be","bf","cd","ce","cf"].分析可以采用兩種方式來(lái)分析思考本題，一種是回溯，一種是組合。采用回溯時(shí)，首先構(gòu)建搜索樹，可以認(rèn)為digits中的第一個(gè)元素對(duì)于的letters為根節(jié)點(diǎn)的子節(jié)點(diǎn)，第二個(gè)元素對(duì)應(yīng)的letters為第一層節(jié)點(diǎn)的子節(jié)點(diǎn)，以此類推。然后我們制定規(guī)則來(lái)DFS搜索這棵樹，并注意保存狀態(tài)，即從根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑，當(dāng)滿足條件時(shí)（到達(dá)葉子節(jié)點(diǎn)時(shí)），再回溯到上一個(gè)節(jié)點(diǎn)，重新選擇路徑來(lái)搜索。采用組合時(shí)，可以采用incremental的方式來(lái)構(gòu)建組合，即首先構(gòu)建一個(gè)空集，然后構(gòu)建包含digitals[0]對(duì)于letters的組合，然后在構(gòu)建包含digitals[0]，digitals[1]對(duì)于letters的組合。同78.Subsets的解法類似。代碼實(shí)現(xiàn)回溯publicpublicMap<Integer,List<Character>>buildMap(){Stringalphabet="abcdefghijklmnopqrstuvwxyz";Map<Integer,List<Character>>map=newHashMap<>();for(inti=2,j=0;i<=9&&j<26;i++){List<Character>list=newArrayList<>();list.add(alphabet.charAt(j++));list.add(alphabet.charAt(j++));list.add(alphabet.charAt(j++));if(i==7||i==9){list.add(alphabet.charAt(j++));}map.put(i,list);}returnmap;}publicList<String>letterCombinations(Stringdigits){List<String>result=newArrayList<>();Map<Integer,List<Character>>map=buildMap();if(digits.length()==0){result.add("");}combine(digits,0,"",result,map);returnresult;}publicvoidcombine(Stringdigits,intindex,Stringprefix,List<String>result,Map<Integer,List<Character>>map){if(index==digits.length()){result.add(prefix);return;};List<Character>chars=map.get(Character.getNumericValue(digits.charAt(index)));for(Characterch:chars){combine(digits,index+1,prefix+ch,result,map);}}組合}}List<String>result=newArrayList<>();if(digits.length()==0)returnresult;result.add("");for(inti=0;i<digits.length();i++){char[]chars=digitletter[digits.charAt(i)-'0'].toCharArray();List<String>temp=newArrayList<>();for(Strings:result){for(charch:chars){temp.add(s+ch);}}result=temp;}returnresult;};publicList<String>letterCombinationsV2(Stringdigits){Stringdigitletter[]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"GenerateParenthesesGenerateParenthesesPAGE52PAGE52GenerateParentheses問(wèn)題描述Givennpairsofparentheses,writeafunctiontogenerateallcombinationsofwell-formedparentheses.Forexample,givenn=3,asolutionsetis:"((()))","(()())","(())()","()(())","()()()"分析采用遞歸的方式構(gòu)造括號(hào)串，當(dāng)左括號(hào)數(shù)量<n時(shí)，添加左括號(hào)，直到=n,然后添加右括號(hào)，并不斷回溯遞歸，直到右括號(hào)數(shù)量=n。代碼實(shí)現(xiàn)publicList<String>generateParenthesis(intn){List<String>result=newArrayList<>();backtrack(result,"",0,0,n);returnresult;}privatevoidbacktrack(List<String>result,Stringstr,intopen,intclose,intn){if(str.length()==2*n){result.add(str);return;}if(open<n){backtrack(result,str+"(",open+1,close,n);}if(close<open){backtrack(result,str+")",open,close+1,n);}}SudokuSolverSudokuSolverPAGE55PAGE55SudokuSolver問(wèn)題描述WriteaprogramtosolveaSudokupuzzlebyfillingtheemptycells.Emptycellsareindicatedbythecharacter'.'.Youmayassumethattherewillbeonlyoneuniquesolution.Asudokupuzzle......anditssolutionnumbersmarkedinred.分析應(yīng)該是采用回回溯的方式來(lái)對(duì)每個(gè)空白的地方進(jìn)行不斷的嘗試。注意，在嘗試之前可以進(jìn)行一些預(yù)處理，去掉那些本行本列中以及存在的數(shù)，只嘗試那些沒出現(xiàn)的數(shù)。代碼實(shí)現(xiàn)publicvoidsolveSudoku(char[][]board){if(board==null||board.length==0)return;solve(board);}publicstaticbooleansolve(char[][]board){for(inti=0;i<9;i++){for(intj=0;j<9;j++){if(board[i][j]=='.'){for(chark='1';k<='9';k++){board[i][j]=k;if(isValid(board,i,j)&&solve(board))returntrue;elseboard[i][j]='.';}returnfalse;}}}//當(dāng)最終求得正確解時(shí),會(huì)走到這一段代碼,因?yàn)樗械目崭穸急惶顫M,所以if語(yǔ)句不會(huì)被執(zhí)行。returntrue;}publicstaticbooleanisValid(char[][]board,inti,intj){for(intcol=0;col<9;col++){if(col!=j&&board[i][col]==board[i][j])returnfalse;}for(introw=0;row<9;row++){if(row!=i&&board[row][j]==board[i][j])returnfalse;}for(introw=(i/3)*3;row<(i/3)*3+3;row++){for(intcol=(j/3)*3;col<(j/3)*3+3;col++){if((row!=i||col!=j)&&board[row][col]==board[i][j])returnfalse;}}returntrue;}復(fù)雜度分析Manyrecursivesearchescanbemodeledasatree.InSodoku,youhave9possibilitieseachtimeyoutryoutanewfield.Atmaximum,youhavetoputsolutionsintoall81fields.Atth