數據結構和算法類面試題javascript代碼實現

Dean 發(fā)布于2019-08-22 10:39 / 478人閱讀

摘要：正文面試題重建二叉樹題目輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹。前序遍歷序列為，中序遍歷序列，。確定了左右子樹后遞歸處理。方法方法面試題在時間刪除鏈表結點。

寫在前面

本文的題目均來自于劍指offer中的題目，題目序號保持了書中的題目序號，由于某些題目并不適合于javascript這種語言，所以這些題目就沒有寫在本篇博客中，因此會出現題目序號的中斷。

正文

面試題6：重建二叉樹
題目：輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果都不含重復的數字。前序遍歷序列為{1,2,4,7,3,5,6,8}，中序遍歷序列{4,7,2,1,5,3,8，6}。
分析：根據前序遍歷和中序遍歷的定義可知，前序遍歷中的第一個值就是根節(jié)點的值，而在中序遍歷中根節(jié)點的值是在左子樹的后面右子樹的前面，由于樹中沒有重復的值所以可以通過對中序遍歷進行一遍搜索來找到這個值，從而也可以確定這棵樹的左右子樹。確定了左右子樹后遞歸處理。
代碼實現

function node(data, left, right){  //用來表示一棵樹中的節(jié)點
  this.data = data;
  this.left = left;
  this.right = right;
  this.show = show;
}
function show(){
  return this.data;
} 

function rebuildBT(pre, mid){ //根據前序遍歷和中序遍歷重建這棵樹并且輸出頭節(jié)點
  var root; //保存頭結點
  var len = pre.length;
  if(len > 1){
    var data = pre[0]; //前序遍歷的第一個元素即樹的根節(jié)點
    for(var i = 0; i
面試題7：用兩個棧實現隊列
題目：用兩個棧實現一個隊列。隊列的聲明如下，請實現它的兩個函數appendTail和deleteHead，分別完成在隊列尾部插入節(jié)點和在隊列頭部刪除節(jié)點的功能。
分析：由于棧是一種先進后出的數據結構，且只能在棧頂來刪除數據，所以本題目的實現思路是先將隊列從頭到尾壓入棧中保存，如果要從尾部添加一個元素那么直接從棧頂壓入一個元素即可，如果是要從頭部刪除一個元素那么將隊列從棧1彈出保存到棧2，對棧2棧頂彈出一個元素再壓回棧1.
面試題目8：旋轉數組的最小數字
題目：把一個數組最開始的若干個元素搬到數組的末尾，稱之為一個數組的旋轉。輸入一個遞增排序的數組的一個旋轉，輸出旋轉數組的最小元素。例如旋轉數組{3,4,5,1,2}的最小值為1.
分析：直觀的方法是對整個數組進行一次遍歷，找出最小值。但是這種復雜對為o（n）的方法顯然不是最佳，因為我們這里沒有用到旋轉數組包含兩個已排序的子序列的特點。對于已排序的數組我們可以用二分法來進行查找，可以將時間復雜度降低為（logn），那么這里我們也可以用相似的思路來實現。
代碼實現：
function minNum(inputArr){
  //輸入為旋轉數組，利用二分法來查找最小元素
  var len = inputArr.length;
  var first=inputArr[0], last=inputArr[len-1], location, min;
  if(len > 2){
    location = Math.ceil(len/2)-1;
    var value = inputArr[location];
    if(value >last){//說明這個中間元素在前面的數組中,那么最小的元素它之后
      min = minNum(inputArr.slice(location));
    }else if(value <= last){//說明這個中間元素在后面的數組中，最小元素在它之前
      min = minNum(inputArr.slice(0,location+1));
    }
  }else if(len === 2){
    min = inputArr[0]>inputArr[1] ? inputArr[1] : inputArr[0];
  }else{
    min = inputArr[0];
  }
  return min;
}
面試題9：斐波那契數列
前言：如果需要多次計算相同的問題通常可以選擇用遞歸或者循環(huán)來實現，遞歸是在一個函數內部調用自身，馴海則是通過設置計算值的初始值和終止條件在一個范圍內重復計算。通常遞歸方法的代碼會比較簡潔，但是它也會有顯著的缺點，由于每次遞歸都是一次函數的調用，所以遞歸效率較低；同時遞歸中有很多運算是重復的（分解的小問題存在重疊的部分），這會對性能造成影響；最重要的是遞歸還有可能造成調用棧的溢出。那么這個時候我們就可以適當地考慮一下用循環(huán)的方法來解決。
題目一：寫一個函數，輸入n求斐波那契數列的第n項。首先得知道斐波那契數列的第n項是如何定義的。定義其實就是如下面方法1函數描述。很明顯使用了遞歸，當n很大的時候運行效率低下不說還會造成調用棧溢出，那么我么用一種循環(huán)的方法來實現一下，如方法2。
//方法1
function fn(n){
 if(n <= 0){
     return 0;
 }else if(n == 1){
     return 1
 }else{
     return fn(n-1)+fn(n-2);
 }
}

//方法2
function fn(n){
  var result, r1, r2;
  if(n<=0){
    return 0;
  }else if(n == 1){
    return 1;
  }else{
    r1 = 1;
    r2 = 0;
    for(var i = 2; i<=n; i++){
      result = r1 + r2;
      r2 = r1;
      r1 = result;
      
    }
  }
  return result;
}

 

面試題13：在O（1）時間刪除鏈表結點。
題目：給定單向鏈表的頭指針和一個結點指針，定義一個函數在O(1)時間刪除該節(jié)點。
分析：在單鏈表中刪除一個結點，直觀的思路就是從鏈表頭節(jié)點開始，順序遍歷查找要刪除的節(jié)點，并在鏈表中刪除該節(jié)點。但是這樣的話時間復雜度就為o(n)。所以我們要換一種方法來做，刪除一個結點是不是必須要已知這個節(jié)點之前的節(jié)點呢？答案是否定的。由于這里已知了刪除節(jié)點的指針，那么我們可以方便地得到下一個節(jié)點，我們把下一個節(jié)點的內容復制到需要刪除的節(jié)點上覆蓋原有的內容，再把下一個節(jié)點刪除，這就相當于把當前需要刪除的節(jié)點刪除掉了。

GPU云服務器云服務器字符串算法面試題 javascript必問面試題面試c語言算法編程題棧和隊列面試題

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/91017.html

前端資源系列（4）-前端學習資源分享&前端面試資源匯總

摘要：特意對前端學習資源做一個匯總，方便自己學習查閱參考，和好友們共同進步。特意對前端學習資源做一個匯總，方便自己學習查閱參考，和好友們共同進步。本以為自己收藏的站點多，可以很快搞定，沒想到一入匯總深似海。還有很多不足&遺漏的地方，歡迎補充。有錯誤的地方，還請斧正... 托管: welcome to git，歡迎交流，感謝star 有好友反應和斧正，會及時更新，平時業(yè)務工作時也會不定期更...

princekin 2019-08-20 11:28 評論0 收藏0
前端面試題總結（js、html、小程序、React、ES6、Vue、算法、全棧熱門視頻資源）

摘要：并總結經典面試題集各種算法和插件前端視頻源碼資源于一身的文檔，優(yōu)化項目，在瀏覽器端的層面上提升速度，幫助初中級前端工程師快速搭建項目。本文是關注微信小程序的開發(fā)和面試問題，由基礎到困難循序漸進，適合面試和開發(fā)小程序。并總結vue React html css js 經典面試題集各種算法和插件、前端視頻源碼資源于一身的文檔，優(yōu)化項目，在瀏覽器端的層面上提升速度，幫助初中級前端工程師快...

pumpkin9 2019-08-23 17:12 評論0 收藏0
前端面試題總結（js、html、小程序、React、ES6、Vue、算法、全棧熱門視頻資源）

摘要：并總結經典面試題集各種算法和插件前端視頻源碼資源于一身的文檔，優(yōu)化項目，在瀏覽器端的層面上提升速度，幫助初中級前端工程師快速搭建項目。本文是關注微信小程序的開發(fā)和面試問題，由基礎到困難循序漸進，適合面試和開發(fā)小程序。并總結vue React html css js 經典面試題集各種算法和插件、前端視頻源碼資源于一身的文檔，優(yōu)化項目，在瀏覽器端的層面上提升速度，幫助初中級前端工程師快...

Carson 2019-07-31 10:21 評論0 收藏0
前端面試題總結（js、html、小程序、React、ES6、Vue、算法、全棧熱門視頻資源）

摘要：并總結經典面試題集各種算法和插件前端視頻源碼資源于一身的文檔，優(yōu)化項目，在瀏覽器端的層面上提升速度，幫助初中級前端工程師快速搭建項目。本文是關注微信小程序的開發(fā)和面試問題，由基礎到困難循序漸進，適合面試和開發(fā)小程序。并總結vue React html css js 經典面試題集各種算法和插件、前端視頻源碼資源于一身的文檔，優(yōu)化項目，在瀏覽器端的層面上提升速度，幫助初中級前端工程師快...

muzhuyu 2019-07-01 12:43 評論0 收藏0