前端算法和數(shù)據(jù)課前課堂課堂知識數(shù)組打平（扁平化）查數(shù)據(jù)動態(tài)貪心推薦擴6總7作8預課前課課堂復雜度數(shù)組鏈表集合hash表棧隊 樹圖排序冒泡快速排序原地快排序.二分搜O的概念，來描述算法的復雜度，簡而言之，就是算法執(zhí)行所需要的執(zhí)行次數(shù)，和數(shù)據(jù)量的關系(時間復雜度)，占用額外空間和數(shù)據(jù)量的關系(空間復雜度)O(1):常數(shù)復雜度(和數(shù)據(jù)量無關O(n線性時間復雜度（數(shù)組遍歷一次）O(n*logn:線性對數(shù)（遍歷+二分）O(n^2):平方方兩層遍歷O(2^nO(n!數(shù)組中name:'xxage:12name:'kaikebaage:12如果按照age排序，排序后，xx和kaikeba的相冒最經(jīng)典和簡單粗暴的排序算法，簡而言之，就是挨個對比，如果比右邊的數(shù)字大，就交換位置遍歷一次，最大的在最右邊，重復步驟，完成排序functionfunctionbubleSort(arr){varlen=arr.lengthfor(letouter=len;outer>=2;outer--{for(letinner=0;inner<=outer-1;{if(arr[inner]>arr[inner+{[arr[inner],arr[inner+1]]=}}}n^2空間1插入排序邏輯和冒泡類似，只不過沒采用挨個交換的邏輯，而是在一個已經(jīng)排好序的數(shù)組里，插入一個元素，讓它依然是有序的functionfunctioninsertSort(arr)forfor(leti=1iarr.lengthi++){//外循環(huán)從1開始，默認arr[0]for(letjij0j--){//ji,將arr[j]依次插入有序段中if(arr[j]<arr[j-1]){[arr[j],arr[j-1]]=[arr[j-}else}}}return}n^2空間1這格略高，使用了二分的思想?？梢运阕钪匾呐判蛩惴ù蟾啪褪钦乙粋€標志位，先遍歷一次，所有個頭比他矮的，都站左邊，比他個頭高的，都站右邊，遍歷一次，就把數(shù)組分成兩部分，然后兩遍的數(shù)組，遞歸執(zhí)行相同的邏輯functionfunction{if(arr.length<=1)returnarr;//遞歸}varleft=[],right=[],current=arr.splice(0,1);//注意splice后，數(shù)組長度少了一for(leti=0;i<arr.length;{if(arr[i]<current)left.push(arr[i])//放在左}elseright.push(arr[i])//}}returnquickSort(left).concat(current,quickSort(right));//遞}上面方便理解，額外占用空間,////原地functionquickSort1(arr,low=0,high=arr.length-1)ifif(low>=high)returnletleft=lowletright=highlettemp=arr[left]while(left<right)if(left<right&&temp<={right-}arr[left]=if(left<right&&temp>={left}arr[right]=}arr[left]=tempquickSort1(arr,low,left-1)quickSort1(arr,left+1,high)returnarr}n*logn空間不穩(wěn)定其他排序算法還有很多，桶排序，堆排序等，還有一個容易挨揍的排序constconstlist=[11,4,3,6,1,9,7,2,0]constnewList=[]list.forEach(item=>{setTimeout(function{newList.push(item)}},item*快排我們了解到，遞歸就是自己調(diào)用自己，形成一個調(diào)用棧，逐漸縮小目標，到達截止條件返回執(zhí)行的邏輯，talkischeap數(shù)組打平（扁平化ArrayAtotype.flat=function(){vararr=[];this.forEach((item,idx)=>{if(Array.isArray(item))arr=arr.concat(item.flat());//遞歸去處理數(shù)組}else }return //遞歸出}arr=爬有一樓梯共10級，剛開始時你在第一級，若每次只能跨上一級或二級，要走上第10級，共有多少種走法？其實就是個斐波那契數(shù)列，，只有兩種方式從第9層上一級，或者從第8級上二級，9和8又各自又兩種情況最后推到3級解題，的兩種方式1和 是固定的次functionfunction{if(n===0)return}elseif(n<{return}elsereturnstairs(n-1)+stairs(n-}}查找比較簡單，我們先來看一個經(jīng)典的二分查找有點類似幸運52的猜價格，比如讓你在1和1000個數(shù)字，挨個猜是很蠢的，要先猜500，如果大了，那就是0~500，每次問題減半，很快就能查到functionfunctionbinarySearch(arr,{varlow=high=arr.length-1,while(low<=high)mid=Math.floor((low+high)/2);if(target===arr[mid]){return`找到了${target},在第${mid+1}個}if(target>{low=mid+}elseif(target<arr[mid])highhigh=mid-}}return-}functionfunctionbinarySearch1(arr,target,low=0,high=arr.length-{constn=Math.floor((low+high)/2);constcur=arr[n];if(cur===target)return`找到了${target},在第${n+1}個}elseif(cur>target)returnbinarySearch1(arr,target,low,n-}elseif(cur<target)return}return-}隊棧classclassStack{this.itemspush(item)}poppop()return}size()return}clear()this.items=}}搜索插入移除經(jīng)典案例：括號匹配，html匹配，表達式計functionfunctionisBalance(symbol){conststack=newStack()constleft='{('constright='})'letpopValuelettag=constmatch=function(popValue,current)if(left.indexOf(popValue)!=={tag=}}for(leti=0;i<symbol.length;i++){if(left.includes(symbol[i])){}elseif{popValue=stack.pop()match(popValue,symbol[i])}}return}鏈有點像火車，車廂和車廂之間，有點是可以隨時替換車廂，react架構的?ber，就是從樹變成了鏈表，能夠讓di?任務隨時中斷classlement=elementthis.next=null}}LinkedList{construthis.head=nullthis.length=0}constnode=newif(this.headnull //插入第一個鏈this.head=}elsethis.current=while(this.current.next //找到最后一個節(jié)this.current=}this.current.next=}}//移除指定位置元removeAt(position)if(position>-1&&position<{letpreviousletindex=0if(position0 //如果是第一個鏈表的話,this.head=}elsethis.current=while(index<position){//循環(huán)找到當前要刪previous=this.currentthis.current=this.current.next}previous.next=}}}//insert(position,{constnode=newNode(element)letindex=0letcurrent,previousif(position>-1&&position<this.length+{if(position0在鏈表current=this.headthis.head=nodethis.head.next=current}elsecurrent=while(index<position){//同removeAt邏輯,找到previous=currentcurrent=current.next}previous.next= //在目標位node.next=}}}鏈表中是否含有某個元素如果有的話返回相應位置無的話返回-1indexOf(element){letindex=0this.current=this.headwhile(index<this.length)if(this.current.element==={return}this.current=this.current.next}return-}//移除某元remove(element)constposition=this.indexOf(element)}//獲取大size()return}//獲取最開頭的鏈getHead{return}//是否為isEmpty()returnthis.length===}//打印鏈表元log()this.current=letstr=this.current.elementwhile(this.current.next){this.current=str=str+''+}returnstr}}//測試用varlinkedList=newLinkedList() //'5101520' //'515linkedList.insert(1,10)時間復雜度搜索插入移除集其實就是es6的set，特點就classSet{this.items}has(value)return}add(value)if{this.items[value]=valuereturntrue}return}remove(value)if{deletethis.items[value]return}return}getsize()return}getvalues()return}}constset=newSet()consoleconsole.log(set.values)//["1"]console.log(set.has(1))//trueconsole.log(set.size)//1console.log(set.values)//["1","2"]console.log(set.has(2))//trueconsole.log(set.size)//2console.log(set.values)//["2"]console.log(set.values)//[]哈希哈西其實就是js里的對象，它在實際的鍵值和存入的哈希值之間存在一層映射。如下例子classclassHashTable{{this.items}put(key,value)consthash=this.keyToHash(key)this.items[hash]=value}get(key)return}remove(key)delete}{lethashforfor(leti=0;i<key.length;i++){hash+=key.charCodeAt(i)}hash=hash%37//為了避免hash的值過大returnhash}}letkkb=newHashTable()kkb.put('name','kaikeba')kkb.put('age',kkb.put('best','大圣老師console.log(kkb.get('name'))console.log(kkb.get('best'))哈希的問題也很明顯，比如兩個數(shù)的hash值一樣的時候，會發(fā)生碰撞，可以用鏈表的方式來解(重復的值存在鏈表里)這些V8幫我們處理的樹我們?yōu)g覽?的dom就是經(jīng)典的樹結構根節(jié)點:內(nèi)部節(jié)點:在它上面還有其它內(nèi)部節(jié)點或者葉節(jié)點的節(jié)點葉節(jié)點::<div<divfunctionwalk(node,func=()=>{}){if(nodeinstanceofwindow.Node){_walk(node,}return}function_walk(node,func){if(func(node)!==false){node=node.firstChild;while(node){_walk(node,node=}}} node=>{console.log(node)動態(tài)規(guī)劃是一種常見的「算法設計技巧」，并沒有什么高深莫測，至于各種高大上的術語，那是嚇唬別人用的，只要你親自體驗幾把，這些名詞的含義其實顯而易見，再簡單不過了。至于為什么最終的解法看起來如此精妙，是因為動態(tài)規(guī)劃遵循一套固定的流程：遞歸的暴力解法->帶備忘錄的遞歸解法->非遞歸的動態(tài)規(guī)劃解法。這個過程是層層遞進的解決問題的過程，你如果沒有前面的鋪墊，直接看最終的非遞歸動態(tài)規(guī)劃解法，當然會覺得牛而不可及了。舉個小栗子，那契數(shù)暴力遞歸functionfunctionif(n==1||n==2)return1returnfib(n-1)+fib(n-2)}遞歸調(diào)用很復雜，比如?b(18)左邊遞歸算法的時間復雜度怎么計算？子問題個數(shù)乘以解決一個子問題需要的時間。子問題個數(shù)，即遞歸樹點的總數(shù)。顯然二叉樹節(jié)點總數(shù)為指數(shù)級別，所以子問題個數(shù)為O(2^n)。解決一個子問題的時間，在本算法中，沒有循環(huán)，只有f(n1f(n2一個加法操作，時間為O(1)。所以，這個算法的時間復雜度為O(2^n)，指數(shù)級別，?；旧?0，40，newcodegit:(master)?nodefib:中間明確了問題，其實就已經(jīng)把問題解決了一半。即然耗時的原因是重復計算，那么我們可以造一個「備忘錄」，每次算出某個子問題的答案后別急著返回，先記到「備忘錄」里再返回；每次遇到一個子問題先去「備忘錄」里查一查，如果發(fā)現(xiàn)之前已經(jīng)解決過這個問題了，直接把答案拿出來用，不要再耗時去計算了。一般使用一個數(shù)組充當這個「備忘錄」，當然你也可以使用哈希表（字典）fibfib(n){letmemo=[]returnhelper(memo,}functionfunctionn){if(n==1||return}//if(memo[n])returnmemo[n]=helper(memo,n-1)+helper(memo,n-2)returnmemo[n]}遞歸算法的時間復雜度怎么算？子問題個數(shù)乘以解決一子問題個數(shù)，即圖點的總數(shù)，由于本算法不存在冗余計算，子問題就是f(1),f(2),f(3)...f(20)，數(shù)量和輸入規(guī)模n=20成正比，所以子問題個數(shù)為O(n)。解決一個子問題的時間，同上，沒有什么循環(huán)，時間 O(1)所以，本算法的時間復雜度 O(n)。比起暴力算法，是降維打擊至此，帶備忘錄的遞歸解法的效率已經(jīng)和動態(tài)規(guī)劃一樣了。實際上，這種解法和動態(tài)規(guī)劃的思想已經(jīng)差不多了，只不過這種方法叫做「自頂向下」，動態(tài)規(guī)劃叫做「自底向上」。啥叫「自頂向下」？注意我們剛才畫的遞歸樹（或者說圖），是從上向下延伸，都是從一個規(guī)模較大的原問題比如說(2)，向下逐漸分解規(guī)模，直到f(1)和(2)觸底，然后逐層返回答案，這就叫「自頂向下」。啥叫「自底向上」？反過來，我們直接從最，最簡單，問題規(guī)模最小的f(1)和f(2)開始往上推，直到推到我們想要的答案(2)，這就是動態(tài)規(guī)劃的思路，這也是為什么動態(tài)規(guī)劃一般都脫離了遞歸，而是由循環(huán)迭代完成計算。動態(tài)規(guī)劃我們可以把這個「備忘錄」獨立出來成為一張表，就叫做Ptable吧，在這張表上完成「自底向上」的推算豈不美哉！那fib(n){let=dp[1]=dp[2]=for(leti=3;i<=n;{dp[i]=dp[i-1]+dp[i-}動態(tài)規(guī)劃找再舉個找零的小栗子，:假1,5,10,20,50,100的4[1,1,1,需4個5需1個[20,10,5,需////找classeType=changeTypethis.cache=}makeChange{letmin=[]if(!amount){return}if(this.cache[amount //讀緩return}for(le