摘要：算法第一章學習筆記實現更多內容目標總結本書主要內容，相應算法使用來模仿實現在計算機科學領域，我們用算法這個詞來描述一種有限確定有效的并適合用計算機程序來實現的解決問題的方法。

更多內容

目標：總結本書主要內容，相應算法使用js來模仿實現

在計算機科學領域，我們用算法這個詞來描述一種有限、確定、有效的并適合用計算機程序來實現的解決問題的方法。
我們關注的大多數算法都需要適當地組織數據，而為了組織數據就產生了數據結構

原書所有代碼是基于JAVA語法的，這里，我們使用js來實現所有算法邏輯

隊列是一種先進先出的集合類型，棧是一種先進后出的集合類型

首先定義要實現的隊列、棧的API

數組方式

由于JS語言的特殊性，采用數組的方式來實現隊列、棧是非常容易的,js中數組本來就提供了從頭部插入、刪除元素，從尾部插入、刪除元素的功能。這里只需要簡單的封裝一下(js的弱類型特點，不需要像JAVA那樣采用泛型來聲明可以儲存任意類型的數據，同時，js中數組是不定長的，可以動態擴展)

實現

隊列的數組方式實現，并模擬可迭代功能

function Queue() {
    this.container = []
}
Queue.prototype.enqueue = function (ele) {
    this.container.push(ele)
}
Queue.prototype.dequeue = function () {
    return this.container.shift()
}
Queue.prototype.isEmpty = function () {
    return !this.container.length
}
Queue.prototype.size = function () {
    return this.container.length
}

Queue.prototype.iterator = function () {
    var container = this.container
    var current = 0
    return {
        hasNext: function () {
            return current !== container.length
        },
        next: function () {
            return container[current++]
        }
    }
}

用例:
var Qu = new Queue()
Qu.enqueue("to")
Qu.enqueue("be")
Qu.enqueue("or")
Qu.enqueue("not")
Qu.dequeue()
var iterator = Qu.iterator()
while (iterator.hasNext()) {
    console.log(iterator.next())
}
輸出:
be
or
not

棧的數組方式實現，并模擬可迭代功能

 class Stack {

    constructor() {
        this.container = []
    }

    push(ele) {
        this.container.unshift(ele)
    }

    pop() {
        return this.container.shift()
    }

    isEmpty() {
        return !this.container.length
    }
    size() {
        return this.container.length
    }

    iterator() {
        const container = this.container
        let current = 0
        return {
            hasNext: function () {
                return current !== container.length
            },
            next: function () {
                return container[current++]
            }
        }
    }

}
用例:
var St = new Stack()
Stack.push("to")
Stack.push("be")
Stack.push("or")
Stack.push("not")
Stack.pop()
var iterator = Stack.iterator()
while (iterator.hasNext()) {
    console.log(iterator.next())
}
輸出:
or
be
to

鏈表方式實現

鏈表是一種遞歸的數據結構，它或者為空(null)，或者是指向一個結點(node)的引用，該結點含有一個泛型的元素和一個指向另一個鏈表的引用。

在這個定義中，結點是一個可能含有任意類型數據的抽象實體，它所包含的指向結點的應用顯示了它在構造鏈表之中的作用。

結點表示:

    function Node(){
        this.item=null
        this.next=null
    }

構造鏈表：

在表頭插入結點

    var oldFirst=first
    first=new Node()
    first.next=oldFirst

從表頭刪除結點

    first=first.next

從表尾插入結點

    var oldlast=last
    lst=new Node()
    oldlast.next=last

實現任意插入和刪除操作的標準解決方案是雙向鏈表，其中每個結點都含有兩個鏈接，分別指向不同的方向

棧的鏈表實現

function Node(item) {
    this.item = item
    this.next = null
}

function Stack() {
    this.count = 0 //元素數量
    this.first = null //指向棧頂
}

Stack.prototype.isEmpty = function () {
    return this.first == null
}
Stack.prototype.size = function () {
    return this.count
}
Stack.prototype.push = function (ele) {
    var oldfirst = this.first
    var newnode = new Node(ele)
    newnode.next = oldfirst
    this.first = newnode
    this.count++
}
Stack.prototype.pop = function () {
    var ele = this.first.item
    this.first = this.first.next
    this.count--
    return ele
}
Stack.prototype.iterator = function () {
    var firstnode = this.first
    var count = this.count
    return {
        hasNext: function () {
            return  count
        },
        next: function () {
            var ele=firstnode.item
            firstnode=firstnode.next
            count--
            return ele
        }
    }
}
用例：
var stack=new Stack()
stack.push("to")
stack.push("be")
stack.push("or")
stack.push("not")
stack.push("to")
stack.push("be")
console.log(stack.size())
var iterator=stack.iterator()
while(iterator.hasNext()){
    console.log(iterator.next())
}
輸出：
6
be
to
not
or
be
to

隊列的鏈表實現

將鏈表表示為一條從最早插入的元素到最近插入的元素的鏈表，實例變量first指向隊列的開頭，last指向隊列的結尾。這樣，要講一個元素入列，就將它添加到表尾，要將一個元素出列，就刪除表頭的結點.

function Node(item) {
    this.item = item
    this.next = null
}

class Queue {

    constructor() {
        this.first = null
        this.last = null
        this.count = 0
    }

    isEmpty() {
        return this.first == null
    }
    size() {
        return this.count
    }
    enqueue(item) {
        const oldlast = this.last
        const last = new Node(item)
        this.last = last
        if (this.isEmpty()) {
            this.first = last
        } else {
            oldlast.next = last
        }
        this.count++
    }
    dequeue() {
        const ele = this.first.item
        this.first = this.first.next
        if (this.isEmpty()) {
            this.last = null
        }
        this.count--
        return ele
    }
    iterator() {
        let firstnode = this.first
        let count = this.count
        return {
            hasNext: function () {
                return count
            },
            next: function () {
                var ele = firstnode.item
                firstnode = firstnode.next
                count--
                return ele
            }
        }
    }
}
用例:
const queue=new Queue()
queue.enqueue("to")
queue.enqueue("be")
queue.enqueue("or")
queue.enqueue("not")
queue.enqueue("to")
queue.enqueue("be")
queue.dequeue()
console.log(queue.size())
const iterator=queue.iterator()
while(iterator.hasNext()){
    console.log(iterator.next())
}

輸出:
5
be
or
not 
to
be

在結構化存儲數據集時，鏈表是數組的一種重要的替代方式，兩者都非常基礎，常常被稱為順序存儲和鏈式存儲。

threeSum問題分析

問題描述：

假設所有整數都不相同，統計一個數組中所有和為0的三整數元組的數量

最基本的實現,暴力算法

function threesum(arr){
    var N=arr.length
    var count=0
    for(var i=0;i
分析：
執行最頻繁的指令決定了程序執行的總時間，對上面的threesum算法，最頻繁的部分就是if語句判斷，它套在三個for循環內，對于給定的N，if語句執行次數為N*(N-1)*(N-2)/6=N^3/6-N^2/2+N/3,當N很大時，首項后的其他項都相對較小可以忽略，所以if語句的執行次數約等于N^3/6,表示為(~N^3/6)
所以暴力算法的threesum執行用時的增長數量級為N^3
優化
學習程序的增長數量級的一個重要動力是為了幫助我們為同一個問題設計更快的算法
改進后的算法的思路是：當且僅當-( a[i]+a[j] )在數組中( 不是a[i]也不是a[j] )時,整數對( a[i]和a[j] )為某個和為0的三元組的一部分。要解決這個問題，首先對數組進行排序(為二分查找做準備),然后對數組中的每個a[i]+a[j],使用二分查找算法對-(a[i]+a[j])進行二分查找，如果結果為k，且k>j,則count加一。
下面中的代碼會將數組排序并進行N*(N-1)/2次二分查找，每次查找所需的時間都和logN成正比，因此總的運行時間和N^2logN成正比。
//二分查找
function binarySearch(key, arr) {
    var start = 0
    var end = arr.length - 1
    while (start <= end) {
        var mid = start + Math.floor((end - start) / 2)
        if (key < arr[mid]) {
            end = mid - 1
        } else if (key > arr[mid]) {
            start = mid + 1
        } else {
            return mid
        }
    }
    return -1
}

function threesum(arr) {
    var N = arr.length
    var count = 0
    arr = arr.sort(function (a, b) {
        return a > b ? 1 : -1
    })
    for (var i = 0; i < N; i++) {
        for (var j = i + 1; j < N; j++) {
            if (binarySearch(-arr[i] - arr[j], arr) > j) {
                count++
            }
        }
    }
    return count
}
增長數量級的分類

案例研究:union-find算法
動態連通性問題
首先我們詳細說明一下問題
問題的輸入是一列整數對，對于一對整數p,q,如果p,q不相連，則將p,q連接
所謂的相連:

[x] 自反性: p與p是相連的
[x] 對稱性: 若p與q是相連的,則q與p是相連的
[x] 傳遞性: 若p與q是相連的,且q和r相連，則p與r是相連的

我們假設相連的整數構成了一個“集合”,對于新的連接，就是在將新的元素加入“集合”來構成更大的“集合”,若判斷p,q是否相連，只要判斷p,q是否在同一個“集合”中即可。

這里我們應用動態連通性來處理計算機網絡中的主機之間的連通關系
輸入中的整數表示的可能是一個大型計算機網絡中的計算機，而整數對則表示網絡中的連接，這個程序能夠判定我們是否需要在p和q之間架設一條新的連接來通信，或是我們可以通過已有的連接在兩者之間建立通信線路。

這里我們使用網絡方面的術語，將輸入的整數稱為觸點，將形成的集合稱為連通分量
分析
為了說明問題，我們設計一份API來封裝所需的基本操作:初始化、連接兩個觸點、判斷包含某個觸點的分量、判斷兩個觸點是否存在于同一個分量之中以及返回所有分量的數量


UF
說明



UF(N)
以整數標識（0到N-1）初始化N個觸點


union(p,q)
連接觸點p、q


find(p)
返回p所在分量的標識符


connected(p,q)
判斷p,q是否存在于同一個連通分量中


count()
連通分量的數量



我們看到，為解決動態連通性問題設計算法的任務轉化成了實現這份API，所有的實現都應該
[x] 定義一種數據結構表示已知的連接
[x] 基于此數據結構實現高效的union()、find()、connected()、count()
我們用一個以觸點為索引的數組id[]作為基本數據結構來表示所有分量，我們將使用分量中的某個觸點的名稱作為分量的標識符
一開始，我們有N個分量，每個觸點都構成了一個只含有自己的分量，因此我們將id[i]的值設為i。
class UF {

    /**
     * 
     * @param {number} N 
     */
    constructor(N) {
        this.id = new Array(N).fill(0).map((x, index) => index)
        this.count = 0
    }

    count(){
        return this.count
    }

    /**
     * 
     * @param {number} p 
     * @param {number} q 
     */
    connected(p,q){
        return this.find(p)===this.find(q)
    }

    /** 
     * @param {number} p 
     */
    find(p){

    }
    /**
     * 
     * @param {number} p 
     * @param {number} q 
     */
    union(p,q){

    }

}

find()和union()是實現的重點,我們將討論三種不同的實現，它們均根據以觸點為索引的id[]數組來確定兩個觸點是否存在于相同的連通分量中
實現
quick-find算法
思想是:保證當且僅當id[p]==id[q]時，p和q是連通的。換句話說，在同一個連通分量中的所有觸點在id[]數組中的值都一樣。
    /** 
     * @param {number} p 
     */
    find(p){
        return this.id[p]
    }

    /**
     * 
     * @param {number} p 
     * @param {number} q 
     */
    union(p,q){
        var pId=this.find(p)
        var qId=this.find(q)
        if(pId==qId) return
        this.id.forEach(x=>{
            if(id[x]==pId){
                id[x]==qId
            }
        })
        this.count--
    }
復雜度分析:
find()操作很快，它只訪問id[]數組一次,但union()會整個掃描id[]數組
在union()中,find p、q會訪問2次數組，for循環及賦值操作會訪問數組 N+1 ~ N+（N-1）次。
所以union()方法訪問數組的次數在(2+N+1) ~(2+N+(N-1)) 即 N+3 ~ 2N+1 次之間
假設我們使用quick-union算法來解決動態連通性問題并最后只得到一個連通分量，則至少需要調用(N-1)次 union(),
即（N+3）（N-1） ~（2N+1）（N-1）次數組訪問
所以此算法的時間復雜度是平方級別的
quick-union算法
此算法的重點是提高union()方法的速度，它也是基于相同的數據結構--以觸點作為索引的id[]數組，但我們賦予這些值的意義不同，我們需要用他們來定義更加復雜的數據結構:
每個觸點所對應的id[]元素都是同一個分量中的另一個觸點的名稱（也可以說是它自己，即根觸點）--我們將這種聯系稱為鏈接。
    /** 
     * 找到根觸點，即分量的標識符
     * @param {number} p 
     */
    find(p) {
        while (p !== this.id[p]) p = this.id[p]
        return p
    }

    /**
     * 
     * @param {number} p 
     * @param {number} q 
     */
    union(p, q) {
        let pRoot = this.find(p)
        let qRoot = this.find(q)
        if (pRoot == qRoot) return
        id[pRoot] = qRoot
        this.count--
    }

如圖所示：id[]數組用父鏈接的形式表示了一片森林
復雜度分析：
一棵樹的大小是它的節點的數量，樹中一個節點的深度是它到根節點路徑上的鏈接數
quick-union算法的分析依賴于輸入的特點，find()訪問數組的次數為1加上給定的觸點所對應的節點的深度的2倍。
在最好的情況下，find()只需要訪問數組1次就能夠得到當前觸點所在分量的標識符
在最壞的情況下，find()需要1 + 2*(N-1) 即 2N-1 次數組訪問
如下圖所示

對最壞的情況，處理N對整數所需的所有find()操作訪問數組的總次數為:
等差數列 (1+ 2N-1) *N /2 = N^2,即在最差的情況下，quick-union算的復雜度為平方級的
union()訪問數組的次數是兩次find()操作，(如果union中給定的兩個觸點在不同的分量還要加1)
由此，我們構造了一個最佳情況的輸入使得算法的運行時間是線性的，最差情況的輸入使得算法的運行時間是平方級的。
加權 quick-union算法 (控制樹的深度)
與其在union()中隨意將一顆樹連接到另一棵樹，我們現在會記錄每一顆樹的大小并總是將較小的樹連接到較大的樹上。

class UF {

    /**
     * 
     * @param {number} N 
     */
    constructor(N) {
        this.id = new Array(N).fill(0).map((x, index) => index)
        //各個根節點所對應的分量的大小
        this.sz = new Array(N).fill(1)
        this.count = 0
    }

    count() {
        return this.count
    }

    /**
     * 
     * @param {number} p 
     * @param {number} q 
     */
    connected(p, q) {
        return this.find(p) === this.find(q)
    }

    /** 
     * 找到根觸點，即分量的標識符
     * @param {number} p 
     */
    find(p) {
        while (p !== this.id[p]) p = this.id[p]
        return p
    }
    /**
     * 
     * @param {number} p 
     * @param {number} q 
     */
    union(p, q) {
        let pRoot = this.find(p)
        let qRoot = this.find(q)
        if (pRoot == qRoot) return
        //將小樹連接到大樹上
        if (sz[pRoot] < sz[qRoot]) {
            id[p] = qRoot
            sz[qRoot] += sz[pRoot]
        } else {
            id[q] = pRoot
            sz[pRoot] += sz[qRoot]
        }
        this.count--
    }

}

復雜度分析：

如圖所示，在最壞的情況下，其中將要被歸并的樹的大小總是相等的，它們均含有2^n個節點（樹的高度為n）,當我們歸并兩個2^n個節點的樹時，得到的樹的高度增加到n+1。
對于加權quick-union算法和N個觸點，在最壞的情況下，find() union()的運行時間的增長數量級為logN
加權quick-union算法處理N個觸點和M條連接時最多訪問數組cMlgN次，這與quick-find需要MN形成了鮮明對比
總結
通過《算法》第一章我學習了

[x] 基本的數據類型棧、隊列
[x] 通過數組、鏈表來構造隊列和棧
[x] 數組和鏈表是兩種基本的數據結構
[x] 時間復雜度的分析和常見的復雜度增長數量級
[x] 二分查找算法
[x] 對一個問題尋求解決方案時，要確定好基本的數據結構，好的數據結構是構造高效算法的前提
[x] 動態連通性問題
[x] 動態連通性問題的解決方案，并不斷優化算法