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

更多內(nèi)容

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

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

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

隊(duì)列是一種先進(jìn)先出的集合類型，棧是一種先進(jìn)后出的集合類型

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

數(shù)組方式

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

實(shí)現(xiàn)

隊(duì)列的數(shù)組方式實(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ù)組方式實(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

鏈表方式實(shí)現(xiàn)

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

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

結(jié)點(diǎn)表示:

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

構(gòu)造鏈表：

在表頭插入結(jié)點(diǎn)

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

從表頭刪除結(jié)點(diǎn)

    first=first.next

從表尾插入結(jié)點(diǎn)

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

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

棧的鏈表實(shí)現(xiàn)

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

function Stack() {
    this.count = 0 //元素?cái)?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

隊(duì)列的鏈表實(shí)現(xiàn)

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

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)化存儲(chǔ)數(shù)據(jù)集時(shí)，鏈表是數(shù)組的一種重要的替代方式，兩者都非常基礎(chǔ)，常常被稱為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。

threeSum問(wèn)題分析

問(wèn)題描述：

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

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

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

案例研究:union-find算法
動(dòng)態(tài)連通性問(wèn)題
首先我們?cè)敿?xì)說(shuō)明一下問(wèn)題
問(wèn)題的輸入是一列整數(shù)對(duì)，對(duì)于一對(duì)整數(shù)p,q,如果p,q不相連，則將p,q連接
所謂的相連:

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

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

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

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


UF
說(shuō)明



UF(N)
以整數(shù)標(biāo)識(shí)（0到N-1）初始化N個(gè)觸點(diǎn)


union(p,q)
連接觸點(diǎn)p、q


find(p)
返回p所在分量的標(biāo)識(shí)符


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


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



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

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

class UF {

    /**
     * 
     * @param {number} N 
     */
    constructor(N) {
        this.id = new Array(N).fill(0).map((x, index) => index)
        //各個(gè)根節(jié)點(diǎn)所對(duì)應(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)
    }

    /** 
     * 找到根觸點(diǎn)，即分量的標(biāo)識(shí)符
     * @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
        //將小樹(shù)連接到大樹(shù)上
        if (sz[pRoot] < sz[qRoot]) {
            id[p] = qRoot
            sz[qRoot] += sz[pRoot]
        } else {
            id[q] = pRoot
            sz[pRoot] += sz[qRoot]
        }
        this.count--
    }

}

復(fù)雜度分析：

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

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