1.鏈表

1.實(shí)現(xiàn)一個(gè)單向鏈表

/*
    實(shí)現(xiàn)一個(gè)單向鏈表，滿足以下條件：
    get(index)：獲取鏈表中第 index 個(gè)節(jié)點(diǎn)的值。如果索引無(wú)效蜀备，則返回-1。
    addAtHead(val)：在鏈表的第一個(gè)元素之前添加一個(gè)值為 val 的節(jié)點(diǎn)荒叶。插入后碾阁，新節(jié)點(diǎn)將成為鏈表的第一個(gè)節(jié)點(diǎn)。
    addAtTail(val)：將值為 val 的節(jié)點(diǎn)追加到鏈表的最后一個(gè)元素些楣。
    addAtIndex(index,val)：在鏈表中的第 index 個(gè)節(jié)點(diǎn)之前添加值為 val  的節(jié)點(diǎn)脂凶。如果 index 等于鏈表的長(zhǎng)度，則該節(jié)點(diǎn)將附加到鏈表的末尾愁茁。如果 index 大于鏈表長(zhǎng)度蚕钦，則不會(huì)插入節(jié)點(diǎn)。如果index小于0鹅很，則在頭部插入節(jié)點(diǎn)嘶居。
    deleteAtIndex(index)：如果索引 index 有效，則刪除鏈表中的第 index 個(gè)節(jié)點(diǎn)促煮。
*/
var MyLinkedList = function() {
    this.length = 0;
    this.head = { val: null, next: null }
};

MyLinkedList.prototype.get = function(index) {
    if(index<0 || index>(this.length-1)) {
        return -1;
    } else {
        let i = 0;
        let node = this.head;
        while(i !== index) {
            i++;
            node = node.next    //這里直接令node=node.next將不再影響this.head值
        }
        return node.val;
    }
};

MyLinkedList.prototype.getNode = function(index) {
    if(index<0 || index>(this.length-1)) {
        return -1;
    } else {
        let i = 0;
        let node = this.head;
        while(i !== index) {
            i++;
            node = node.next
        }
        return node;
    }
};

MyLinkedList.prototype.addAtHead = function(val) {
    if(this.head.val === null) {
        this.head.val = val;
        this.head.next = null;
    } else {
        let node = this.head;
        this.head = {}; //注意這里要先將this.head置空邮屁，改變其引用地址，否則直接修改會(huì)影響到原node值
        this.head.next = node;
        this.head.val = val;
    }
    this.length++;
};

MyLinkedList.prototype.addAtTail = function(val) {
    if(this.head.val === null) {
        this.addAtHead(val)
    } else {
        let node = this.getNode(this.length-1);
        let tailNode = { val: val, next: null };
        node.next = tailNode;
        this.length++;
    }
};

MyLinkedList.prototype.addAtIndex = function(index, val) {
    if(index === this.length) {
        this.addAtTail(val);
    }
    else if(index > this.length) {
        return
    }
    else if(index <= 0) {
        this.addAtHead(val);
    }
    else {
        let prevNode = this.getNode(index-1);
        let nextNode = this.getNode(index);
        let node = { val: val, next: nextNode };
        prevNode.next = node;
        this.length++;
    }
};


MyLinkedList.prototype.deleteAtIndex = function(index) {
    if(index<0 || index>=this.length){
        return
    }
    if(this.length === 1) {
        this.head = { val: null, next: null };
        this.length--;
    } else {
        if(index === 0) {
            this.head = this.getNode(1);   
            this.length--;
        } else {
            let prevNode = this.getNode(index-1);
            let node = this.getNode(index);
            prevNode.next = node.next;
            node = {};  //將刪除節(jié)點(diǎn)置空
            this.length--;
        }   
    }
};

2.找出鏈表相交節(jié)點(diǎn)污茵，假設(shè)均沒(méi)有環(huán)

// 找出鏈表相交節(jié)點(diǎn)樱报，假設(shè)均沒(méi)有環(huán)
// 1. 雙指針?lè)?var getIntersectionNode = function(headA, headB) {
    if(headA==null || headB==null) {
        return null;
    }
    let p = headA;
    let q = headB;
    while(p.next !== q.next) {
        if(p.next == null) {
            p = headB;
        } else {
            p = p.next;
        }
        if(q.next == null) {
            q = headA;
        } else {
            q = q.next;
        }
    }
    if(p == q) {
        return p
    }
    return p.next;
};

// 2. 取出長(zhǎng)度，長(zhǎng)度大的先走幾步達(dá)到與長(zhǎng)度短的相同泞当，然后開(kāi)始同步遍歷，相同就停止民珍；
//    若有相交節(jié)點(diǎn)則會(huì)返回相交節(jié)點(diǎn)襟士，若無(wú)相交節(jié)點(diǎn)，最終均走到null嚷量，返回null

var getIntersectionNode = function(headA, headB) {
    if(headA==null || headB==null) {
        return null;
    }
    let a = 0, b=0;
    let p = headA, q = headB;
    while(p.next !== null) {
        p = p.next;
        a++;
    }
    while(q.next !== null) {
        q = q.next;
        b++;
    }
    let c = a - b;
    if(c > 0) {
        p = headA;
        while(c !=0) {
            p = p.next;
            c--;
        }
        q = headB;
    } else {
        p = headA;
        c = Math.abs(c);
        q = headB;
        while(c !=0) {
            q = q.next;
            c--;
        }
    }
    while(p !== q) {
        p = p.next;
        q = q.next;
    }
    return p;
};

3.判斷鏈表是否有環(huán)
思路：使用快慢兩個(gè)指針陋桂，當(dāng)鏈表含有環(huán)時(shí)，將不會(huì)走到null蝶溶，則快指針終將在超出慢指針k個(gè)環(huán)路長(zhǎng)度后追到慢指針：

var hasCycle = function(head) {
    if(!head|| !head.next) {
        return false;
    }
    let p = head;
    let q = head;
    while(q!==null && q.next!==null) {
        p = p.next;
        q = q.next.next;
        if(p === q) {
            return true;
        }
    }
    return false;
};

進(jìn)一步找到環(huán)的開(kāi)始節(jié)點(diǎn)：
當(dāng)快慢指針相遇后嗜历，快指針此時(shí)走了慢指針兩倍距離，假設(shè)環(huán)長(zhǎng)度為l抖所，非環(huán)長(zhǎng)度為n梨州，相遇時(shí)距離環(huán)起點(diǎn)為m，則此時(shí)慢指針共走了(m+n)距離田轧，快指針走了(m+n+kl)距離暴匠，其中k為快指針比慢指針多走的環(huán)路圈數(shù)。
m+n+kl = 2(m+n)
即傻粘，k*l = m+n
此時(shí)距離環(huán)起點(diǎn)慢指針已走了m步每窖，若再走n步則相當(dāng)于從環(huán)起點(diǎn)開(kāi)始繞環(huán)行走了k圈又回到環(huán)起點(diǎn)帮掉！
而n正好為鏈表非環(huán)長(zhǎng)度，此時(shí)令快指針從頭開(kāi)始一步一步走窒典，則快指針走n步時(shí)也正好達(dá)環(huán)起點(diǎn)蟆炊！
即當(dāng)兩指針初次相遇后，令快指針從鏈表頭開(kāi)始一步一步走瀑志，慢指針繼續(xù)一步一步走涩搓，當(dāng)它們?cè)俅蜗嘤鰰r(shí)，即為環(huán)起點(diǎn)后室！

var detectCycle = function(head) {
    if(!head || !(head.next)) {
        return null;
    }
    let slow = head, fast = head;
    let flag = false;
    while(fast!==null && fast.next!==null) {
        slow = slow.next;
        fast = fast.next.next;
        if(slow === fast) {
            flag = true;
            break;
        }
    }
    if(flag) {
        fast = head;
        while(fast !== slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    } else {
        return null;
    }
};

4.給定一個(gè)鏈表缩膝，刪除鏈表的倒數(shù)第 n 個(gè)節(jié)點(diǎn)，并且返回鏈表的頭結(jié)點(diǎn)
給定條件：n保證是有效的
思路：要?jiǎng)h除倒數(shù)第n個(gè)節(jié)點(diǎn)岸霹，可給定兩個(gè)指針疾层，快指針和慢指針，讓快指針先向前走n步贡避，然后兩個(gè)指針再一起走痛黎，當(dāng)快指針走到null時(shí)，慢指針剛好走到倒數(shù)第n個(gè)節(jié)點(diǎn)刮吧。
又由于刪除倒數(shù)第n個(gè)節(jié)點(diǎn)湖饱，就是讓倒數(shù)第n+1個(gè)節(jié)點(diǎn)的next指向刪除節(jié)點(diǎn)的next，因此兩個(gè)指針一起走時(shí)可令快指針不走到null杀捻，而是走到最后一個(gè)節(jié)點(diǎn)井厌，即此節(jié)點(diǎn)的next指向null，此時(shí)慢節(jié)點(diǎn)正好走到倒數(shù)第n+1個(gè)節(jié)點(diǎn)致讥，假設(shè)為node仅仆，令node.next = node.next.next即可刪除倒數(shù)第n個(gè)節(jié)點(diǎn)
此外需注意，當(dāng)n等于鏈表長(zhǎng)度時(shí)垢袱，快指針先走n步已走到null墓拜，此時(shí)慢指針為頭結(jié)點(diǎn)，即為倒數(shù)第n個(gè)節(jié)點(diǎn)请契，而非倒數(shù)第n+1個(gè)節(jié)點(diǎn)咳榜，因此刪除頭結(jié)點(diǎn)即可，直接返回head.next

var removeNthFromEnd = function(head, n) {
    let p = head, q = head;
    while(n>0) {
        p = p.next;
        n--;
    }
    if(p === null) {
        return head.next;
    }
    while(p.next !== null) {
        p = p.next;
        q = q.next;
    }
    q.next = q.next.next;
    return head;
};

5.反轉(zhuǎn)鏈表
反轉(zhuǎn)一個(gè)單鏈表爽锥，例如：
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL

非遞歸思路：遍歷鏈表涌韩，將每個(gè)鏈表元素，依次放到首位救恨。
利用head去遍歷鏈表贸辈，首先，令headNode=head，令nextNode=head.next取到第二個(gè)節(jié)點(diǎn)擎淤，然后令head.next=nextNode.head奢啥，即將head放到第二個(gè)節(jié)點(diǎn)位置，然后令nextNode.next=headNode嘴拢，將原本第二個(gè)節(jié)點(diǎn)放到第一個(gè)位置桩盲，再令headNode=nextNode取得現(xiàn)在的第一個(gè)節(jié)點(diǎn)，此時(shí)head為第二個(gè)節(jié)點(diǎn)席吴，按上述方法再將head放到第三個(gè)節(jié)點(diǎn)位置赌结，將第三個(gè)節(jié)點(diǎn)指向headNode，即放到第一個(gè)位置孝冒，再令headNode等于第三個(gè)節(jié)點(diǎn)柬姚，仍取現(xiàn)在的第一個(gè)節(jié)點(diǎn)，循環(huán)往復(fù)庄涡，直至head移動(dòng)到最后一個(gè)位置指向null量承，此時(shí)原最后一個(gè)節(jié)點(diǎn)放到了首位，完成鏈表的反轉(zhuǎn)

var reverseList = function(head) {
    if(head === null || head.next===null) {
        return head;
    }
    let headNode = head;
    while(head.next !== null) {
        let nextNode = head.next;
        head.next = nextNode.next;
        nextNode.next = headNode;
        headNode = nextNode;
    }
    return headNode;
};

遞歸思路：將最后一個(gè)節(jié)點(diǎn)的next指向前一個(gè)節(jié)點(diǎn)穴店，再將前一個(gè)節(jié)點(diǎn)的next指向null撕捍，然后就反轉(zhuǎn)了最后兩個(gè)元素；再繼續(xù)將前一個(gè)節(jié)點(diǎn)的next指向前前一個(gè)節(jié)點(diǎn)泣洞，將前前一個(gè)節(jié)點(diǎn)的next指向null忧风，這樣又完成了倒數(shù)第二個(gè)節(jié)點(diǎn)和倒數(shù)第三個(gè)節(jié)點(diǎn)的反轉(zhuǎn)；最終完成所有元素的反轉(zhuǎn)

var reverseList = function(head) {
    if(head === null || head.next===null) {
        return head;
    }
    const node = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return node;
};

6.移除鏈表元素
題目描述：刪除鏈表中等于給定值 val 的所有節(jié)點(diǎn)
思路：
首先判斷頭結(jié)點(diǎn)的值是否等于指定值球凰，等于則令head=head.next狮腿，將頭結(jié)點(diǎn)后移一位，直到刪除所有等于指定值的頭結(jié)點(diǎn)呕诉；
然后從頭結(jié)點(diǎn)開(kāi)始蚤霞，判斷下一個(gè)節(jié)點(diǎn)的值是否等于指定值(因?yàn)橐獎(jiǎng)h除一個(gè)節(jié)點(diǎn)需要令它的前一個(gè)節(jié)點(diǎn)指向它的后一個(gè)節(jié)點(diǎn))，等于則刪除义钉，直到其后面的節(jié)點(diǎn)值不等于指定值；
若其后面的節(jié)點(diǎn)值不等于指定值规肴，則將其后移一位捶闸，循環(huán)第二、三過(guò)程拖刃，直到鏈表結(jié)束

var removeElements = function(head, val) {
    while(head && head.val === val) {
        head = head.next;
    }
    let p = head;
    while(p && p.next) {
        while(p.next && p.next.val === val) {
            p.next = p.next.next;
        }
        p = p.next;
    }
    return head
};

7.奇偶鏈表
題目描述：給定一個(gè)單鏈表删壮，把所有的奇數(shù)節(jié)點(diǎn)和偶數(shù)節(jié)點(diǎn)分別排在一起。請(qǐng)注意兑牡，這里的奇數(shù)節(jié)點(diǎn)和偶數(shù)節(jié)點(diǎn)指的是節(jié)點(diǎn)編號(hào)的奇偶性央碟，而不是節(jié)點(diǎn)的值的奇偶性
例如：
輸入: 1->2->3->4->5->NULL
輸出: 1->3->5->2->4->NULL

思路：首先判斷鏈表長(zhǎng)度是否小于等于二，是則直接返回head均函；
定義四個(gè)指針亿虽，p=head菱涤，q=head.next，r=head.next洛勉，s=null粘秆，其中p和q分別去遍歷鏈表的奇數(shù)項(xiàng)和偶數(shù)項(xiàng)，并將其拆開(kāi)收毫，奇數(shù)項(xiàng)指向奇數(shù)項(xiàng)攻走，偶數(shù)項(xiàng)指向偶數(shù)項(xiàng)；r用來(lái)保存偶數(shù)項(xiàng)第一項(xiàng)節(jié)點(diǎn)此再，等待遍歷完成令奇數(shù)項(xiàng)最后一項(xiàng)的指針指向它昔搂；s用來(lái)保存奇數(shù)項(xiàng)和偶數(shù)項(xiàng)指向變化前的指向，避免形成閉環(huán)

var oddEvenList = function(head) {
    if(!head || !head.next || !head.next.next) {
        return head;
    }
    let p = head;
    let q = head.next;
    let r = head.next;
    let s = null;
    while(p && p.next && p.next.next) {
        s = p.next.next;
        p.next = p.next.next;
        p = s;
        if(q && q.next.next) {
            s = q.next.next;
            q.next = q.next.next;
            q = s;
        }
    }
    p.next = r;
    q.next = null;
    return head;
};

8.回文鏈表
題目描述：判斷一個(gè)鏈表是否為回文鏈表
示例：
輸入: 1->2
輸出: false
輸入: 1->2->2->1
輸出: true

思路：判斷一個(gè)鏈表是否為回文鏈表输拇，即判斷其正向返回值與反向返回值是否相同摘符；定義兩個(gè)字符串，一個(gè)正向str淳附，一個(gè)方向str_reverse议慰；遍歷鏈表，正向字符串每次加上每個(gè)節(jié)點(diǎn)的值奴曙，反向字符串每次將節(jié)點(diǎn)的值放到最前面然后加上反向字符串的值别凹，這樣遍歷完成后，正向字符串存儲(chǔ)的為正向遍歷的值洽糟，反向字符串存儲(chǔ)的為鏈表反向的值炉菲，判斷它們是否相等即可

var isPalindrome = function(head) {
    let str = "";
    let str_reverse = "";
    while(head) {
        str += head.val;
        str_reverse = head.val + str_reverse;
        head = head.next;
    }
    return str === str_reverse;
};

9.實(shí)現(xiàn)雙向列表

var MyLinkedList = function() {
    this.length = 0;
    this.head = { val: null, prev: null, next: null }
};

MyLinkedList.prototype.get = function(index) {
    if(index<0 || index>(this.length-1)) {
        return -1;
    } else {
        let i = 0;
        let node = this.head;
        while(i !== index) {
            i++;
            node = node.next
        }
        return node.val;
    }
};

MyLinkedList.prototype.getNode = function(index) {
    if(index<0 || index>(this.length-1)) {
        return -1;
    } else {
        let i = 0;
        let node = this.head;
        while(i !== index) {
            i++;
            node = node.next
        }
        return node;
    }
};

MyLinkedList.prototype.addAtHead = function(val) {
    if(this.head.val === null) {
        this.head.val = val;
        this.head.prev = null;
        this.head.next = null;
    } else {
        let node = this.head;
        this.head = { val: val, prev: null, next: node };
        node.prev = this.head;
    }
    this.length++;
};

MyLinkedList.prototype.addAtTail = function(val) {
    if(this.head.val === null) {
        this.addAtHead(val)
    } else {
        let node = this.getNode(this.length-1);
        node.next = { val: val, prev: node, next: null };
        this.length++;
    }
};

MyLinkedList.prototype.addAtIndex = function(index, val) {
    if(index === this.length) {
        this.addAtTail(val);
    }
    else if(index > this.length) {
        return
    }
    else if(index <= 0) {
        this.addAtHead(val);
    }
    else {
        let prevNode = this.getNode(index-1);
        let node = { val: val, prev: prevNode, next: prevNode.next };
        prevNode.next = node;
        node.next.prev = node;
        this.length++;
    }
};


MyLinkedList.prototype.deleteAtIndex = function(index) {
    if(index<0 || index>=this.length){
        return
    }
    if(this.length === 1) {
        this.head = { val: null, prev: null, next: null };
        this.length--;
    } else {
        if(index === 0) {
            this.head = this.getNode(1);
            this.head.prev = null;
        } else if(index === this.length-1) {
            let node = this.getNode(index-1);
            node.next = null;
        } else {
            let node = this.getNode(index);
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }   
        this.length--;
    }
};

10.合并兩個(gè)有序鏈表
題目描述：將兩個(gè)升序鏈表合并為一個(gè)新的 升序 鏈表并返回。新鏈表是通過(guò)拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的
示例：
輸入：1->2->4, 1->3->4
輸出：1->1->2->3->4->4

思路：新建一個(gè)鏈表坤溃，頭結(jié)點(diǎn)指向空拍霜，遍歷比較兩個(gè)排序鏈表，將較小的值放到新鏈表后薪介，比較完成后查看兩個(gè)鏈表是否仍有剩余祠饺，將剩余鏈表直接鏈接到新鏈表后方，返回時(shí)需注意返回新鏈表的第二個(gè)節(jié)點(diǎn)

var mergeTwoLists = function(l1, l2) {
    let l3 = new ListNode();
    let cur = l3;
    while(l1 && l2) {
        if(l1.val <= l2.val) {
            cur.next = l1;
            l1 = l1.next;
        } else {
            cur.next = l2;
            l2 = l2.next;
        }
        cur = cur.next;
    }
    if(l1) {
        cur.next = l1;
    }
    if(l2) {
        cur.next = l2;
    }
    return l3.next;
};

10.兩數(shù)相加
題目描述：給出兩個(gè) 非空 的鏈表用來(lái)表示兩個(gè)非負(fù)的整數(shù)汁政。其中道偷，它們各自的位數(shù)是按照 逆序 的方式存儲(chǔ)的，并且它們的每個(gè)節(jié)點(diǎn)只能存儲(chǔ) 一位 數(shù)字
如果记劈，我們將這兩個(gè)數(shù)相加起來(lái)勺鸦，則會(huì)返回一個(gè)新的鏈表來(lái)表示它們的和
給定條件：假設(shè)除了數(shù)字 0 之外，這兩個(gè)數(shù)都不會(huì)以 0 開(kāi)頭
示例：
輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出：7 -> 0 -> 8
原因：342 + 465 = 807

思路：新建鏈表指向兩鏈表之和的鏈表目木，首先將兩個(gè)鏈表對(duì)應(yīng)位置遍歷相加换途，相加時(shí)判斷進(jìn)位flag是否為true，為true則再加1；相加有進(jìn)位時(shí)令flag=true军拟，令和sum=sum%10剃执，新建節(jié)點(diǎn){val: sun, next: null}添加到新鏈表后方
當(dāng)一個(gè)鏈表遍歷完成后，判斷另一個(gè)鏈表是否還有剩余吻谋，有剩余則判斷此時(shí)flag是否為true忠蝗，為true則遍歷剩余節(jié)點(diǎn)，節(jié)點(diǎn)值加1形成新節(jié)點(diǎn)添加到新鏈表后方漓拾，直至flag不再為true阁最；當(dāng)flag不為true時(shí)，說(shuō)明不再需要加進(jìn)位骇两，則直接將剩余鏈表放到新鏈表后方
當(dāng)兩個(gè)鏈表和剩余鏈表均遍歷完成后速种，判斷此時(shí)flag是否為true，為true則說(shuō)明最后仍有進(jìn)位低千，則需在新鏈表后方添加節(jié)點(diǎn){ val: 1, next: null }
返回新鏈表的第二個(gè)節(jié)點(diǎn)(第二個(gè)節(jié)點(diǎn)才是和鏈表的第一個(gè)節(jié)點(diǎn))

var addTwoNumbers = function(l1, l2) {
    let l3 = new ListNode();
    let cur = l3;
    let sum = 0, flag = false;
    while(l1 && l2) {
        if(flag) {
            sum = l1.val + l2.val + 1;
            flag = false;
        } else {
            sum = l1.val + l2.val;
        }
        if(sum >= 10) {
            flag = true;
            sum = sum % 10;
        }
        cur.next = new ListNode(sum, null);
        cur = cur.next;
        l1 = l1.next;
        l2 = l2.next;
    }
    while(l1) {
        if(flag) {
            sum = l1.val + 1;
            if(sum >= 10) {
                sum = sum % 10;
                cur.next = new ListNode(sum, null);
                cur = cur.next;
                l1 = l1.next;
            } else {
                flag = false;
                cur.next = new ListNode(sum, null);
                cur = cur.next;
                l1 = l1.next;
                cur.next = l1;
                break;
            }
        }else {
            cur.next = l1;
            break;
        }
    }
    while(l2) {
        if(flag) {
            sum = l2.val + 1;
            if(sum >= 10) {
                sum = sum % 10;
                cur.next = new ListNode(sum, null);
                cur = cur.next;
                l2 = l2.next;
            } else {
                flag = false;
                cur.next = new ListNode(sum, null);
                cur = cur.next;
                l2 = l2.next;
                cur.next = l2;
                break;
            }
        }else {
            cur.next = l2;
            break;
        }
    }
    if(flag) {
        cur.next = new ListNode(1, null);
    }
    return l3.next;
};

11.扁平化多級(jí)雙向鏈表
題目描述：多級(jí)雙向鏈表中配阵，除了指向下一個(gè)節(jié)點(diǎn)和前一個(gè)節(jié)點(diǎn)指針之外，它還有一個(gè)子鏈表指針示血，可能指向單獨(dú)的雙向鏈表棋傍。這些子列表也可能會(huì)有一個(gè)或多個(gè)自己的子項(xiàng)，依此類推难审，生成多級(jí)數(shù)據(jù)結(jié)構(gòu)瘫拣，如下面的示例所示。
給你位于列表第一級(jí)的頭節(jié)點(diǎn)告喊，請(qǐng)你扁平化列表麸拄，使所有結(jié)點(diǎn)出現(xiàn)在單級(jí)雙鏈表中
多級(jí)鏈表如下圖所示：

多級(jí)雙向列表

扁平化后雙向鏈表

思路：將多層鏈表逐層遞減最終轉(zhuǎn)換為單層；如例所示黔姜，即將三層轉(zhuǎn)換為兩層拢切，再將兩層轉(zhuǎn)化為一層
遍歷當(dāng)前鏈表，查看當(dāng)前節(jié)點(diǎn)是否含有子節(jié)點(diǎn)秆吵，含有則查看當(dāng)前節(jié)點(diǎn)是否為當(dāng)前層最后一個(gè)節(jié)點(diǎn)淮椰，即查看當(dāng)前節(jié)點(diǎn)的next是否為null；若當(dāng)前節(jié)點(diǎn)為當(dāng)前層最后一個(gè)節(jié)點(diǎn)纳寂，則將子節(jié)點(diǎn)連接到當(dāng)前節(jié)點(diǎn)即可实苞；若當(dāng)前節(jié)點(diǎn)不為當(dāng)前層最后一個(gè)節(jié)點(diǎn)，則遍歷子節(jié)點(diǎn)當(dāng)前層烈疚，將最后的節(jié)點(diǎn)接入當(dāng)前節(jié)點(diǎn)后面節(jié)點(diǎn)的前面；此時(shí)則將第二層轉(zhuǎn)到了第一層聪轿，若原來(lái)子層仍含有子層爷肝，則此時(shí)轉(zhuǎn)變?yōu)榈诙樱?br> 然后令當(dāng)前節(jié)點(diǎn)為后一個(gè)節(jié)點(diǎn)，繼續(xù)遍歷，直至將所有節(jié)點(diǎn)都連接到一層灯抛，扁平化完成

var flatten = function(head) {
    let p = head;
    while(p) {
        if(p.child !== null) {
            if(p.next !== null) {
                let q = p.next;
                p.next = p.child;
                p.next.prev = p;
                let r = p.next;
                while(r.next !== null) {
                    r = r.next;
                }
                r.next = q;
                q.prev = r;
                p.child = null;
            } else {
                p.next = p.child;
                p.next.prev = p;
                p.child = null;
            }
        }
        p = p.next;
    }
    return head;
};

12.旋轉(zhuǎn)鏈表
題目描述：給定一個(gè)鏈表金赦，旋轉(zhuǎn)鏈表，將鏈表每個(gè)節(jié)點(diǎn)向右移動(dòng) k 個(gè)位置对嚼，其中 k 是非負(fù)數(shù)
示例：
輸入: 1->2->3->4->5->NULL, k = 2
輸出: 4->5->1->2->3->NULL
輸入: 0->1->2->NULL, k = 4
輸出: 2->0->1->NULL

思路：首先求出鏈表長(zhǎng)度len夹抗，求取過(guò)程中存儲(chǔ)尾節(jié)點(diǎn)p；移動(dòng)k位就相當(dāng)于移動(dòng)(k%len)位(無(wú)論k是否大于len)纵竖，而當(dāng)k為len的整數(shù)倍時(shí)漠烧，相當(dāng)于不做任何操作；
當(dāng)k不為len的整數(shù)倍時(shí)靡砌，向右移動(dòng)k位已脓，相當(dāng)于將由尾節(jié)點(diǎn)開(kāi)始，長(zhǎng)度為k的子鏈表放置到鏈表頭部通殃；即度液，將當(dāng)前尾節(jié)點(diǎn)指向當(dāng)前頭結(jié)點(diǎn)，將倒數(shù)第k個(gè)節(jié)點(diǎn)設(shè)為頭結(jié)點(diǎn)画舌，并將倒數(shù)第k+1個(gè)節(jié)點(diǎn)的next指向null堕担；
求長(zhǎng)度時(shí)獲得了尾節(jié)點(diǎn)p，令尾節(jié)點(diǎn)指向當(dāng)前head曲聂，p.next=head霹购；從頭結(jié)點(diǎn)開(kāi)始玄柠，向后走(len-k)步即走到倒數(shù)第k個(gè)節(jié)點(diǎn)斑匪，而我們要將第k個(gè)節(jié)點(diǎn)設(shè)為頭結(jié)點(diǎn)，并將倒數(shù)第k+1個(gè)節(jié)點(diǎn)指向null嬉愧，這只需我們獲得倒數(shù)第k+1個(gè)節(jié)點(diǎn)即可(倒數(shù)第k個(gè)節(jié)點(diǎn)等于倒數(shù)第k+1個(gè)節(jié)點(diǎn)的next)乍丈，因此我們只需向后走(len-k+1)步剂碴，然后進(jìn)行操作即可

var rotateRight = function(head, k) {
    if(!head || !head.next) {
        return head;
    }
    let len = 0;
    let p = head;
    while(p.next) {
        len++;
        p = p.next;
    }
    len = len+1;
    k = k % len;
    if(k === 0) return head;
    k = len - k;
    let q = head;
    while(k>1) {
        k--;
        q = q.next;
    }
    p.next = head;
    head = q.next;
    q.next = null;
    return head;
    
};

13.復(fù)制帶隨機(jī)指針的鏈表
題目描述：給定一個(gè)鏈表，每個(gè)節(jié)點(diǎn)包含一個(gè)額外增加的隨機(jī)指針轻专，該指針可以指向鏈表中的任何節(jié)點(diǎn)或空節(jié)點(diǎn)忆矛，要求返回這個(gè)鏈表的 深拷貝
思路：遍歷兩次原鏈表，第一次復(fù)制每個(gè)節(jié)點(diǎn)的val和next请垛，并將復(fù)制的新節(jié)點(diǎn)插入到原節(jié)點(diǎn)后面催训，這樣即形成A->A'->B->B'->C->C'->...
第二次遍歷原鏈表復(fù)制隨機(jī)指針，假設(shè)原A的隨機(jī)指針指向C宗收，則A'隨機(jī)指針應(yīng)指向C'漫拭，即A.next.random=A.random.next，復(fù)制時(shí)需注意原鏈表節(jié)點(diǎn)的隨機(jī)指針是否指向null混稽，是的話A.next.random=null
復(fù)制完成后將鏈表拆開(kāi)采驻，一部分為原鏈表审胚，一部分為新鏈表，注意將原鏈表指向改回來(lái)礼旅，即A.next=A.next.next膳叨，最后注意將原鏈表最后節(jié)點(diǎn)指向null

var copyRandomList = function(head) {
    if(!head) {
        return head;
    }
    let p = head;
    let tmp = new Node(0, null, null);
    while(p) {
        tmp = new Node(p.val, p.next, null);
        p.next = tmp;
        p = p.next.next;
    }
    p = head;
    while(p) {
        if(p.random === null) {
            p.next.random = null;
        } else {
            p.next.random = p.random.next;   
        }
        p = p.next.next;
    }
    let newHead = head.next;
    p = head;
    let q = newHead;
    while(q && q.next) {
        p.next = p.next.next;
        q.next = q.next.next;
        p = p.next;
        q = q.next;
    }
    p.next = null;
    return newHead;
};

2.隊(duì)列和棧

1.實(shí)現(xiàn)一個(gè)循環(huán)隊(duì)列
要求：
MyCircularQueue(k): 構(gòu)造器，設(shè)置隊(duì)列長(zhǎng)度為 k 痘系。
Front: 從隊(duì)首獲取元素菲嘴。如果隊(duì)列為空，返回 -1 汰翠。
Rear: 獲取隊(duì)尾元素龄坪。如果隊(duì)列為空，返回 -1 奴璃。
enQueue(value): 向循環(huán)隊(duì)列插入一個(gè)元素悉默。如果成功插入則返回真。
deQueue(): 從循環(huán)隊(duì)列中刪除一個(gè)元素苟穆。如果成功刪除則返回真抄课。
isEmpty(): 檢查循環(huán)隊(duì)列是否為空。
isFull(): 檢查循環(huán)隊(duì)列是否已滿雳旅。

/**
 * Initialize your data structure here. Set the size of the queue to be k.
 * @param {number} k
 */
var MyCircularQueue = function(k) {
    this.len = k;
    this.queue = [];
};

/**
 * Insert an element into the circular queue. Return true if the operation is successful. 
 * @param {number} value
 * @return {boolean}
 */
MyCircularQueue.prototype.enQueue = function(value) {
    console.log(this.queue)
    let len = this.queue.length;
    if(len === this.len) {
        return false;
    }
    this.queue.push(value);
    return true;
};

/**
 * Delete an element from the circular queue. Return true if the operation is successful.
 * @return {boolean}
 */
MyCircularQueue.prototype.deQueue = function() {
    if(this.queue.length === 0) {
        return false;
    } 
    this.queue.shift();
    return true;
};

/**
 * Get the front item from the queue.
 * @return {number}
 */
MyCircularQueue.prototype.Front = function() {
    if(this.queue.length === 0) {
        return -1
    }
    return this.queue[0];
};

/**
 * Get the last item from the queue.
 * @return {number}
 */
MyCircularQueue.prototype.Rear = function() {
    if(this.queue.length === 0) {
        return -1;
    }
    let len = this.queue.length;
    return this.queue[len-1];
};

/**
 * Checks whether the circular queue is empty or not.
 * @return {boolean}
 */
MyCircularQueue.prototype.isEmpty = function() {
    return this.queue.length === 0;
};

/**
 * Checks whether the circular queue is full or not.
 * @return {boolean}
 */
MyCircularQueue.prototype.isFull = function() {
    return this.queue.length === this.len;
};

2.島嶼數(shù)量
題目描述：給你一個(gè)由 '1'（陸地）和 '0'（水）組成的的二維網(wǎng)格跟磨，請(qǐng)你計(jì)算網(wǎng)格中島嶼的數(shù)量；島嶼總是被水包圍攒盈，并且每座島嶼只能由水平方向或豎直方向上相鄰的陸地連接形成抵拘；此外，你可以假設(shè)該網(wǎng)格的四條邊均被水包圍型豁。
示例：
輸入:
[
['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']
]
輸出: 3
解釋：所有通過(guò)上下左右連接起來(lái)的"1"算是一個(gè)島嶼

思路：深度優(yōu)先遍歷僵蛛；
遍歷整個(gè)二維數(shù)組，判斷當(dāng)前元素是否等于"1"迎变，等于則令島嶼數(shù)目加1充尉；
遍歷此島嶼，將該元素置"0"衣形，判斷該元素其四周連接(上下左右)元素是否為"1"驼侠，為"1"則置"0"，繼續(xù)判斷為"1"的周圍元素的周圍元素是否為"1"谆吴，直到遇到"0"或邊界為止(邊界也為"0")倒源；
這樣對(duì)某一元素周圍元素深度優(yōu)先遍歷后，其周圍為"1"的元素將全被置"0"句狼，當(dāng)前島嶼遍歷完畢笋熬；繼續(xù)尋找其他島嶼，重復(fù)上述過(guò)程直至結(jié)束腻菇；
例：
[
['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']
]
處理一次后突诬，島嶼個(gè)數(shù)加1苫拍，第一個(gè)島嶼遍歷完成，原數(shù)組變?yōu)椋?br> [
['0','0','0','0','0'],
['0','0','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']
]
然后尋找到第二個(gè)島嶼旺隙，并遍歷完成后：
[
['0','0','0','0','0'],
['0','0','0','0','0'],
['0','0','0','0','0'],
['0','0','0','1','1']
]
尋找第三個(gè)島嶼。并遍歷完成后：
[
['0','0','0','0','0'],
['0','0','0','0','0'],
['0','0','0','0','0'],
['0','0','0','0','0']
]
此時(shí)不再有島嶼骏令，且整個(gè)數(shù)組遍歷完成蔬捷，結(jié)束

var numIslands = function(grid) {
    let height = grid.length;
    if(height === 0) return 0;
    let width = grid[0].length;
    let count = 0;
    for(let i=0; i<height; i++)
        for(let j=0; j<width; j++) {
            if(grid[i][j] === "1") {
                count++;
                isIsland(j, i, grid, width, height);
            }
        }
    return count;
};

function isIsland(x, y, grid, w, h) {
    if(x<0 || y<0 || x===w || y===h || grid[y][x]==='0') return;
    grid[y][x] = '0';
    isIsland(x-1, y, grid, w, h);
    isIsland(x, y-1, grid, w, h);
    isIsland(x+1, y, grid, w, h);
    isIsland(x, y+1, grid, w, h);
}

3.設(shè)計(jì)最小棧
題目要求：
設(shè)計(jì)一個(gè)支持 push ，pop 榔袋，top 操作周拐，并能在常數(shù)時(shí)間內(nèi)檢索到最小元素的棧。
push(x) —— 將元素 x 推入棧中凰兑。
pop() —— 刪除棧頂?shù)脑亍?br> top() —— 獲取棧頂元素妥粟。
getMin() —— 檢索棧中的最小元素。

/**
 * initialize your data structure here.
 */
var MinStack = function() {
    this.stack = [];
    this.minStack = [];
};

/** 
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
    this.stack.push(x);
    if(this.minStack.length===0 || x<=this.getMin()) {
        this.minStack.push(x);
    }
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    let x = this.stack.pop();
    if(x === this.getMin()) {
        this.minStack.pop();
    }
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    let len = this.stack.length;
    return this.stack[len-1];
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
    let len = this.minStack.length;
    return this.minStack[len-1];
};

/**
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(x)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.getMin()
 */

4.有效的括號(hào)
題目描述：給定一個(gè)只包括 '('吏够，')'勾给，'{'，'}'锅知，'['播急，']' 的字符串，判斷字符串是否有效售睹。
有效字符串需滿足：
左括號(hào)必須用相同類型的右括號(hào)閉合桩警。
左括號(hào)必須以正確的順序閉合。
注意：空字符串可被認(rèn)為是有效字符串昌妹。
示例：
輸入: "{[]}"
輸出: true
輸入: "([)]"
輸出: false
思路1：將給定字符串轉(zhuǎn)換為數(shù)組捶枢，然后遍歷數(shù)組；
依次判斷遇到的字符飞崖，若為"("烂叔，"["或"{"，則push入一個(gè)臨時(shí)數(shù)組蚜厉；
當(dāng)遇到")"长已，"]"或"}"時(shí)，則判斷臨時(shí)數(shù)組中最后一位是否為對(duì)應(yīng)的"("昼牛，"["或"{"术瓮，若是，則將該元素從臨時(shí)數(shù)組中pop掉贰健，否則說(shuō)明不符合條件胞四，退出遍歷，返回false伶椿；
當(dāng)遍歷完成后判斷臨時(shí)數(shù)組中是否仍含有元素辜伟，若是氓侧，則說(shuō)明含有未能配對(duì)的括號(hào)，不滿足條件导狡，返回false约巷。

var isValid = function(s) {
    let arr = [...s];
    let tmp = [];
    for(let i=0; i<arr.length; i++) {
        if(arr[i]==="(" || arr[i]==="[" || arr[i]==="{") {
            tmp.push(arr[i]);
        }
        if(arr[i] === ")") {
            if(tmp[tmp.length-1] === "(") {
                tmp.pop();
            } else {
                return false;
            }
        }
        if(arr[i] === "]") {
            if(tmp[tmp.length-1] === "[") {
                tmp.pop();
            } else {
                return false;
            }
        }
        if(arr[i] === "}") {
            if(tmp[tmp.length-1] === "{") {
                tmp.pop();
            } else {
                return false;
            }
        }
    }
    return tmp.length===0 ? true : false
};

思路2：利用字符串替代，依次將()旱捧，[]独郎，{}用空字符串替代，替代完畢后枚赡，若字符串長(zhǎng)度為0則說(shuō)明滿足條件氓癌，否則不滿足條件

var isValid = function(s) {
    let len = s.length / 2;
    for(let i=0; i<len; i++) {
        s = s.replace("()", "");
        s = s.replace("[]", "");
        s = s.replace("{}", "");
    }
    return s.length===0 ? true : false
};

5.每日溫度
題目描述：請(qǐng)根據(jù)每日 氣溫 列表，重新生成一個(gè)列表贫橙。對(duì)應(yīng)位置的輸出為：要想觀測(cè)到更高的氣溫贪婉，至少需要等待的天數(shù)。如果氣溫在這之后都不會(huì)升高卢肃，請(qǐng)?jiān)谠撐恢糜?0 來(lái)代替
示例：
輸入：temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
輸出：res = [1, 1, 4, 2, 1, 1, 0, 0]

思路1：暴力解決法疲迂，查找剩余元素是否存在比當(dāng)前值大的值，有則獲得天數(shù)差践剂，沒(méi)有則當(dāng)前位置為0

var dailyTemperatures = function(T) {
    let days = [];
    let len = T.length;
    for(let i=0; i<len; i++) {
        let idx = T.findIndex(item => item>T[0]);
        if(idx === -1) { days.push(0) }
        else { days.push(idx) };
        T.shift();
    }
    return days;
};

思路2：將index入棧鬼譬，然后比較下一個(gè)溫度與棧頂index對(duì)應(yīng)的溫度，若大于逊脯，則在結(jié)果相應(yīng)index處填入下一個(gè)溫度的index與棧頂index的差优质，并將棧頂元素出棧(已找到至少等待天數(shù))；并繼續(xù)將下一個(gè)溫度與棧頂index對(duì)應(yīng)的溫度比較军洼，直至清空椆Γ或小于棧頂index對(duì)應(yīng)的溫度
由于找到大于棧頂index對(duì)應(yīng)溫度的溫度時(shí)就會(huì)將棧頂元素出棧，因此棧內(nèi)index對(duì)應(yīng)的溫度是由大到小的匕争，且說(shuō)明到當(dāng)前遍歷的溫度為止避乏，仍沒(méi)有溫度大于棧內(nèi)index對(duì)應(yīng)的溫度。當(dāng)原溫度列表遍歷完畢后甘桑，棧內(nèi)仍有元素拍皮，則說(shuō)明未找到大于該index對(duì)應(yīng)溫度的溫度，則結(jié)果中該index置0

var dailyTemperatures = function(T) {
    let len = T.length;
    let res = new Array(len).fill(0);
    let stack = [];
    for(let i=0; i<len; i++) {
        while(stack.length!==0 && T[i]>T[stack[stack.length-1]]) {
            let top = stack.pop();
            res[top] = i - top;
        }
        stack.push(i);
    }
    return res;
};

6.逆波蘭表達(dá)式求值
題目描述：根據(jù)[逆波蘭表示法求表達(dá)式的值
示例：
輸入: ["2", "1", "+", "3", "*"]
輸出: 9
解釋: 該算式轉(zhuǎn)化為常見(jiàn)的中綴算術(shù)表達(dá)式為：((2 + 1) * 3) = 9
輸入: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
輸出: 22
解釋:
該算式轉(zhuǎn)化為常見(jiàn)的中綴算術(shù)表達(dá)式為：
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
思路：定義一個(gè)stack棧用來(lái)存儲(chǔ)運(yùn)算需要的數(shù)據(jù)跑杭，遍歷給定數(shù)組铆帽，當(dāng)元素為"+"，"-"德谅，"*"爹橱，"/"時(shí)，從stack棧頂取出兩個(gè)元素進(jìn)行相應(yīng)運(yùn)算并存回stack窄做，當(dāng)元素不為運(yùn)算符號(hào)時(shí)愧驱，將元素轉(zhuǎn)為數(shù)字存入stack棧內(nèi)
運(yùn)算時(shí)減法和除法需注意參與運(yùn)算的數(shù)字的順序

var evalRPN = function(tokens) {
    let operator = ["+", "-", "*", "/"];
    let stack = [];
    let len = tokens.length;
    for(let i=0; i<len; i++) {
        if(operator.includes(tokens[i])) {
            let a = stack.pop();
            let b = stack.pop();
            if(tokens[i] === "+") {
                stack.push(a+b);
            }
            if(tokens[i] === "-") {
                stack.push(b-a);
            }
            if(tokens[i] === "*") {
                stack.push(a*b);
            }
            if(tokens[i] === "/") {
                stack.push(parseInt(b/a));
            }
        } else {
            stack.push(parseInt(tokens[i]));
        }
    }
    return stack[0];
};

7.克隆圖
題目描述：給你無(wú)向連通圖中一個(gè)節(jié)點(diǎn)的引用慰技，請(qǐng)你返回該圖的深拷貝（克隆）组砚。
圖中的每個(gè)節(jié)點(diǎn)都包含它的值 val（int） 和其鄰居的列表（list[Node]）
示例：

克隆圖.png

思路：先拷貝節(jié)點(diǎn)的值吻商，再拷貝相鄰接點(diǎn)
定義一個(gè)哈希表(一個(gè)空對(duì)象)用來(lái)存儲(chǔ)所有節(jié)點(diǎn)，先定義一個(gè)新節(jié)點(diǎn)糟红，拷貝給定節(jié)點(diǎn)的值手报，然后將給定節(jié)點(diǎn)的值作為屬性，新節(jié)點(diǎn)作為屬性值改化，存入哈希表中，并將給定節(jié)點(diǎn)放入隊(duì)列中枉昏；
接下來(lái)拷貝給定節(jié)點(diǎn)的相鄰節(jié)點(diǎn)陈肛，取出隊(duì)列中一個(gè)節(jié)點(diǎn)，查看其相鄰節(jié)點(diǎn)的值是否已存儲(chǔ)在哈希表屬性中兄裂，若是句旱，則將哈希表中對(duì)應(yīng)的值(即對(duì)應(yīng)相鄰節(jié)點(diǎn)的新節(jié)點(diǎn))追加到新節(jié)點(diǎn)的相鄰接點(diǎn)數(shù)組中；若不存在晰奖，則生成一個(gè)只拷貝該相鄰接點(diǎn)值的新節(jié)點(diǎn)谈撒，添加到哈希表中，并將相鄰接點(diǎn)的新節(jié)點(diǎn)追加到新節(jié)點(diǎn)的相鄰接點(diǎn)數(shù)組中匾南，最后將相鄰節(jié)點(diǎn)放入隊(duì)列中啃匿；
不斷取出隊(duì)列中的值，重復(fù)以上操作蛆楞，直至隊(duì)列清空溯乒，最終返回給定節(jié)點(diǎn)的拷貝節(jié)點(diǎn)。

var cloneGraph = function(node) {
    if(!node) return 
    let visited = {};
    let newNode = new Node(node.val, []);
    visited[node.val] = newNode;
    let queue = [];
    queue.push(node);
    while(queue.length !== 0) {
        let curNode = queue.pop();
        for(let item of curNode.neighbors) {
            if(visited.hasOwnProperty(item.val)) {
                visited[curNode.val].neighbors.push(visited[item.val]);
            } else {
                let copyNode = new Node(item.val, []);
                visited[curNode.val].neighbors.push(copyNode);
                visited[item.val] = copyNode;
                queue.push(item);
            }
        }
    }
    return newNode;
};

8.二叉樹(shù)的中序遍歷
題目描述：給定一個(gè)二叉樹(shù)豹爹，返回它的中序遍歷裆悄。
中序遍歷：先左節(jié)點(diǎn)，再根節(jié)點(diǎn)臂聋，后右節(jié)點(diǎn)
示例：
輸入: [1,null,2,3]
1
\
2
/
3

輸出: [1,3,2]

思路一：遞歸方法
使用中序遍歷的遞歸方法光稼，不斷遞歸遍歷左節(jié)點(diǎn)，根節(jié)點(diǎn)和右節(jié)點(diǎn)孩等，直到節(jié)點(diǎn)為null

var inorderTraversal = function(root) {
    if(root === null) {
        return []
    }
    let res = [];
    res = [...res, ...inorderTraversal(root.left)];
    res.push(root.val);
    res = [...res, ...inorderTraversal(root.right)];
    return res;
};

思路2：不使用遞歸
建立一個(gè)棧用來(lái)存儲(chǔ)左子樹(shù)節(jié)點(diǎn)艾君，對(duì)每個(gè)傳入的節(jié)點(diǎn)的左節(jié)點(diǎn)進(jìn)行壓棧處理；由于棧為先進(jìn)后出瞎访，因此能夠滿足最底層的左節(jié)點(diǎn)先輸出腻贰；
新建一個(gè)空數(shù)組，用來(lái)存儲(chǔ)中序遍歷的結(jié)果扒秸；
當(dāng)遍歷到最下層左節(jié)點(diǎn)時(shí)播演，此時(shí)棧頂即為該節(jié)點(diǎn)冀瓦，將該元素出棧，值存入結(jié)果數(shù)組中写烤；
若此節(jié)點(diǎn)含有右節(jié)點(diǎn)翼闽，則對(duì)此節(jié)點(diǎn)的右節(jié)點(diǎn)進(jìn)行壓棧處理，然后遍歷到右節(jié)點(diǎn)最下層的左子節(jié)點(diǎn)洲炊，出棧存值感局，繼續(xù)查看是否含有右節(jié)點(diǎn)，直至此節(jié)點(diǎn)遍歷完成暂衡；
若不含有右節(jié)點(diǎn)询微，或右節(jié)點(diǎn)遍歷完成，則此時(shí)棧頂元素為倒數(shù)第二層左節(jié)點(diǎn)狂巢，重復(fù)上述處理撑毛，直到棧被清空且當(dāng)前節(jié)點(diǎn)指向null

var inorderTraversal = function(root) {
    let stack = [];
    let res = [];
    while(root || stack.length!==0) {
        while(root) {
            stack.push(root);
            root = root.left;
        }
        let top = stack.pop();
        res.push(top.val);
        root = top.right;
    }
    return res;
};

9.字符串解碼
題目描述：給定一個(gè)經(jīng)過(guò)編碼的字符串，返回它解碼后的字符串
編碼規(guī)則為: k[encoded_string]唧领，表示其中方括號(hào)內(nèi)部的 encoded_string 正好重復(fù) k 次藻雌。
條件：

1. k 保證為正整數(shù)
2. 輸入字符串總是有效的；輸入字符串中沒(méi)有額外的空格斩个，且輸入的方括號(hào)總是符合格式要求的
3. 原始數(shù)據(jù)不包含數(shù)字胯杭，所有的數(shù)字只表示重復(fù)的次數(shù) k

示例：
輸入：s = "3[a2[c]]"
輸出："accaccacc"

思路：定義一個(gè)棧stack，將所有遇到的"["的index存儲(chǔ)起來(lái)受啥，這樣當(dāng)遇到"]"時(shí)做个，stack的棧頂值即為"]"對(duì)應(yīng)的"["index值(最后一個(gè)開(kāi)始的括號(hào)總是最先閉合)；
獲取該index與當(dāng)前位置之間的字符串腔呜，即為需要重復(fù)的字符串叁温，求出index前面的數(shù)字(注意數(shù)字可能不止一位)，即為要重復(fù)的次數(shù)核畴；
將需要重復(fù)的字符串重復(fù)指定次數(shù)膝但，并插入到原字符串代替 原字符串中編碼內(nèi)容(即k[encoded_string]部分)；
注意代替完成后谤草，字符串長(zhǎng)度會(huì)發(fā)生變化跟束，需將當(dāng)前位置改變?yōu)樽址嫱瓿珊蟮奈恢?/p>

var decodeString = function(s) {
    let stack = [];
    for(let i=0; i<s.length; i++) {
        if(s[i] === "[") {
            stack.push(i);
        }
        if(s[i] === "]") {
            let pos = stack.pop();
            let data = s.slice(pos+1, i);
            pos = pos-1;
            let k = "";
            while(pos>=0 && !isNaN(parseInt(s[pos]))) {
                k = s[pos] + k;
                pos--;
            }
            k = parseInt(k);
            let str = "";
            while(k>0) {
                str += data;
                k--;
            }
            s = s.slice(0, pos+1) + str + s.slice(i+1);
            i = pos + str.length;  //注意修改i的值
        }
    }
    return s;
};

10.圖像渲染
題目描述：有一幅以二維整數(shù)數(shù)組表示的圖畫，每一個(gè)整數(shù)表示該圖畫的像素值大小丑孩，數(shù)值在 0 到 65535 之間冀宴。
給你一個(gè)坐標(biāo) (sr, sc) 表示圖像渲染開(kāi)始的像素值（行 ，列）和一個(gè)新的顏色值 newColor温学，讓你重新上色這幅圖像略贮。
為了完成上色工作，從初始坐標(biāo)開(kāi)始，記錄初始坐標(biāo)的上下左右四個(gè)方向上像素值與初始坐標(biāo)相同的相連像素點(diǎn)逃延，接著再記錄這四個(gè)方向上符合條件的像素點(diǎn)與他們對(duì)應(yīng)四個(gè)方向上像素值與初始坐標(biāo)相同的相連像素點(diǎn)览妖，……，重復(fù)該過(guò)程揽祥。將所有有記錄的像素點(diǎn)的顏色值改為新的顏色值讽膏。
最后返回經(jīng)過(guò)上色渲染后的圖像。

示例：
輸入:
image = [[1,1,1],[1,1,0],[1,0,1]]
sr = 1, sc = 1, newColor = 2
輸出: [[2,2,2],[2,2,0],[2,0,1]]

思路：小島數(shù)量變形題拄丰，同樣使用DFS府树；
首先判斷給出的新值是否等于舊值，等于則直接返回原圖像料按，否則進(jìn)行修改處理奄侠；
遞歸調(diào)用，遞歸返回條件為(sr<0 || sc<0 || sr===h || sc===w || img[sr][sc]!==oldColor)载矿，即當(dāng)前坐標(biāo)超出圖像范圍或當(dāng)前坐標(biāo)值不等于給定坐標(biāo)的舊值(只修改相連的等于給定坐標(biāo)舊值的值)遭铺；遞歸修改該坐標(biāo)上下左右四個(gè)相鄰像素的值，直到最后全部修改完畢恢准。

var floodFill = function(image, sr, sc, newColor) {
    let h = image.length;
    if(h === 0) return;
    let w = image[0].length;
    let oldColor = image[sr][sc];
    if(oldColor !== newColor)
        modifyColor(image, sr, sc, oldColor, newColor, w, h);
    return image;
};

function modifyColor(img, sr, sc, o, n, w, h) {
    if(sr<0 || sc<0 || sr===h || sc===w || img[sr][sc]!==o) return
    img[sr][sc] = n;
    modifyColor(img, sr-1, sc, o, n, w, h);
    modifyColor(img, sr+1, sc, o, n, w, h);
    modifyColor(img, sr, sc-1, o, n, w, h);
    modifyColor(img, sr, sc+1, o, n, w, h);
}

11. 01 矩陣
題目描述：給定一個(gè)由 0 和 1 組成的矩陣，找出每個(gè)元素到最近的 0 的距離甫题。兩個(gè)相鄰元素間的距離為 1 馁筐。
條件：
給定矩陣的元素個(gè)數(shù)不超過(guò) 10000。
給定矩陣中至少有一個(gè)元素是 0坠非。
矩陣中的元素只在四個(gè)方向上相鄰: 上敏沉、下、左炎码、右盟迟。
示例：
輸入:
0 0 0
0 1 0
1 1 1

輸出:
0 0 0
0 1 0
1 2 1

思路：首先創(chuàng)建結(jié)果矩陣，令原矩陣為0處仍為0潦闲，原矩陣為1處為w+h-2(w攒菠，h分別為原矩陣寬高，最大距離即為w+h-2)歉闰；
最近的0只可能在上下左右四個(gè)相鄰元素辖众，若都不為0，則在它們之中存在距離0最近的和敬，因此只需與它們加1比較取最小值即可

var updateMatrix = function(matrix) {
    let h = matrix.length;
    if(h===0)   return matrix
    let w = matrix[0].length;
    let tmp = [];
    for(let i=0; i<h; i++) {
        tmp[i] = [];
        for(let j=0; j<w; j++) {
            if(matrix[i][j] === 0) {
                tmp[i][j] = 0;
            } else {
                tmp[i][j] = w+h-2;
            }
        }
    }
    for(let i=0; i<h; i++)
        for(let j=0; j<w; j++) {
            if(j>0) {
                tmp[i][j] = Math.min(tmp[i][j], tmp[i][j-1]+1);
            }
            if(i>0) {
                tmp[i][j] = Math.min(tmp[i][j], tmp[i-1][j]+1);
            }
        }
    for(let i=h-1; i>=0; i--)
        for(let j=w-1; j>=0; j--) {
            if(j<w-1) {
                tmp[i][j] = Math.min(tmp[i][j], tmp[i][j+1]+1);
            }
            if(i<h-1) {
                tmp[i][j] = Math.min(tmp[i][j], tmp[i+1][j]+1);
            }
        }
    return tmp;
};

12.鑰匙和房間
題目描述：有 N 個(gè)房間凹炸，開(kāi)始時(shí)你位于 0 號(hào)房間。每個(gè)房間有不同的號(hào)碼：0昼弟，1啤它，2，...，N-1变骡，并且房間里可能有一些鑰匙能使你進(jìn)入下一個(gè)房間离赫。
在形式上，對(duì)于每個(gè)房間 i 都有一個(gè)鑰匙列表 rooms[i]锣光，每個(gè)鑰匙 rooms[i][j] 由 [0,1笆怠，...，N-1] 中的一個(gè)整數(shù)表示誊爹，其中 N = rooms.length蹬刷。 鑰匙 rooms[i][j] = v 可以打開(kāi)編號(hào)為 v 的房間。
最初频丘，除 0 號(hào)房間外的其余所有房間都被鎖住办成。
你可以自由地在房間之間來(lái)回走動(dòng)。
如果能進(jìn)入每個(gè)房間返回 true搂漠，否則返回 false

示例：
輸入: [[1],[2],[3],[]]
輸出: true
解釋:
我們從 0 號(hào)房間開(kāi)始迂卢，拿到鑰匙 1。
之后我們?nèi)?1 號(hào)房間桐汤，拿到鑰匙 2而克。
然后我們?nèi)?2 號(hào)房間，拿到鑰匙 3怔毛。
最后我們?nèi)チ?3 號(hào)房間员萍。
由于我們能夠進(jìn)入每個(gè)房間，我們返回 true

思路：利用棧和BFS拣度，以第0個(gè)房間作為起點(diǎn)碎绎，遍歷每個(gè)房間的鑰匙；
將鑰匙0入棧抗果，創(chuàng)建一個(gè)visited對(duì)象筋帖，將屬性0置為true，將能打開(kāi)的房間數(shù)目count置為1冤馏；
從棧頂取出一個(gè)鑰匙日麸，訪問(wèn)該鑰匙能打開(kāi)的房間，并遍歷其中的鑰匙逮光，若鑰匙已存在與visited中赘淮，則不做處理；若不存在睦霎，則count加1梢卸，放入visited，并將鑰匙入棧副女；
依次從棧頂取出鑰匙蛤高，按照上述步驟處理，直到棧被清空；
最后判斷count是否等于房間長(zhǎng)度戴陡，等于則說(shuō)明房間都能打開(kāi)塞绿，返回true，否則返回false恤批。

var canVisitAllRooms = function(rooms) {
    let len = rooms.length;
    let count = 1;
    let visited = { 0: true };
    let stack = [0];
    while(stack.length) {
        let top = stack.pop();
        let arr = rooms[top];
        for(let i=0; i<arr.length; i++) {
            if(!visited.hasOwnProperty(arr[i])) {
                count++;
                stack.push(arr[i]);
                visited[arr[i]] = true;
            }
        }
    }
    return len===count
};

3.完全平方數(shù)

題目描述：給定正整數(shù) n异吻，找到若干個(gè)完全平方數(shù)（比如 1, 4, 9, 16, ...）使得它們的和等于 n。你需要讓組成和的完全平方數(shù)的個(gè)數(shù)最少喜庞。
示例：
輸入: n = 12
輸出: 3
解釋: 12 = 4 + 4 + 4

思路：有一個(gè)數(shù)學(xué)定理淘邻，任何一個(gè)正整數(shù)都可以表示成不超過(guò)四個(gè)整數(shù)的平方之和总滩，也就是說(shuō)給定一個(gè)正整數(shù)n钱雷，組成它的完全平方數(shù)的個(gè)數(shù)只有1,2,3,4四種可能棠耕；此外有一個(gè)推論，當(dāng)一個(gè)正整數(shù)n只能由四個(gè)完全平方數(shù)組成時(shí)晰房，它必定滿足n=4^a*(8b+7)
由此求摇，我們可以先判斷n是否只能由四個(gè)完全平方數(shù)組成；若為否殊者，由于要返回最少的個(gè)數(shù)与境，因此接下來(lái)再判斷n是否能由1個(gè)完全平方數(shù)組成；仍為否猖吴，判斷n是否能由兩個(gè)完全平方數(shù)組成嚷辅；最后則只能由3個(gè)完全平方數(shù)組成

var numSquares = function(n) {
    while(n%4 === 0) {
        n = n / 4;  //這里并不影響后續(xù)判斷組成n的完全平方數(shù)的個(gè)數(shù)，因?yàn)槿魏瓮耆椒綌?shù)乘4仍為完全平方數(shù)
    }
    if(n%8 === 7) return 4;
    for(let i=0; i*i<=n; i++) {
        if(i*i === n) return 1;
    }
    for(let i=0; i*i<n; i++) {
        if(Number.isInteger(Math.sqrt(n-i*i))) return 2;
    }
    return 3;
};

4.數(shù)組與字符串

數(shù)組與列表的區(qū)別：數(shù)組有索引距误，列表沒(méi)有索引；數(shù)組在內(nèi)存中是連續(xù)存儲(chǔ)的扁位，而列表則不一定
數(shù)組與鏈表的區(qū)別：
數(shù)組在內(nèi)存中是連續(xù)存儲(chǔ)的准潭，而鏈表則不一定；
數(shù)組有索引域仇，鏈表沒(méi)有刑然；
數(shù)組可以根據(jù)索引查找元素，鏈表只能從頭結(jié)點(diǎn)遍歷查找暇务；

1.尋找數(shù)組的中心索引
題目描述：給定一個(gè)整數(shù)類型的數(shù)組 nums泼掠，請(qǐng)編寫一個(gè)能夠返回?cái)?shù)組 “中心索引” 的方法。
我們是這樣定義數(shù)組 中心索引 的：數(shù)組中心索引的左側(cè)所有元素相加的和等于右側(cè)所有元素相加的和垦细。
如果數(shù)組不存在中心索引择镇，那么我們應(yīng)該返回 -1。如果數(shù)組有多個(gè)中心索引括改，那么我們應(yīng)該返回最靠近左邊的那一個(gè)腻豌。
示例：
輸入：
nums = [1, 7, 3, 6, 5, 6]
輸出：3
解釋：
索引 3 (nums[3] = 6) 的左側(cè)數(shù)之和 (1 + 7 + 3 = 11)，與右側(cè)數(shù)之和 (5 + 6 = 11) 相等。
同時(shí), 3 也是第一個(gè)符合要求的中心索引吝梅。

輸入：
nums = [1, 2, 3]
輸出：-1

思路：如果存在中心索引虱疏，那么其左側(cè)的值相加等于其右側(cè)的值相加，即數(shù)組總和減去該索引對(duì)應(yīng)的值除以2應(yīng)該等于其左側(cè)值的和苏携，也等于其右側(cè)值的和做瞪；
我們先求出數(shù)組總和，然后再遍歷數(shù)組右冻，判斷總和減去該索引對(duì)應(yīng)的值再除以2是否等于該索引左側(cè)所有值的和装蓬，等于則說(shuō)明該索引即為中心索引，返回該索引国旷；遍歷完畢尋找不到則說(shuō)明不存在矛物，返回-1。
注意：第二次遍歷判斷時(shí)跪但，要先判斷履羞，再計(jì)算左側(cè)和，因?yàn)樽髠?cè)的和不應(yīng)該包括中心索引對(duì)應(yīng)的值屡久；
另外忆首，當(dāng)遍歷到最后一個(gè)索引值時(shí)，若左側(cè)之和恰好為0被环，則返回最后一個(gè)索引糙及，默認(rèn)其右側(cè)無(wú)值的話，右側(cè)和為0.

var pivotIndex = function(nums) {
    let len = nums.length;
    let sum = 0;
    for(let i=0; i<len; i++) {
        sum += nums[i];
    }
    let left = 0;
    for(let i=0; i<len; i++) {
        if((sum-nums[i])/2 === left) {
            return i
        }
        left += nums[i];
    }
    return -1;
};

2.搜索插入位置
題目描述：給定一個(gè)排序數(shù)組和一個(gè)目標(biāo)值筛欢，在數(shù)組中找到目標(biāo)值浸锨，并返回其索引。如果目標(biāo)值不存在于數(shù)組中版姑，返回它將會(huì)被按順序插入的位置柱搜。
你可以假設(shè)數(shù)組中無(wú)重復(fù)元素。
示例：
輸入: [1,3,5,6], 5
輸出: 2
輸入: [1,3,5,6], 2
輸出: 1

思路一：將元素放入數(shù)組中剥险，然后將數(shù)組重新排序聪蘸，遍歷數(shù)組，找到該元素index表制，返回即可

var searchInsert = function(nums, target) {
    nums.push(target);
    nums.sort((a, b) => a-b);
    return nums.findIndex(item => item===target)
};

思路二：遍歷原數(shù)組健爬，由于原數(shù)組按升序排列，因此找到第一個(gè)大于或等于目標(biāo)值的index返回即可么介；若沒(méi)有元素大于或等于目標(biāo)值娜遵，則目標(biāo)值應(yīng)被插入到最后，返回原數(shù)組長(zhǎng)度即可壤短。

var searchInsert = function(nums, target) {
    let len = nums.length;
    for(let i=0; i<len; i++) {
        if(target <= nums[i])
            return i;
    }
    return len;
};

3.合并區(qū)間
題目描述：
給出一個(gè)區(qū)間的集合魔熏，請(qǐng)合并所有重疊的區(qū)間
示例：
輸入: [[1,3],[2,6],[8,10],[15,18]]
輸出: [[1,6],[8,10],[15,18]]

思路：首先將給定集合intervals按照所有區(qū)間起始位置進(jìn)行升序(起始位置相同時(shí)按照結(jié)束位置進(jìn)行升序)排列衷咽；
定義結(jié)果存儲(chǔ)數(shù)組res，并初始化res=intervals[0]蒜绽；
依次對(duì)intervals所有區(qū)間進(jìn)行合并镶骗，遍歷intervals集合，每次將res[res.length-1]區(qū)間與當(dāng)前intervals[i]區(qū)間進(jìn)行合并躲雅，i由1開(kāi)始(因?yàn)閞es初始化為intervals[0])鼎姊；
判斷前一區(qū)間結(jié)束是否小于后一區(qū)間開(kāi)始，若是則說(shuō)明不重疊相赁，直接返回后一區(qū)間相寇，并追加到res數(shù)組；若否钮科，則說(shuō)明有重疊區(qū)間唤衫，取前一區(qū)間開(kāi)始，前一區(qū)間結(jié)束和后一區(qū)間結(jié)束最大值绵脯，兩者之間即為合并后區(qū)間佳励，返回該區(qū)間，并將res最后一個(gè)元素代替為該區(qū)間蛆挫。

var merge = function(intervals) {
    if(intervals.length < 2) return intervals;
    intervals.sort((a, b) => {
        if(a[0] !== b[0])
            return a[0]-b[0]
        else 
            return a[1]-b[1]
    });
    let res = [intervals[0]];
    for(let i=1; i<intervals.length; i++) {
        let len = res.length;
        let obj = mergeTwo(res[len-1], intervals[i]);
        if(obj.flag) {
            res.pop();           
        } 
        res.push(obj.arr);
    }
    return res;
};

function mergeTwo(arr1, arr2) {
    let s1 = arr1[0], e1 = arr1[1];
    let s2 = arr2[0], e2 = arr2[1];
    if(e1 < s2) {
        return { flag: false, arr: arr2};
    } else {
        return { flag: true, arr: [s1, Math.max(e1, e2)] };
    }
}

4.旋轉(zhuǎn)矩陣
題目描述：給你一幅由 N × N 矩陣表示的圖像赃承，其中每個(gè)像素的大小為 4 字節(jié)。請(qǐng)你設(shè)計(jì)一種算法悴侵，將圖像旋轉(zhuǎn) 90 度瞧剖。不占用額外內(nèi)存空間能否做到
示例：
給定 matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],
原地旋轉(zhuǎn)輸入矩陣，使其變?yōu)?
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]

思路一：將原矩陣第一維反轉(zhuǎn)可免，然后將對(duì)角線兩側(cè)對(duì)應(yīng)元素互換即可

var rotate = function(matrix) {
    let h = matrix.length;
    if(h<2) return matrix;
    let w = matrix[0].length;
    matrix = matrix.reverse();
    for(let i=0; i<h-1; i++)
        for(let j=i+1; j<w; j++) {
            matrix[i][j] = matrix[i][j] + matrix[j][i];
            matrix[j][i] = matrix[i][j] - matrix[j][i];
            matrix[i][j] = matrix[i][j] - matrix[j][i];
        }
    return matrix;
};

思路2：將矩陣自下向上每一行的元素抓于，依次放至每一行后面，例如將最后一行N個(gè)元素浇借，分別放到N行后面捉撮，相當(dāng)于在矩陣后添加一列；
全部添加完畢后逮刨，將每一行前N個(gè)元素刪除，則剩余矩陣即為旋轉(zhuǎn)后的矩陣堵泽。

var rotate = function(matrix) {
    let N = matrix.length;
    if(N<2) return matrix;
    for(let i=N-1; i>=0; i--)
        for(let j=0; j<N; j++) {
            matrix[j].push(matrix[i][j]);
        }
    for(let i=0; i<N; i++){
        matrix[i].splice(0, N);
    }
    return matrix;
};

5.零矩陣
題目描述：編寫一種算法修己，若M × N矩陣中某個(gè)元素為0，則將其所在的行與列清零
示例：
輸入：
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
輸出：
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]

思路一：先遍歷整個(gè)矩陣迎罗，將矩陣中為0的元素所在的行和列的索引值分別利用一個(gè)數(shù)組(zeroRow睬愤，zeroCol)存起來(lái)；
再次遍歷矩陣纹安，若該元素的行或列的索引在zeroRow或zeroCol中尤辱，則將該元素置0砂豌，否則說(shuō)明該元素所在行列均沒(méi)有0元素存在，保持元素值不變光督。

var setZeroes = function(matrix) {
    let h = matrix.length;
    if(h === 0) return matrix;
    let w = matrix[0].length;
    let zeroRow = [], zeroCol = [];
    for(let i=0; i<h; i++)
        for(let j=0; j<w; j++) {
            if(matrix[i][j] === 0) {
                if(!zeroRow.includes(i)) {
                    zeroRow.push(i);
                }
                if(!zeroCol.includes(j)) {
                    zeroCol.push(j);
                }
            }
        }
    for(let i=0; i<h; i++)
        for(let j=0; j<w; j++) {
            if(zeroRow.includes(i) || zeroCol.includes(j)) {
                matrix[i][j] = 0;
            }
        }
    return matrix;
};

思路二：將原矩陣復(fù)制一份阳距，遍歷判斷新矩陣中元素是否為0，若是則將原矩陣對(duì)應(yīng)行列置0结借，最終返回原矩陣筐摘；
復(fù)制一份是為了避免直接修改原矩陣，使得矩陣最終全為0;船老。

var setZeroes = function(matrix) {
    let h = matrix.length;
    if(h === 0) return matrix;
    let w = matrix[0].length;
    let newMatrix = JSON.parse(JSON.stringify(matrix));
    for(let i=0; i<h; i++)
        for(let j=0; j<w; j++) {
            if(newMatrix[i][j] === 0) {
                for(let i1=0; i1<h; i1++) {
                    matrix[i1][j] = 0;
                }
                for(let j1=0; j1<w; j1++) {
                    matrix[i][j1] = 0;
                }
            }
        }
    return matrix;
};

6.對(duì)角線遍歷
題目描述：給定一個(gè)含有 M x N 個(gè)元素的矩陣（M 行咖熟，N 列），請(qǐng)以對(duì)角線遍歷的順序返回這個(gè)矩陣中的所有元素柳畔，對(duì)角線遍歷如下圖所示
示例：
輸入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]

輸出: [1,2,4,7,5,3,6,8,9]
解釋:

對(duì)角線遍歷

思路：對(duì)角線上的元素滿足腳標(biāo)之和相等馍管，如(0,1)(1,0)，(2,0)(1,1)(0,2)薪韩；
則每遍歷一條對(duì)角線确沸，就是將所有腳標(biāo)之和等于該條對(duì)角線index(第1條，第2條等)的元素找出并按順序存入結(jié)果數(shù)組躬存；
順序在對(duì)角線index為偶數(shù)時(shí)為自下向上(即y坐標(biāo)不斷減小)张惹，在對(duì)角線index為奇數(shù)時(shí)，自上向下(即x坐標(biāo)不斷減小)岭洲；
遍歷每條對(duì)角線宛逗，判斷該對(duì)角線index為奇數(shù)還是偶數(shù)；
當(dāng)index為奇數(shù)時(shí)盾剩，令x值取最大(min(index, w-1))雷激，并令x不斷減小，直至x等于0(到達(dá)最左端)或index-x等于h-1(到達(dá)最下端)告私；
當(dāng)index為偶數(shù)時(shí)屎暇，令y值取最大(min(index, h-1))，并令y不斷減小驻粟，直至y等于0(到達(dá)最上端)或index-y等于w-1(到達(dá)最右端)根悼；

var findDiagonalOrder = function(matrix) {
    let h = matrix.length;
    if(h === 0) return matrix;
    let w = matrix[0].length;
    let res = [];
    for(let i=0; i<h+w-1; i++) {
        let xMax = i>w-1 ? w-1 : i;
        let yMax = i>h-1 ? h-1 : i;
        if(i%2 === 0) {
            let y = yMax;
            while(y>=0 && (i-y)<w) {
                res.push(matrix[y][i-y]);
                y--;
            }
        } else {
            let x = xMax;
            while(x>=0 && (i-x)<h) {
                res.push(matrix[i-x][x]);
                x--;
            }
        }
    }
    return res;
};

7.最長(zhǎng)公共前綴
題目描述：編寫一個(gè)函數(shù)來(lái)查找字符串?dāng)?shù)組中的最長(zhǎng)公共前綴，如果不存在公共前綴蜀撑，返回空字符串 ""
示例：
輸入: ["flower","flow","flight"]
輸出: "fl"
輸入: ["dog","racecar","car"]
輸出: ""

思路：首先找出字符串?dāng)?shù)組中最短的字符串挤巡，然后依次判斷是否所有字符串均以該字符串為開(kāi)頭，是酷麦，則返回該字符串矿卑，否，將該字符串去掉末尾字符沃饶，再依次檢測(cè)母廷，直至找到所有字符串均相同的前綴轻黑，返回該前綴，或所有字符串找不到相同前綴琴昆，返回""

var longestCommonPrefix = function(strs) {
    if(strs.length === 0)  return ""
    let str = strs[0];
    let minLen = strs[0].length;
    for(let i=1; i<strs.length; i++) {
        if(strs[i].length < minLen) {
            minLen = strs[i].length;
            str = strs[i];
        }
    }
    let flag;
    for(let i=minLen; i>0; i--){
        str = str.slice(0, i);
        flag = true;
        for(let j=0; j<strs.length; j++){
            if(!strs[j].startsWith(str)) {
                flag = false;
                break;
            }
        }
        if(flag) {
            break;
        }
    }
    if(!flag)   return "";
    return str;
};

8.翻轉(zhuǎn)字符串里的單詞
題目描述：給定一個(gè)字符串氓鄙，逐個(gè)翻轉(zhuǎn)字符串中的每個(gè)單詞。
無(wú)空格字符構(gòu)成一個(gè)單詞椎咧。
輸入字符串可以在前面或者后面包含多余的空格玖详，但是反轉(zhuǎn)后的字符不能包括。
如果兩個(gè)單詞間有多余的空格勤讽，將反轉(zhuǎn)后單詞間的空格減少到只含一個(gè)蟋座。

示例：
輸入: "?? hello world! ?? "
輸出: "world! hello"
輸入: "a good? ? ? example"
輸出: "example good a"

思路：去掉首尾空格，利用正則全局替換將多個(gè)空格替換為單個(gè)空格脚牍，再按空格切割為數(shù)組向臀，之后反轉(zhuǎn)數(shù)組，最后再以空格拼接數(shù)組為字符串诸狭，返回即可券膀。

var reverseWords = function(s) {
    return s.trim().replace(/\s+/g, " ").split(" ").reverse().join(" ");
};

9.實(shí)現(xiàn) strStr()
題目描述：給定一個(gè) haystack 字符串和一個(gè) needle 字符串，在 haystack 字符串中找出 needle 字符串出現(xiàn)的第一個(gè)位置 (從0開(kāi)始)驯遇。如果不存在芹彬，則返回 -1
示例：
輸入: haystack = "hello", needle = "ll"
輸出: 2
輸入: haystack = "aaaaa", needle = "bba"
輸出: -1

思路：使用indexOf()或search()函數(shù)，測(cè)試結(jié)果indexOf用時(shí)72ms叉庐，search用時(shí)96ms
注：針對(duì)空字符串""舒帮，indexOf和search均返回0

var strStr = function(haystack, needle) {
    if(needle === "") return 0;
    // return haystack.search(needle)
    return haystack.indexOf(needle)
};

10.反轉(zhuǎn)字符串
題目描述：編寫一個(gè)函數(shù)，其作用是將輸入的字符串反轉(zhuǎn)過(guò)來(lái)陡叠。輸入字符串以字符數(shù)組 char[]的形式給出玩郊。
不要給另外的數(shù)組分配額外的空間，你必須原地修改輸入數(shù)組枉阵、使用 O(1) 的額外空間解決這一問(wèn)題译红。
你可以假設(shè)數(shù)組中的所有字符都是 [ASCII]碼表中的可打印字符。
示例：
輸入：["h","e","l","l","o"]
輸出：["o","l","l","e","h"]
輸入：["H","a","n","n","a","h"]
輸出：["h","a","n","n","a","H"]
思路：利用reverse函數(shù)或雙指針?lè)崔D(zhuǎn)兴溜，雙指針定義兩個(gè)指針侦厚，一個(gè)從頭開(kāi)始，一個(gè)從尾開(kāi)始拙徽，依次交換刨沦，直到相遇
運(yùn)行結(jié)果，雙指針運(yùn)行132ms斋攀，reverse函數(shù)120ms

var reverseString = function(s) {
    let len = s.length;
    if(len < 2) return s;
    let i=0, j=len-1;
    let tmp = "";
    while(i<j) {
        tmp = s[i];
        s[i] = s[j];
        s[j] = tmp;
        i++;
        j--;
    }
    return s;
    // return s.reverse();
};

11.長(zhǎng)度最小的子數(shù)組
題目描述：給定一個(gè)含有 n 個(gè)正整數(shù)的數(shù)組和一個(gè)正整數(shù) s 已卷，找出該數(shù)組中滿足其和 ≥ s 的長(zhǎng)度最小的 連續(xù) 子數(shù)組梧田，并返回其長(zhǎng)度淳蔼。如果不存在符合條件的子數(shù)組侧蘸，返回 0
示例：
輸入：s = 7, nums = [2,3,1,2,4,3]
輸出：2
解釋：子數(shù)組 [4,3] 是該條件下的長(zhǎng)度最小的子數(shù)組

思路：利用雙指針，定義兩個(gè)指針鹉梨，start和end讳癌，定義子數(shù)組之和sum；
開(kāi)始start靜止不動(dòng)存皂，end后移晌坤，sum不斷累加end對(duì)應(yīng)的數(shù)組值，由于給定為正整數(shù)數(shù)組旦袋，因此sum的值逐漸增大骤菠，當(dāng)sum大于等于給定s時(shí)，end暫停疤孕，記錄下此時(shí)子數(shù)組長(zhǎng)度(end-start+1)商乎；
start不斷后移，并且sum值減去start對(duì)應(yīng)的數(shù)組值祭阀，直到sum小于s鹉戚，此過(guò)程中子數(shù)組不斷縮小，要注意更新最小子數(shù)組長(zhǎng)度专控；
end繼續(xù)后移抹凳，直到sum再次大于等于s，重復(fù)上述步驟伦腐，不斷更新最小子數(shù)組長(zhǎng)度赢底，直至end遍歷到數(shù)組末尾；
初始子數(shù)組長(zhǎng)度設(shè)置為給定數(shù)組長(zhǎng)度加1(若數(shù)組中有子數(shù)組元素之和大于等于s蔗牡，則子數(shù)組長(zhǎng)度至多為給定數(shù)組長(zhǎng)度)颖系，最后判斷最小子數(shù)組長(zhǎng)度是否等于初始值，等于則說(shuō)明整個(gè)數(shù)組之和仍小于s辩越，返回0嘁扼，否則返回最小子數(shù)組長(zhǎng)度

var minSubArrayLen = function(s, nums) {
    let start = 0, end = 0, sum = 0, ans = nums.length+1;
    while(end < nums.length) {
        sum += nums[end];
        while(sum >= s) {
            if((end-start+1) < ans)
                ans = end - start + 1;
            sum -= nums[start];
            start++;
        }
        end++;
    }
    if(ans === nums.length+1)   return 0;
    return ans;
};

12.復(fù)原IP地址
題目描述：給定一個(gè)只包含數(shù)字的字符串，復(fù)原它并返回所有可能的 IP 地址格式黔攒。
有效的 IP 地址正好由四個(gè)整數(shù)（每個(gè)整數(shù)位于 0 到 255 之間組成）趁啸，整數(shù)之間用 '.' 分隔。
示例：
輸入: "25525511135"
輸出: ["255.255.11.135", "255.255.111.35"]

思路：每個(gè)整數(shù)最少一位督惰，最多三位不傅，四層循環(huán)，分別代表第一赏胚、二访娶、三、四四個(gè)整數(shù)的長(zhǎng)度觉阅，當(dāng)它們相加等于字符串長(zhǎng)度時(shí)崖疤，說(shuō)明可能是有效的IP地址秘车；
然后將原字符串按照四個(gè)長(zhǎng)度切成四個(gè)子字符串，判斷四個(gè)子字符串轉(zhuǎn)成整數(shù)后是否符合IP地址規(guī)則劫哼，要求有小于255叮趴，除非長(zhǎng)度為1否則不能以0為開(kāi)始，滿足則返回true权烧，否則返回false眯亦；
當(dāng)四個(gè)子字符串均滿足要求時(shí)，說(shuō)明為合法IP地址般码，放入結(jié)果數(shù)組中妻率，若有一個(gè)不滿足，則說(shuō)明不合法板祝，則繼續(xù)循環(huán)尋找舌涨，直到結(jié)束。

var restoreIpAddresses = function(s) {
    let res = [];
    for(let a=1; a<4; a++)
        for(let b=1; b<4; b++)
            for(let c=1; c<4; c++)
                for(let d=1; d<4; d++) {
                    if(a+b+c+d === s.length) {
                        let n1 = s.slice(0, a);
                        let n2 = s.slice(a, a+b);
                        let n3 = s.slice(a+b, a+b+c);
                        let n4 = s.slice(a+b+c);
                        if(valid(n1) && valid(n2) && valid(n3) && valid(n4)) {
                            res.push(n1 + "." + n2 + "." + n3 + "." + n4);
                        }
                    }
                }
    return res;
};

function valid(str) {
    if(parseInt(str) <= 255) {
        if(str[0]!=='0' || (str[0]==='0' && str.length===1)) {
            return true;
        }
    }
    return false;
}

13.數(shù)組快排
思路一：利用額外空間存儲(chǔ)left和right扔字，遞歸調(diào)用快排函數(shù)對(duì)left和right進(jìn)行排序囊嘉，直到排序數(shù)組為空則返回空數(shù)組，或排序數(shù)組長(zhǎng)度為1返回原數(shù)組革为；最終將排好序的left和right以及參考數(shù)值pivot拼接起來(lái)返回即可

function quickSort(arr) {
    if(arr.length === 0)   return [];
    if(arr.length === 1)   return arr;
    let pivot = arr[0];
    let len = arr.length;
    let left = [], right = [];
    for(let i=1; i<len; i++) {
        if(arr[i] <= pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    left = quickSort(left);
    right = quickSort(right);
    return [...left, pivot, ...right];
}

思路二：不占用額外空間扭粱，直接對(duì)數(shù)組進(jìn)行操作；
選取最右端數(shù)組值為參考值震檩，定義index初始化為最左端的索引琢蛤，從最左端到最右端遍歷比較每個(gè)值是否小于參考值，小于則將該值與index對(duì)應(yīng)值交換抛虏，并將index加1(即博其，將小于參考值的數(shù)組值依次放到前面)；
遍歷完成后將最右側(cè)數(shù)組值與當(dāng)前index對(duì)應(yīng)值交換迂猴，則此時(shí)index左側(cè)均為小于參考值的值慕淡，右側(cè)均為大于參考值的值；
將數(shù)組左側(cè)和右側(cè)再遞歸調(diào)用排序函數(shù)進(jìn)行排序沸毁，直至最終排序完成峰髓；
結(jié)束條件為要排序的子數(shù)組長(zhǎng)度為0，即傳入的左側(cè)索引值大于右側(cè)索引值息尺。

function quickSort(left, right) {
    if(left > right)   return;
    let pivot = arr[right];
    let index = left;
    for(let i=left; i<right; i++) {
        if(arr[i] < pivot) {
            swap(arr, i, index);
            index++;
        }
    }
    swap(arr, right, index);
    quickSort(left, index-1);
    quickSort(index+1, right);
}

function swap(arr, i, j) {
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

quickSort(0, arr.length-1)

14.買賣股票的最佳時(shí)機(jī)
題目描述：給定一個(gè)數(shù)組携兵，它的第 i 個(gè)元素是一支給定股票第 i 天的價(jià)格。
如果你最多只允許完成一筆交易（即買入和賣出一支股票一次）搂誉，設(shè)計(jì)一個(gè)算法來(lái)計(jì)算你所能獲取的最大利潤(rùn)徐紧。
注意：你不能在買入股票前賣出股票。
示例 :
輸入: [7,1,5,3,6,4]
輸出: 5
解釋: 在第 2 天（股票價(jià)格 = 1）的時(shí)候買入，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣出并级，最大利潤(rùn) = 6-1 = 5 巴柿。
注意利潤(rùn)不能是 7-1 = 6, 因?yàn)橘u出價(jià)格需要大于買入價(jià)格；同時(shí)死遭，你不能在買入前賣出股票。
輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒(méi)有交易完成, 所以最大利潤(rùn)為 0凯旋。

思路：尋找最大利潤(rùn)呀潭，即尋找數(shù)組最大差值，且大值在小值右側(cè)至非；
假設(shè)最大利潤(rùn)maxProfit最初為0钠署，最小股價(jià)minPrice最初為最大值(Number.MAX_SAFE_INTEGER，保證股價(jià)不會(huì)超出此值)荒椭，然后遍歷整個(gè)數(shù)組谐鼎；
當(dāng)股價(jià)小于當(dāng)前最小股價(jià)時(shí)，將最小股價(jià)改為此值趣惠，否則判斷當(dāng)前股價(jià)減去最小股價(jià)是否大于當(dāng)前最大利潤(rùn)狸棍，大于則更新最大利潤(rùn)；
這樣遍歷完畢即可找出最大利潤(rùn)味悄。

var maxProfit = function(prices) {
    let minPrice = Number.MAX_SAFE_INTEGER;
    let maxProfit = 0;
    for(let i=0; i<prices.length; i++) {
        if(prices[i] < minPrice) {
            minPrice = prices[i];
        } else {
            maxProfit = Math.max(maxProfit, prices[i]-minPrice);
        }
    }
    return maxProfit;
};

15.數(shù)組中的第K個(gè)最大元素
題目描述：在未排序的數(shù)組中找到第 k 個(gè)最大的元素草戈。請(qǐng)注意，你需要找的是數(shù)組排序后的第 k 個(gè)最大的元素侍瑟，而不是第 k 個(gè)不同的元素唐片。
示例 :
輸入: [3,2,1,5,6,4] 和 k = 2
輸出: 5

思路一：將數(shù)組降序排序，取第k-1個(gè)值即可

var findKthLargest = function(nums, k) {
    nums.sort((a, b) => b-a);
    return nums[k-1];
};

思路二：利用快排思想涨颜，取出一個(gè)值作為參考值费韭，選取參考值時(shí)要隨機(jī)選取，這樣可以使平均復(fù)雜度降低庭瑰，index初始化為0星持；
將大于參考值的值與index所在值交換，同時(shí)index右移弹灭，遍歷完整個(gè)數(shù)組后钉汗，將參考值與index所在值交換，這樣大于參考值的值都在參考值左側(cè)鲤屡，小于參考值的值都在參考值右側(cè)损痰；
判斷當(dāng)前參考值index是否等于k-1，等于則說(shuō)明參考值即所求值酒来；
否則卢未，若index小于k-1，則說(shuō)明在所求值在其右側(cè)，對(duì)其右側(cè)如上述步驟同樣處理辽社；
若index大于k-1伟墙，則說(shuō)明所求值在其左側(cè)，對(duì)其左側(cè)如上述步驟同樣處理滴铅；直至尋找到相應(yīng)index戳葵。

var findKthLargest = function(nums, k) {
    function quickSort(left, right) {
        let random = Math.floor(Math.random() * (right-left+1)) + left;
        let pivot = nums[random];
        swap(random, right);
        let index = left;
        for(let i=left; i<right; i++) {
            if(nums[i] > pivot) {
                swap(index, i);
                index++;
            }
        }
        swap(index, right);
        if(index === k-1) {
            return nums[index];
        }
        let res;
        if(index < k-1) {
            res = quickSort(index+1, right);
        }
        if(index > k-1) {
            res = quickSort(left, index-1);
        }
        return res;
    }

    function swap(i, j) {
        let tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    return quickSort(0, nums.length-1);
};

16.數(shù)組拆分 I
題目描述：給定長(zhǎng)度為 2n 的數(shù)組, 你的任務(wù)是將這些數(shù)分成 n 對(duì), 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得從1 到 n 的 min(ai, bi) 總和最大
示例 1:
輸入: [1,4,3,2]
輸出: 4
解釋: n 等于 2, 最大總和為 4 = min(1, 2) + min(3, 4)

思路：將數(shù)組升序排列汉匙，相鄰值相差最小拱烁，取第0,2，...,2n-2個(gè)元素相加即可得到最終結(jié)果

var arrayPairSum = function(nums) {
    let sum = 0;
    nums.sort((a, b) => a-b);
    for(let i=0; i<nums.length; i=i+2) {
        sum += nums[i];
    }
    return sum;
};

17.兩數(shù)之和 II - 輸入有序數(shù)組
題目描述：
給定一個(gè)已按照升序排列 的有序數(shù)組噩翠，找到兩個(gè)數(shù)使得它們相加之和等于目標(biāo)數(shù)戏自。
函數(shù)應(yīng)該返回這兩個(gè)下標(biāo)值 index1 和 index2，其中 index1 必須小于 index2伤锚。
說(shuō)明:
返回的下標(biāo)值（index1 和 index2）不是從零開(kāi)始的擅笔。
你可以假設(shè)每個(gè)輸入只對(duì)應(yīng)唯一的答案，而且你不可以重復(fù)使用相同的元素屯援。
示例：
輸入: numbers = [2, 7, 11, 15], target = 9
輸出: [1,2]
解釋: 2 與 7 之和等于目標(biāo)數(shù) 9 猛们。因此 index1 = 1, index2 = 2

思路：設(shè)置兩個(gè)指針，start=0狞洋，end=numbers.length-1阅懦，循環(huán)判斷numbers[start]+numbers[end]是否等于target，等于則返回[start+1, end+1]徘铝；若小于target則start++耳胎；若大于target則end--。

var twoSum = function(numbers, target) {
    if(numbers.length < 2)  return -1;
    let start = 0, end = numbers.length-1;
    while(start < end) {
        if(numbers[start]+numbers[end] === target) {
            return [start+1, end+1];
        }
        if(numbers[start]+numbers[end] < target) {
            start++;
        }
        if(numbers[start]+numbers[end] > target) {
            end--;
        }
    }
    return -1;
};

18.移除元素
題目描述：給你一個(gè)數(shù)組 nums 和一個(gè)值 val惕它，你需要 原地移除所有數(shù)值等于 val 的元素怕午，并返回移除后數(shù)組的新長(zhǎng)度。
不要使用額外的數(shù)組空間淹魄，你必須僅使用 O(1) 額外空間并 原地修改輸入數(shù)組郁惜。
元素的順序可以改變。你不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素甲锡。
示例：
給定 nums = [3,2,2,3], val = 3,
函數(shù)應(yīng)該返回新的長(zhǎng)度 2, 并且 nums 中的前兩個(gè)元素均為 2兆蕉。
你不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素。

思路：給定一個(gè)slow指針缤沦，初始化為0虎韵，遍歷數(shù)組，當(dāng)數(shù)組元素不等于給定val時(shí)缸废，nums[slow]=nums[i]后专，同時(shí)slow后移一位，最終返回slow的值

var removeElement = function(nums, val) {
    let slow = 0;
    for(let i=0; i<nums.length; i++) {
        if(nums[i] !== val) {
            nums[slow] = nums[i];
            slow++;
        }
    }
    return slow;
    
};

19.最大連續(xù)1的個(gè)數(shù)
題目描述：給定一個(gè)二進(jìn)制數(shù)組掉盅， 計(jì)算其中最大連續(xù)1的個(gè)數(shù)
示例：
輸入: [1,1,0,1,1,1]
輸出: 3
解釋: 開(kāi)頭的兩位和最后的三位都是連續(xù)1，所以最大連續(xù)1的個(gè)數(shù)是 3

思路：設(shè)定一個(gè)指針slow=0埂蕊，最大連續(xù)1長(zhǎng)度maxLen=0，遍歷數(shù)組，當(dāng)數(shù)組元素等于1時(shí)，判斷i-slow+1是否大于maxLen份乒，大于則更新maxLen；若數(shù)組元素不等于1腕唧，則slow=i+1(當(dāng)數(shù)組元素不等于1時(shí)或辖，slow永遠(yuǎn)指向下一個(gè)元素，直到數(shù)組元素等于1)

var findMaxConsecutiveOnes = function(nums) {
    let slow = 0;
    let maxLen = 0;
    for(let i=0; i<nums.length; i++) {
        if(nums[i] === 1) {
            if(i-slow+1 > maxLen) {
                maxLen = i-slow+1;
            }
        } else {
            slow = i+1;
        }
    }
    return maxLen;
};

20.楊輝三角
題目描述：給定一個(gè)非負(fù)整數(shù) numRows四苇，生成楊輝三角的前 numRows 行

楊輝三角.gif

var generate = function(numRows) {
    if(numRows === 0)   return [];
    if(numRows === 1)   return [[1]];
    if(numRows === 2)   return  [[1], [1, 1]];
    let res = [[1], [1, 1]];
    for(let i=2; i<numRows; i++) {
        let arr = [];
        for(let j=0; j<i-1; j++) {
            arr.push(res[i-1][j] + res[i-1][j+1]);
        }
        arr.push(1);
        arr.unshift(1);
        res.push(arr);
    }
    return res;
};

21.楊輝三角 II
題目描述：給定一個(gè)非負(fù)索引 k，其中 k ≤ 33瓣赂，返回楊輝三角的第 k 行榆骚，你可以優(yōu)化你的算法到 O(k) 空間復(fù)雜度嗎？
示例:
輸入: 3
輸出: [1,3,3,1]
說(shuō)明：第0行為[1]煌集，第一行為[1,1]

思路：對(duì)于給定第k行妓肢，其第一個(gè)元素等于其上層第k-1行第一個(gè)元素和第二個(gè)元素之和，第二個(gè)元素等于其上層第二個(gè)和第三個(gè)元素之和苫纤，以此類推碉钠，只需令arr[0]=arr[0]+arr[1]，arr[1]=arr[1]+arr[2]..., arr[i]=arr[i]+arr[i+1]卷拘，一直到上一層相加完畢喊废；假設(shè)上一層長(zhǎng)度為n，則此時(shí)數(shù)組長(zhǎng)度仍為n栗弟，且前n-1個(gè)元素分別是上層元素相鄰元素之和污筷，最后一個(gè)元素仍為1；最后在新數(shù)組前加入一個(gè)1即可乍赫；
循環(huán)調(diào)用此函數(shù)瓣蛀，直到達(dá)到要求的k行。

var getRow = function(rowIndex) {
    if(rowIndex === 0)  return [1];
    if(rowIndex === 1)  return [1, 1];
    let arr = [1, 1];
    function getK() {
        for(let i=0; i<arr.length-1; i++) {
            arr[i] = arr[i] + arr[i+1];
        }
        arr.unshift(1);
    }
    while(rowIndex > 1) {
        getK();
        rowIndex--;
    }
    return arr;
};

22.刪除排序數(shù)組中的重復(fù)項(xiàng)
題目描述：給定一個(gè)排序數(shù)組雷厂，你需要在原地刪除重復(fù)出現(xiàn)的元素惋增，使得每個(gè)元素只出現(xiàn)一次，返回移除后數(shù)組的新長(zhǎng)度改鲫。
不要使用額外的數(shù)組空間器腋，你必須在原地修改輸入數(shù)組 并在使用 O(1) 額外空間的條件下完成
示例：
給定 nums = [0,0,1,1,1,2,2,3,3,4],
函數(shù)應(yīng)該返回新的長(zhǎng)度 5, 并且原數(shù)組 nums 的前五個(gè)元素被修改為 0, 1, 2, 3, 4。
你不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素。

思路：設(shè)定慢指針slow=0纫塌，遍歷nums數(shù)組诊县，當(dāng)nums[i]!==nums[slow]時(shí)，slow++措左，并令nums[slow]=nums[i]依痊，最后返回slow+1；注意當(dāng)nums長(zhǎng)度為0時(shí)怎披，直接返回0.

var removeDuplicates = function(nums) {
    if(nums.length === 0)   return 0;
    let slow = 0;
    for(let i=0; i<nums.length; i++) {
        if(nums[slow] !== nums[i]) {
            slow++;
            nums[slow] = nums[i];    
        }
    }
    return slow+1;
};

23.移動(dòng)零
題目描述：給定一個(gè)數(shù)組 nums胸嘁，編寫一個(gè)函數(shù)將所有 0 移動(dòng)到數(shù)組的末尾，同時(shí)保持非零元素的相對(duì)順序凉逛。
示例：
輸入: [0,1,0,3,12]
輸出: [1,3,12,0,0]

思路：遍歷數(shù)組性宏，判斷元素是否為0，為0則刪除該元素状飞，并在數(shù)組后方push一個(gè)0毫胜；
注意每次刪除當(dāng)前0元素后，由于下一個(gè)元素index變成了當(dāng)前index诬辈，因此需要將i--酵使；另外，由于只需要遍歷原數(shù)組長(zhǎng)度焙糟，因此初始先設(shè)定len=nums.length口渔，每次刪除元素，i--后穿撮，len也要相應(yīng)進(jìn)行l(wèi)en--缺脉。

var moveZeroes = function(nums) {
    let len = nums.length;
    for(let i=0; i<len; i++){
        if(nums[i] === 0) {
            nums.splice(i, 1);
            i--;
            len--;
            nums.push(0);
        }
    }
    return nums;
};

24.無(wú)重復(fù)字符的最長(zhǎng)子串
題目描述：給定一個(gè)字符串，請(qǐng)你找出其中不含有重復(fù)字符的 最長(zhǎng)子串 的長(zhǎng)度
示例：
輸入: "pwwkew"
輸出: 3
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "wke"悦穿，所以其長(zhǎng)度為 3枪向。
請(qǐng)注意，你的答案必須是 子串 的長(zhǎng)度咧党，"pwke" 是一個(gè)子序列秘蛔，不是子串

思路：初始化最大不重復(fù)子串長(zhǎng)度maxLen為0，初始化一個(gè)visited空數(shù)組傍衡；
遍歷字符串深员，當(dāng)visited中不含有當(dāng)前字符時(shí)，說(shuō)明沒(méi)有重復(fù)字符蛙埂，則visited數(shù)組push入該字符倦畅，并令maxLen=Math.max(maxLen, visited.length)，更新最大長(zhǎng)度绣的；
若visited中含有該字符叠赐，說(shuō)明出現(xiàn)重復(fù)字符欲账，則將visited第一次出現(xiàn)該字符及其前面的字符刪除，重新push該字符芭概，然后繼續(xù)遍歷赛不，重復(fù)上述步驟，直到遍歷完成

var lengthOfLongestSubstring = function(s) {
    let maxLen = 0;
    let visited = [];
    for(let i=0; i<s.length; i++) {
        let idx = visited.indexOf(s[i]);
        if(idx !== -1) {
            visited.splice(0, idx+1);
        }
        visited.push(s[i]);
        maxLen = Math.max(maxLen, visited.length);
    }
    return maxLen;
};

5.二叉樹(shù)

1.求根到葉子節(jié)點(diǎn)數(shù)字之和
題目描述：給定一個(gè)二叉樹(shù)罢洲，它的每個(gè)結(jié)點(diǎn)都存放一個(gè) 0-9 的數(shù)字踢故，每條從根到葉子節(jié)點(diǎn)的路徑都代表一個(gè)數(shù)字。
例如惹苗，從根到葉子節(jié)點(diǎn)路徑 1->2->3 代表數(shù)字 123殿较。
計(jì)算從根到葉子節(jié)點(diǎn)生成的所有數(shù)字之和。
示例：
輸入: [1,2,3]
?1
/ \
2 ?3
輸出: 25
解釋:
從根到葉子節(jié)點(diǎn)路徑 1->2 代表數(shù)字 12.
從根到葉子節(jié)點(diǎn)路徑 1->3 代表數(shù)字 13.
因此桩蓉，數(shù)字總和 = 12 + 13 = 25.

思路：深度優(yōu)先遍歷淋纲；
初始值設(shè)為0，判斷當(dāng)前節(jié)點(diǎn)是否為空節(jié)點(diǎn)院究，是則直接返回洽瞬，不是則將此值乘10加上當(dāng)前節(jié)點(diǎn)的值存起來(lái)設(shè)為當(dāng)前值；
判斷當(dāng)前節(jié)點(diǎn)是否沒(méi)有子節(jié)點(diǎn)儡首，沒(méi)有則說(shuō)明到底片任，將當(dāng)前值加入總和偏友，返回蔬胯；有子節(jié)點(diǎn)說(shuō)明還未到底，繼續(xù)遞歸遍歷其子節(jié)點(diǎn)位他；
當(dāng)所有節(jié)點(diǎn)被遍歷完成氛濒，返回總和。

var sumNumbers = function(root) {
    let sum = 0;
    function dfs(root, cur) {
        if(!root)   return;
        cur = cur*10 + root.val;
        if(!root.left && !root.right) {
            sum += cur;
            return;
        }
        dfs(root.left, cur);
        dfs(root.right, cur);
    }
    dfs(root, 0);
    return sum;
};

3.二叉樹(shù)的最大深度
題目描述：給定一個(gè)二叉樹(shù)鹅髓，找出其最大深度舞竿。
二叉樹(shù)的深度為根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長(zhǎng)路徑上的節(jié)點(diǎn)數(shù)。
示例：
給定二叉樹(shù) [3,9,20,null,null,15,7]窿冯，
3
/ \
9 20
????/ \
??15 7
返回它的最大深度 3 骗奖。

思路：給定一個(gè)節(jié)點(diǎn)，假設(shè)它為葉子節(jié)點(diǎn)醒串，即沒(méi)有子節(jié)點(diǎn)执桌，則它的最大深度為1；而若它含有子節(jié)點(diǎn)芜赌，則其最大深度為子節(jié)點(diǎn)最大深度加1仰挣。

var maxDepth = function(root) {
    if(!root) return 0;
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
};

4.二叉樹(shù)中的最大路徑和
題目描述：給定一個(gè)非空二叉樹(shù)，返回其最大路徑和缠沈。
本題中膘壶，路徑被定義為一條從樹(shù)中任意節(jié)點(diǎn)出發(fā)错蝴，達(dá)到任意節(jié)點(diǎn)的序列。該路徑至少包含一個(gè)節(jié)點(diǎn)颓芭，且不一定經(jīng)過(guò)根節(jié)點(diǎn)顷锰。
示例：
輸入: [-10,9,20,null,null,15,7]
-10
??/ \
?9 20
???? / \
???15 7
輸出: 42

思路：給定一個(gè)節(jié)點(diǎn)，找到它的左側(cè)子節(jié)點(diǎn)最大貢獻(xiàn)值畜伐，右側(cè)子節(jié)點(diǎn)最大貢獻(xiàn)值馍惹；
由于可能是子節(jié)點(diǎn)獲取到最大和，因此需要比較當(dāng)前最大和與當(dāng)前節(jié)點(diǎn)值+左子節(jié)點(diǎn)最大貢獻(xiàn)值+右子節(jié)點(diǎn)最大貢獻(xiàn)值玛界，使最大和取兩者之間最大值万矾；
返回當(dāng)前節(jié)點(diǎn)值+max(左子節(jié)點(diǎn)最大貢獻(xiàn)值，右子節(jié)點(diǎn)最大貢獻(xiàn)值)慎框，即當(dāng)前節(jié)點(diǎn)為父節(jié)點(diǎn)貢獻(xiàn)的最大值(因?yàn)槁窂讲荒茏呷胱庸?jié)點(diǎn)再返回良狈，因此只能選取一側(cè)最大值)；
遍歷完成笨枯，返回最大和薪丁。

var maxPathSum = function(root) {
    let maxSum = Number.MIN_SAFE_INTEGER;
    function dfs(root) {
        if(!root)   return 0;
        let left = Math.max(0, dfs(root.left));
        let right = Math.max(0, dfs(root.right));
        maxSum = Math.max(maxSum, left+root.val+right);
        return root.val+Math.max(left, right);
    }
    dfs(root);
    return maxSum;
};

6.動(dòng)態(tài)規(guī)劃

1. 零錢兌換
題目描述：給定不同面額的硬幣 coins 和一個(gè)總金額 amount。編寫一個(gè)函數(shù)來(lái)計(jì)算可以湊成總金額所需的最少的硬幣個(gè)數(shù)馅精。如果沒(méi)有任何一種硬幣組合能組成總金額严嗜，返回 -1
示例：
輸入: coins = [1, 2, 5], amount = 11
輸出: 3
解釋: 11 = 5 + 5 + 1
輸入: coins = [2], amount = 3
輸出: -1

思路：假設(shè)總金額為S，需要的最少硬幣數(shù)為F(S)洲敢，則：
F(S) = min(F(S-ci)) + 1漫玄，其中i=1,2,...,n，n為coins數(shù)組長(zhǎng)度
也就是說(shuō)構(gòu)成總金額S最少需要的硬幣數(shù)等于構(gòu)成其依次減去所給硬幣金額后金額最小硬幣數(shù)加1压彭；
例如假設(shè)給定coins[5,10]睦优，給定金額10，則10依次減去5和10分別為5和0壮不，構(gòu)成0的硬幣數(shù)為0汗盘，加1為1，構(gòu)成5的最小硬幣數(shù)為1询一，加1為2隐孽，最終比較1和2，得到結(jié)果為1健蕊；
如上例所示菱阵，假設(shè)我們已知F(0)和F(5)，則取它們最小值加1即可得到結(jié)果绊诲；
因此針對(duì)F(S)送粱，假設(shè)我們已知F(0),F(1),...,F(S-1)，則我們將S減去所給硬幣面額掂之，然后由F(0),F(1),...,F(S-1)中找到它們對(duì)應(yīng)的值抗俄，再比較出最小值脆丁，加1即可求得F(S)；
因此我們可定義一個(gè)數(shù)組dp动雹，用來(lái)存儲(chǔ)0-S分別對(duì)應(yīng)的F(i)的值槽卫，然后用到哪個(gè)值直接取出即可；
dp初始化值除dp[0]外均為S+1(因?yàn)闃?gòu)成S的硬幣數(shù)最多為S個(gè)胰蝠，否則不能構(gòu)成)歼培，dp[0]=0是因?yàn)闃?gòu)成總額為0需要0個(gè)硬幣；
我們從0開(kāi)始茸塞，F(xiàn)(0)=0躲庄，然后利用循環(huán)來(lái)依次求取F(1)_{F(S)的值，例如到F(i)時(shí)钾虐，由于F(0)}F(i-1)的值我們都已知了噪窘，直接找到對(duì)應(yīng)值求取最小值加1即可；
最終判斷F(S)是否大于S效扫，大于則說(shuō)明給定硬幣無(wú)法構(gòu)成金額S倔监，返回-1，否則返回F(S)即dp[S]菌仁。

var coinChange = function(coins, amount) {
    let dp = new Array(amount+1).fill(amount+1);
    dp[0] = 0;
    for(let i=1; i<=amount; i++) {
        for(let j=0; j<coins.length; j++) {
            if(coins[j] <= i) {
                dp[i] = Math.min(dp[i], dp[i-coins[j]]+1);
            }
        }
    }
    return dp[amount]>amount ? -1 : dp[amount]
};