国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

JAVASCRIPT算法（3）

Miyang / 524人閱讀

摘要：首先是鏈表的定義語法搞錯了。分析本題與編程之美上的從無頭單鏈表中刪除節點類似。但是如果節點是尾節點時，該方法就行不通了。分析非遞歸的算法很簡單，用三個臨時指針在鏈表上循環一遍即可。遞歸算法是先逆轉下一個節點，再逆轉當前節點。

鏈接描述## 面試前準備了Promise的一種實現（大致理解和寫出來），二叉樹的構建，刪除，查找，插入，快排的非遞歸，準備了蠻多的吧，但是沒考慮鏈表。然后考個鏈表的反轉，其實很簡單，只不過有點懵，比我想的稍微難了點，然后這種考慮算法的實現而忽略了特殊情況的考慮，雖然我確定我能寫出來，但是在那段懵的時間沒有。后來看到了我朋友寫的鏈表面試題，鏈接在此。

我朋友是做Android開發的，以java的形式舉了幾個例子。我是眼高手低，還是練練javascript的形式吧。

首先是鏈表的定義
/*class Node{ //語法搞錯了。
constructor(val){
this.val= val;
this.next = null;
}
}*/
function Node(val){
this.val = val;
this.next = null;
}

題目描述：給定單鏈表中需要刪除的節點（不是尾節點），在 O(1) 時間刪除該節點。

分析：本題與《編程之美》上的「從無頭單鏈表中刪除節點」類似。主要思想都是「貍貓換太子」，即用下一個節點數據覆蓋要刪除的節點，然后刪除下一個節點。但是如果節點是尾節點時，該方法就行不通了。

function deleteNode(node){
 if(node==null||node.next==null) return ;
 node.val = node.next.val;
 node.next = node.next.next;
}

題目描述：輸出一個單鏈表的逆序反轉后的鏈表。

分析：非遞歸的算法很簡單，用三個臨時指針 prev、cur、next 在鏈表上循環一遍即可。遞歸算法是先逆轉下一個節點，再逆轉當前節點。

有點傷心的題目啊，其實還是蠻簡單的，就是在改變next的指向的時候，保留next指向的節點。

function reverseByLoop(head){
     if(head == null || head.next == null) return head;
     var pre = null,
         next;
     while(head!=null){
       next = head.next;
       head.next = pre;
       pre = head;
       head = next;
     }
     return pre;
}

function reverseByRecursion(head){
  if(head==null||head.next ==null) return head;
  //遞歸的好難理解。。
  var headOfNext = reverseByRecursion(head.next);
  head.next.next = head;
  head.next = null;
  return headOfNext;
  
}

遞歸有一種給我一個支點和足夠長的棍，我就能翹起地球一樣的感覺。
比如原鏈表是這樣的結構A->B->C->D->E.
既然這個function的目的是把鏈表倒序，那么如果我調用reverseByRecursion(B),
那么返回的結果一定是E,并且E->D->C->B.
現在我手中還有A，A->B。所以為了形成E->D->C->B->A, 只需要把B指向A,然后A指向NULL. 所以就是后續操作了。

那么還需要驗證臨界情況，即最里面一層執行的狀態能否達成逆轉鏈表的效果。
調用棧如下
reverseByRecursion(E)->return E;
reverseByRecursion(D)-> D.next.next=D;=>E->D D.next=NULL; return E; E->D->NULL
reverseByRecursion(C)-> C.next.next=C;=>D.next=C C.next=NULL; return E;=>E->D->C->NULL
reverseByRecursion(B)
reverseByRecursion(A)

先這樣吧。果然有點眼高手低。

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

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

相關文章

  • 優秀程序員都應該學習的 GitHub 上開源的數據結構與算法項目

    摘要：強烈推薦上值得前端學習的數據結構與算法項目，包含圖的演示過程與視頻講解。該倉庫包含了多種基于的算法與數據結構，提供進一步閱讀的解釋和鏈接。數據結構和算法必知必會的個代碼實現。 showImg(https://segmentfault.com/img/bVbvpYZ); 前言 算法為王。想學好前端，先練好內功，內功不行，就算招式練的再花哨，終究成不了高手；只有內功深厚者，前端之路才會走得...

    cheukyin 評論0 收藏0

  • JavaScript深入淺出第3課：什么是垃圾回收算法？

    摘要：摘要是如何回收內存的深入淺出系列深入淺出第課箭頭函數中的究竟是什么鬼深入淺出第課函數是一等公民是什么意思呢深入淺出第課什么是垃圾回收算法最近垃圾回收這個話題非常火，大家不能隨隨便便的扔垃圾了，還得先分類，這樣方便對垃圾進行回收再利用。 摘要： JS是如何回收內存的？ 《JavaScript深入淺出》系列： JavaScript深入淺出第1課：箭頭函數中的this究竟是什么鬼？ Jav...

    AaronYuan 評論0 收藏0

  • 常用排序算法之JavaScript實現

    摘要：代碼實現六堆排序算法簡介堆排序是指利用堆這種數據結構所設計的一種排序算法。九計數排序算法簡介計數排序是一種穩定的排序算法。計數排序不是比較排序，排序的速度快于任何比較排序算法。 贊助我以寫出更好的文章，give me a cup of coffee? 2017最新最全前端面試題 1、插入排序 1）算法簡介 插入排序（Insertion-Sort）的算法描述是一種簡單直觀的排序算法。它...

    jerry 評論0 收藏0

  • 深入淺出 JavaScript 的 Array.prototype.sort 排序算法

    摘要：快速排序是不穩定的排序算法。瀏覽器的實現不同有什么影響排序算法不穩定有什么影響舉個例子某市的機動車牌照拍賣系統，最終中標的規則為按價格進行倒排序相同價格則按照競標順位即價格提交時間進行正排序。 本文要解決的問題 1、找出 Array.prototype.sort 使用的什么排序算法 2、用一種直觀的方式展示 Array.prototype.sort 的時間復雜度，看看它有多快？ 3、...

    itvincent 評論0 收藏0

  • 【你該懂一點Javascript算法系列】之單源最短路徑 - Dijkstra算法

    摘要：算法系列單源最短路徑算法迪杰斯特拉算法是由荷蘭計算機科學家狄克斯特拉于年提出的，因此又叫狄克斯特拉算法。是從一個頂點到其余各頂點的最短路徑算法，解決的是有向圖中最短路徑問題。 Javascript算法系列 - 單源最短路徑 - Dijkstra算法 迪杰斯特拉算法是由荷蘭計算機科學家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是從一個頂點到其余各頂點的最短路徑算法，解決的是有...

    SoapEye 評論0 收藏0

  • JavaScript算法 ,Python算法,Go算法,java算法,系列之歸并排序

    摘要：常見的內部排序算法有插入排序希爾排序選擇排序冒泡排序歸并排序快速排序堆排序基數排序等。用一張圖概括歸并排序英語，或，是創建在歸并操作上的一種有效的排序算法，效率為。 常見的內部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數排序等。用一張圖概括： showImg(https://segmentfault.com/img/bVNwuO?w=966&h=...

    zhou_you 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<