摘要：算法第一章學(xué)習(xí)筆記實現(xiàn)更多內(nèi)容目標總結(jié)本書主要內(nèi)容，相應(yīng)算法使用來模仿實現(xiàn)在計算機科學(xué)領(lǐng)域，我們用算法這個詞來描述一種有限確定有效的并適合用計算機程序來實現(xiàn)的解決問題的方法。

更多內(nèi)容

目標：總結(jié)本書主要內(nèi)容，相應(yīng)算法使用js來模仿實現(xiàn)

在計算機科學(xué)領(lǐng)域，我們用算法這個詞來描述一種有限、確定、有效的并適合用計算機程序來實現(xiàn)的解決問題的方法。
我們關(guān)注的大多數(shù)算法都需要適當(dāng)?shù)亟M織數(shù)據(jù)，而為了組織數(shù)據(jù)就產(chǎn)生了數(shù)據(jù)結(jié)構(gòu)

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

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

首先定義要實現(xiàn)的隊列、棧的API

數(shù)組方式

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

實現(xiàn)

隊列的數(shù)組方式實現(xiàn)，并模擬可迭代功能

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

棧的數(shù)組方式實現(xiàn)，并模擬可迭代功能

 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

鏈表方式實現(xiàn)

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

在這個定義中，結(jié)點是一個可能含有任意類型數(shù)據(jù)的抽象實體，它所包含的指向結(jié)點的應(yīng)用顯示了它在構(gòu)造鏈表之中的作用。

結(jié)點表示:

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

構(gòu)造鏈表：

在表頭插入結(jié)點

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

從表頭刪除結(jié)點

    first=first.next

從表尾插入結(jié)點

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

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

棧的鏈表實現(xiàn)

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

function Stack() {
    this.count = 0 //元素數(shù)量
    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

隊列的鏈表實現(xiàn)

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

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

在結(jié)構(gòu)化存儲數(shù)據(jù)集時，鏈表是數(shù)組的一種重要的替代方式，兩者都非?；A(chǔ)，常常被稱為順序存儲和鏈式存儲。

threeSum問題分析

問題描述：

假設(shè)所有整數(shù)都不相同，統(tǒng)計一個數(shù)組中所有和為0的三整數(shù)元組的數(shù)量

最基本的實現(xiàn),暴力算法

function threesum(arr){
    var N=arr.length
    var count=0
    for(var i=0;i
分析：
執(zhí)行最頻繁的指令決定了程序執(zhí)行的總時間，對上面的threesum算法，最頻繁的部分就是if語句判斷，它套在三個for循環(huán)內(nèi)，對于給定的N，if語句執(zhí)行次數(shù)為N*(N-1)*(N-2)/6=N^3/6-N^2/2+N/3,當(dāng)N很大時，首項后的其他項都相對較小可以忽略，所以if語句的執(zhí)行次數(shù)約等于N^3/6,表示為(~N^3/6)
所以暴力算法的threesum執(zhí)行用時的增長數(shù)量級為N^3
優(yōu)化
學(xué)習(xí)程序的增長數(shù)量級的一個重要動力是為了幫助我們?yōu)橥粋€問題設(shè)計更快的算法
改進后的算法的思路是：當(dāng)且僅當(dāng)-( a[i]+a[j] )在數(shù)組中( 不是a[i]也不是a[j] )時,整數(shù)對( a[i]和a[j] )為某個和為0的三元組的一部分。要解決這個問題，首先對數(shù)組進行排序(為二分查找做準備),然后對數(shù)組中的每個a[i]+a[j],使用二分查找算法對-(a[i]+a[j])進行二分查找，如果結(jié)果為k，且k>j,則count加一。
下面中的代碼會將數(shù)組排序并進行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
}
增長數(shù)量級的分類

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

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

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

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

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


UF
說明



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


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


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


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


count()
連通分量的數(shù)量



我們看到，為解決動態(tài)連通性問題設(shè)計算法的任務(wù)轉(zhuǎn)化成了實現(xiàn)這份API，所有的實現(xiàn)都應(yīng)該
[x] 定義一種數(shù)據(jù)結(jié)構(gòu)表示已知的連接
[x] 基于此數(shù)據(jù)結(jié)構(gòu)實現(xiàn)高效的union()、find()、connected()、count()
我們用一個以觸點為索引的數(shù)組id[]作為基本數(shù)據(jù)結(jié)構(gòu)來表示所有分量，我們將使用分量中的某個觸點的名稱作為分量的標識符
一開始，我們有N個分量，每個觸點都構(gòu)成了一個只含有自己的分量，因此我們將id[i]的值設(shè)為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()是實現(xiàn)的重點,我們將討論三種不同的實現(xiàn)，它們均根據(jù)以觸點為索引的id[]數(shù)組來確定兩個觸點是否存在于相同的連通分量中
實現(xiàn)
quick-find算法
思想是:保證當(dāng)且僅當(dāng)id[p]==id[q]時，p和q是連通的。換句話說，在同一個連通分量中的所有觸點在id[]數(shù)組中的值都一樣。
    /** 
     * @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--
    }
復(fù)雜度分析:
find()操作很快，它只訪問id[]數(shù)組一次,但union()會整個掃描id[]數(shù)組
在union()中,find p、q會訪問2次數(shù)組，for循環(huán)及賦值操作會訪問數(shù)組 N+1 ~ N+（N-1）次。
所以union()方法訪問數(shù)組的次數(shù)在(2+N+1) ~(2+N+(N-1)) 即 N+3 ~ 2N+1 次之間
假設(shè)我們使用quick-union算法來解決動態(tài)連通性問題并最后只得到一個連通分量，則至少需要調(diào)用(N-1)次 union(),
即（N+3）（N-1） ~（2N+1）（N-1）次數(shù)組訪問
所以此算法的時間復(fù)雜度是平方級別的
quick-union算法
此算法的重點是提高union()方法的速度，它也是基于相同的數(shù)據(jù)結(jié)構(gòu)--以觸點作為索引的id[]數(shù)組，但我們賦予這些值的意義不同，我們需要用他們來定義更加復(fù)雜的數(shù)據(jù)結(jié)構(gòu):
每個觸點所對應(yīng)的id[]元素都是同一個分量中的另一個觸點的名稱（也可以說是它自己，即根觸點）--我們將這種聯(lián)系稱為鏈接。
    /** 
     * 找到根觸點，即分量的標識符
     * @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[]數(shù)組用父鏈接的形式表示了一片森林
復(fù)雜度分析：
一棵樹的大小是它的節(jié)點的數(shù)量，樹中一個節(jié)點的深度是它到根節(jié)點路徑上的鏈接數(shù)
quick-union算法的分析依賴于輸入的特點，find()訪問數(shù)組的次數(shù)為1加上給定的觸點所對應(yīng)的節(jié)點的深度的2倍。
在最好的情況下，find()只需要訪問數(shù)組1次就能夠得到當(dāng)前觸點所在分量的標識符
在最壞的情況下，find()需要1 + 2*(N-1) 即 2N-1 次數(shù)組訪問
如下圖所示

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

class UF {

    /**
     * 
     * @param {number} N 
     */
    constructor(N) {
        this.id = new Array(N).fill(0).map((x, index) => index)
        //各個根節(jié)點所對應(yīng)的分量的大小
        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--
    }

}

復(fù)雜度分析：

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

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