摘要：劍指在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。例如輸入前序遍歷序列和中序遍歷序列，則重建二叉樹(shù)并返回。其中負(fù)數(shù)用補(bǔ)碼表示。

本文為8月?？途W(wǎng)《劍指 offer》刷題做得，現(xiàn)整理出來(lái)作為參考。
雖然是算法題，但本文用 JavaScript 編寫(xiě)，看了《劍指 offer》以后發(fā)現(xiàn)很多問(wèn)題處理的過(guò)程并不是最好的，所以本文僅供參考。以前全部代碼 AC 通過(guò)，但即便是 AC 的代碼也不見(jiàn)得就是最好的，比如有的內(nèi)存分配了卻沒(méi)有釋放，這樣的問(wèn)題?？途W(wǎng)是查不出來(lái)的。

在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請(qǐng)完成一個(gè)函數(shù)，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組中是否含有該整數(shù)。

function Find(target, array){
    var rowCount = array.length - 1, i, j;

    for(i=rowCount,j=0; i >= 0 && j < array[i].length;){
        if(target == array[i][j]){
            return true;
        }else if(target > array[i][j]){
            j++;
            continue;
        }else if(target < array[i][j]){
            i--;
            continue;
        }
    }
    return false;
}

請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，將一個(gè)字符串中的空格替換成“%20”。例如，當(dāng)字符串為We Are Happy.則經(jīng)過(guò)替換之后的字符串為We%20Are%20Happy。

function replaceSpace(str){
    return str.replace(/ /g, "%20");
}

輸入一個(gè)鏈表，從尾到頭打印鏈表每個(gè)節(jié)點(diǎn)的值。

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function printListFromTailToHead(head){
    if(!head){
        return 0;
    } else {
        var arr = new Array();
        var curr = head;
        while(curr){
            arr.push(curr.val);
            curr = curr.next;
        }
        return arr.reverse();
    }
}

輸入某二叉樹(shù)的前序遍歷和中序遍歷的結(jié)果，請(qǐng)重建出該二叉樹(shù)。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹(shù)并返回。

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function reConstructBinaryTree(pre, vin){
    if(pre.length == 0 || vin.length == 0){
        return null;
    };
    var index = vin.indexOf(pre[0]);
    var left = vin.slice(0,index);
    var right = vin.slice(index+1);
    var node = new TreeNode(vin[index]);
    node.left = reConstructBinaryTree(pre.slice(1,index+1),left);
    node.right = reConstructBinaryTree(pre.slice(index+1),right);
    return node;
}

用兩個(gè)棧來(lái)實(shí)現(xiàn)一個(gè)隊(duì)列，完成隊(duì)列的Push和Pop操作。 隊(duì)列中的元素為int類型。

var stack1 = [];
var stack2 = [];

function push(node){
    stack1.push(node);
}

function pop(){
    var temp = stack1.pop();
    while(temp){
        stack2.push(temp);
        temp = stack1.pop();
    }
    var result = stack2.pop();
    temp = stack2.pop();
    while(temp){
        stack1.push(temp);
        temp = stack2.pop();
    }
    return result;
}

把一個(gè)數(shù)組最開(kāi)始的若干個(gè)元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)。 輸入一個(gè)非遞減排序的數(shù)組的一個(gè)旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。 例如數(shù)組{3,4,5,1,2}為{1,2,3,4,5}的一個(gè)旋轉(zhuǎn)，該數(shù)組的最小值為1。 NOTE：給出的所有元素都大于0，若數(shù)組大小為0，請(qǐng)返回0。

function minNumberInRotateArray(rotateArray){
    var len = rotateArray.length;
    if(len === 0){
        return 0;
    }
    return Math.min.apply(null,rotateArray);
}

大家都知道斐波那契數(shù)列，現(xiàn)在要求輸入一個(gè)整數(shù)n，請(qǐng)你輸出斐波那契數(shù)列的第n項(xiàng)。n<=39

function Fibonacci(n){
    var a = 1, b = 1, temp;
    if(n <= 0) return 0;
    for(var i = 2; i <= n; i++){
      temp = b;
      b = a + b;
      a = temp;
    }
    return a;
}

一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法。

function jumpFloor(number){
    if(number < 1){
        return 0;
    }
    if(number === 1){
        return 1;
    }
    if(number === 2){
        return 2;
    }
    var temp = 0, a = 1, b = 2;
    for(var i = 3; i <= number; i++){
        temp = a + b;
        a = b;
        b = temp;
    }
    return temp;
}

一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)……它也可以跳上n級(jí)。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法。

function jumpFloorII(number){
  return Math.pow(2, number - 1);
}

我們可以用21的小矩形橫著或者豎著去覆蓋更大的矩形。請(qǐng)問(wèn)用n個(gè)21的小矩形無(wú)重疊地覆蓋一個(gè)2*n的大矩形，總共有多少種方法？

function rectCover(number){
    var a = 1, b = 2, temp;
    if(number <= 0){
        return 0;
    }
    if(number === 1){
        return 1;
    }
    if(number === 2){
        return 2
    }
    for(var i = 3; i <= number; i++){
      temp = a + b;
      a = b;
      b = temp;
    }
    return temp;
}

輸入一個(gè)整數(shù)，輸出該數(shù)二進(jìn)制表示中1的個(gè)數(shù)。其中負(fù)數(shù)用補(bǔ)碼表示。

function NumberOf1(n){
    if(n < 0){
        n = n >>> 0;
    }
    var arr = n.toString(2).split("");
    return arr.reduce(function(a,b){
        return b === "1" ? a + 1 : a;
    },0);
}

給定一個(gè)double類型的浮點(diǎn)數(shù)base和int類型的整數(shù)exponent。求base的exponent次方。

function Power(base, exponent){
    return Math.pow(base, exponent);
}

輸入一個(gè)整數(shù)數(shù)組，實(shí)現(xiàn)一個(gè)函數(shù)來(lái)調(diào)整該數(shù)組中數(shù)字的順序，使得所有的奇數(shù)位于數(shù)組的前半部分，所有的偶數(shù)位于位于數(shù)組的后半部分，并保證奇數(shù)和奇數(shù)，偶數(shù)和偶數(shù)之間的相對(duì)位置不變。

function reOrderArray(array){
    var result = [];
    var even = [];
    array.forEach(function(item){
        if((item & 1) === 1){
            result.push(item);
        } else {
            even.push(item);
        }
    });
    return result.concat(even);
}

輸入一個(gè)鏈表，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)。

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function FindKthToTail(head, k){
    if(!head || k <= 0){
        return null;
    }
    var i = head, j = head;
    while(--k){
        j = j.next;
        if(!j){
            return null;
        }
    }
    while(j.next){
        i = i.next;
        j = j.next;
    }
    j = null;
    return i;
}

輸入一個(gè)鏈表，反轉(zhuǎn)鏈表后，輸出鏈表的所有元素。

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function ReverseList(pHead){
    var newHead, temp;
    if(!pHead){
        return null;
    }
    if(pHead.next === null){
        return pHead;
    } else {
        newHead = ReverseList(pHead.next);
    }
    temp = pHead.next;
    temp.next = pHead;
    pHead.next = null;
    temp = null;
    return newHead;
}

輸入兩個(gè)單調(diào)遞增的鏈表，輸出兩個(gè)鏈表合成后的鏈表，當(dāng)然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則。

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function Merge(pHead1, pHead2){
    if(!pHead1){
        return pHead2 ? pHead2 : null
    } else if(!pHead2){
        return pHead1;
    }
    // debugger;
    var curr1 = pHead1;
    var curr2 = pHead2;
    var result = new ListNode(-1);
    var curr = result;
    while(curr1 && curr2){
        if(curr1.val < curr2.val){
            curr.next = curr1;
            curr1 = curr1.next;
        } else{
            curr.next = curr2;
            curr2 = curr2.next;
        }
        curr = curr.next;
    }
    if(curr1){
        curr.next = curr1;
    }
    if(curr2){
        curr.next = curr2;
    }

    //防止內(nèi)存泄露
    curr = result.next;
    result.next = null;
    result = curr;
    curr = curr1 = curr2 = null;

    return result;
}

輸入兩棵二叉樹(shù)A，B，判斷B是不是A的子結(jié)構(gòu)。（ps：我們約定空樹(shù)不是任意一個(gè)樹(shù)的子結(jié)構(gòu)）

function HasSubtree(pRoot1, pRoot2){
    if(pRoot1 == null || pRoot2 == null){
        return false;
    }
    if(isSubTree(pRoot1, pRoot2)){
        return true;
    } else{
        return HasSubtree(pRoot1.left, pRoot2) || HasSubtree(pRoot1.right, pRoot2);
    }

    function isSubTree(pRoot1, pRoot2){
        if(pRoot2 == null) return true;
        if(pRoot1 == null) return false;
        if(pRoot1.val === pRoot2.val){
            return isSubTree(pRoot1.left, pRoot2.left) && isSubTree(pRoot1.right, pRoot2.right);
        } else {
            return false;
        }

    }
}

操作給定的二叉樹(shù)，將其變換為源二叉樹(shù)的鏡像。

function Mirror(root){
    if(!root){
        return null;
    }
    var temp = root.left;
    root.left = root.right;
    root.right = temp;
    if(root.left){
        Mirror(root.left);
    }
    if(root.right){
        Mirror(root.right);
    }
}

輸入一個(gè)矩陣，按照從外向里以順時(shí)針的順序依次打印出每一個(gè)數(shù)字，例如，如果輸入如下矩陣： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 則依次打印出數(shù)字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

function printMatrix(matrix){
    if(!matrix || !matrix.length) return null;
    var result = [];
    var rows = matrix.length, cols = matrix[0].length;
    var len = rows * cols;
    var i = 0, j = 0;
    var circle = 0;
    while(1){
        while(j < cols - circle){
            result.push(matrix[i][j]);
            j++;
        }
        if(result.length === len) break;
        j--, i++;
        while(i < rows - circle){
            result.push(matrix[i][j])
            i++;
        }
        if(result.length === len) break;
        i--, j--;
        while(j >= circle){
            result.push(matrix[i][j]);
            j--;
        }
        if(result.length === len) break;
        j++, i--;
        circle++;
        while(i >= circle){
            result.push(matrix[i][j])
            i--;
        }
        if(result.length === len) break;
        j++, i++;
    }
    return result;
}

定義棧的數(shù)據(jù)結(jié)構(gòu)，請(qǐng)?jiān)谠擃愋椭袑?shí)現(xiàn)一個(gè)能夠得到棧最小元素的min函數(shù)。

var stack = [];
function push(node){
    stack.push(node);
}
function pop(){
    return stack.pop();
}
function top(){
    return stack[stack.length - 1];
}
function min(){
    return Math.min.apply(null, stack);
}

輸入兩個(gè)整數(shù)序列，第一個(gè)序列表示棧的壓入順序，請(qǐng)判斷第二個(gè)序列是否為該棧的彈出順序。假設(shè)壓入棧的所有數(shù)字均不相等。例如序列1,2,3,4,5是某棧的壓入順序，序列4，5,3,2,1是該壓棧序列對(duì)應(yīng)的一個(gè)彈出序列，但4,3,5,1,2就不可能是該壓棧序列的彈出序列。（注意：這兩個(gè)序列的長(zhǎng)度是相等的）

function IsPopOrder(pushV, popV){
    if(!pushV.length || !popV.length){
        return false;
    }
    var temp = [];
    var popIndex = 0;
    var len = pushV.length;
    for(var i = 0; i < len; i++){
        temp.push(pushV[i]);
        while(temp.length && temp[temp.length - 1] === popV[popIndex]){
            temp.pop();
            popIndex++;
        }
    }
    return temp.length === 0;
}

從上往下打印出二叉樹(shù)的每個(gè)節(jié)點(diǎn)，同層節(jié)點(diǎn)從左至右打印。

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function PrintFromTopToBottom(root){
    if (!root) {
        return [];
    }
    var queue = [];
    queue.push(root);
    var result = [];

    while (queue.length) {
        var temp = queue.shift();
        result.push(temp.val);
        if (temp.left) {
            queue.push(temp.left);
        }
        if (temp.right) {
            queue.push(temp.right);
        }
    }
    return result;
}

輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹(shù)的后序遍歷的結(jié)果。如果是則輸出Yes,否則輸出No。假設(shè)輸入的數(shù)組的任意兩個(gè)數(shù)字都互不相同。(測(cè)試用例用的是 false/true, 不是題目中的 "Yes"/"No")

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function VerifySquenceOfBST(sequence) {
    var len = sequence.length
    if (!len) {
        return false;
    }
    return adjustSequence(0, len - 1);

    function adjustSequence(start, end){
        if (start >= end) {
            return true;
        }
        var root = sequence[end];
        for(var i = start; i < end && sequence[i] < root; i++);
        var index = i;
        for (i = i + 1; i < end; i++) {
            if (sequence[i] < root) {
                return false;
            }
        }
        return adjustSequence(start, index - 1) && (adjustSequence(index, end - 1));
    }
}

輸入一顆二叉樹(shù)和一個(gè)整數(shù)，打印出二叉樹(shù)中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑。路徑定義為從樹(shù)的根結(jié)點(diǎn)開(kāi)始往下一直到葉結(jié)點(diǎn)所經(jīng)過(guò)的結(jié)點(diǎn)形成一條路徑。

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function FindPath(root, expectNumber){
    var temp = [];
    // var found = false;
    var result = [];
    dfs(root, 0);
    return result;
    function dfs(root, sum){
      // debugger;s
        if(!root){
            return;
        }
        temp.push(root.val);
        sum += root.val;
        if(!root.left && !root.right && sum === expectNumber){
            result.push(temp.concat());
        }
        if(root.left){
            dfs(root.left, sum);
        }
        if(root.right){
            dfs(root.right, sum);
        }
        temp.pop();
        return;
    }
}

輸入一個(gè)復(fù)雜鏈表（每個(gè)節(jié)點(diǎn)中有節(jié)點(diǎn)值，以及兩個(gè)指針，一個(gè)指向下一個(gè)節(jié)點(diǎn)，另一個(gè)特殊指針指向任意一個(gè)節(jié)點(diǎn)），返回結(jié)果為復(fù)制后復(fù)雜鏈表的head。（注意，輸出結(jié)果中請(qǐng)不要返回參數(shù)中的節(jié)點(diǎn)引用，否則判題程序會(huì)直接返回空）

function Clone(pHead)
{
    if(!pHead){
        return null;
    }
    var head = new RandomListNode(pHead.label);
    head.random = pHead.random;
    head.next = Clone(pHead.next);
    return head;
}

輸入一棵二叉搜索樹(shù)，將該二叉搜索樹(shù)轉(zhuǎn)換成一個(gè)排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只能調(diào)整樹(shù)中結(jié)點(diǎn)指針的指向。

將左子樹(shù)構(gòu)成雙向鏈表，返回的是左子樹(shù)的尾結(jié)點(diǎn)，將其連接到root的左邊；
將右子樹(shù)構(gòu)成雙向鏈表，將其追加到root結(jié)點(diǎn)之后，并返回尾結(jié)點(diǎn)；
向左遍歷返回的鏈表至頭結(jié)點(diǎn)處，即為所求雙向鏈表的首結(jié)點(diǎn)。

function Convert(pRootOfTree){
    if(!pRootOfTree) {
        return null;
    }
    var lastNode = null;
    lastNode = ConvertNode(pRootOfTree);
    var head = lastNode;
    while(head && head.left) {
        head = head.left;
    }
    return head;

    function ConvertNode(node){
        if(!node){
            return;
        }
        if(node.left) {
            lastNode = ConvertNode(node.left);
        }
        node.left = lastNode;
        if(lastNode){
            lastNode.right = node;
        }
        lastNode = node;
        if(node.right){
            lastNode = ConvertNode(node.right);
        }
        return lastNode;
    }
}

輸入一個(gè)字符串,按字典序打印出該字符串中字符的所有排列。例如輸入字符串a(chǎn)bc,則打印出由字符a,b,c所能排列出來(lái)的所有字符串a(chǎn)bc,acb,bac,bca,cab和cba。

function Permutation(str){
    if(!str || str.length === 0){
        return [];
    }
    var result = [];
    var arr = str.split("");
    var temp = "";
    ordering(arr);
    result = result.filter(function(item, index){  //去重
      return result.indexOf(item) === index;
    });
    return result;

    function ordering(tempArr){
        if(tempArr.length === 0){
            result.push(temp);
            return;
        }
        for(var i = 0; i < tempArr.length; i++){
            temp += tempArr[i];
            insideArr = tempArr.concat();
            insideArr.splice(i,1);
            ordering(insideArr);
            temp = temp.substring(0, temp.length - 1);   //回溯
        }
    }
}

數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過(guò)數(shù)組長(zhǎng)度的一半，請(qǐng)找出這個(gè)數(shù)字。例如輸入一個(gè)長(zhǎng)度為9的數(shù)組{1,2,3,2,2,2,5,4,2}。由于數(shù)字2在數(shù)組中出現(xiàn)了5次，超過(guò)數(shù)組長(zhǎng)度的一半，因此輸出2。如果不存在則輸出0。

function MoreThanHalfNum_Solution(numbers){
    if(!numbers || numbers.length === 0){
        return 0;
    }
    var arr = [];
    var len = numbers.length, index;
    for(var i = 0; i < len; i++){
      var index = numbers[i];
      arr[index] !== undefined ? arr[index]++ : arr[index] = 1;
    }
    var index = -1;
    var arrLen = arr.length;
    var max = -Infinity;
    for(var i = 0; i < arrLen; i++){
      if(!arr[i]) continue;
      max = arr[i] > max ? (index = i, arr[i]) : max;
    }
    return max > len / 2 ? index : 0;
}

輸入n個(gè)整數(shù)，找出其中最小的K個(gè)數(shù)。例如輸入4,5,1,6,2,7,3,8這8個(gè)數(shù)字，則最小的4個(gè)數(shù)字是1,2,3,4。

function GetLeastNumbers_Solution(input, k){
    if(!input || input.length < k){
        return [];
    }
    return input.sort(function(a,b){
        return a - b
    }).slice(0, k);
}

HZ偶爾會(huì)拿些專業(yè)問(wèn)題來(lái)忽悠那些非計(jì)算機(jī)專業(yè)的同學(xué)。今天測(cè)試組開(kāi)完會(huì)后,他又發(fā)話了:在古老的一維模式識(shí)別中,常常需要計(jì)算連續(xù)子向量的最大和,當(dāng)向量全為正數(shù)的時(shí)候,問(wèn)題很好解決。但是,如果向量中包含負(fù)數(shù),是否應(yīng)該包含某個(gè)負(fù)數(shù),并期望旁邊的正數(shù)會(huì)彌補(bǔ)它呢？例如:{6,-3,-2,7,-15,1,2,2},連續(xù)子向量的最大和為8(從第0個(gè)開(kāi)始,到第3個(gè)為止)。你會(huì)不會(huì)被他忽悠住？(子向量的長(zhǎng)度至少是1)

function FindGreatestSumOfSubArray(array){
    if (array.length < 0)
        return 0;
    var sum = array[0],
        tempsum = array[0];
    for (var i = 1; i < array.length; i++) {
        tempsum = tempsum < 0 ? array[i] : tempsum + array[i];
        sum = tempsum > sum ? tempsum : sum;
    }
    return sum;
}

求出1~13的整數(shù)中1出現(xiàn)的次數(shù),并算出100~1300的整數(shù)中1出現(xiàn)的次數(shù)？為此他特別數(shù)了一下1~13中包含1的數(shù)字有1、10、11、12、13因此共出現(xiàn)6次,但是對(duì)于后面問(wèn)題他就沒(méi)轍了。ACMer希望你們幫幫他,并把問(wèn)題更加普遍化,可以很快的求出任意非負(fù)整數(shù)區(qū)間中1出現(xiàn)的次數(shù)。

function NumberOf1Between1AndN_Solution(n)
{
    if (n < 0) return 0;
    var ones = 0;
    var arr = [];
    while(n){
        arr.push(n);
        n--;
    }
    return arr.join("").replace(/[^1]+/g,"").length;
}

輸入一個(gè)正整數(shù)數(shù)組，把數(shù)組里所有數(shù)字拼接起來(lái)排成一個(gè)數(shù)，打印能拼接出的所有數(shù)字中最小的一個(gè)。例如輸入數(shù)組{3，32，321}，則打印出這三個(gè)數(shù)字能排成的最小數(shù)字為321323。

function PrintMinNumber(numbers)
{
    if(!numbers || numbers.length === 0){
        return [];
    }
    var result = [];
    var temp = "";
    ordering(numbers);

    result = result.map(Number).reduce(function(min , a){  //最小值
      return min < a ? min : a;
    }, Infinity);
    return result;

    function ordering(tempArr){
        var innerLen = 0;
        if(tempArr.length === 0){
            result.push(temp);
            return;
        }
        for(var i = 0; i < tempArr.length; i++){
            innerLen = tempArr[i].toString().length;
            temp += tempArr[i];
            insideArr = tempArr.concat();
            insideArr.splice(i,1);
            ordering(insideArr);
            temp = temp.substring(0, temp.length - innerLen);   //回溯
        }
    }
}

把只包含因子2、3和5的數(shù)稱作丑數(shù)（Ugly Number）。例如6、8都是丑數(shù)，但14不是，因?yàn)樗蜃?。 習(xí)慣上我們把1當(dāng)做是第一個(gè)丑數(shù)。求按從小到大的順序的第N個(gè)丑數(shù)。

function GetUglyNumber_Solution(index) {
    if (index === 0) return 0;
    var uglyNum = [1];
    var factor2 = 0, factor3 = 0, factor5 = 0;
    for (var i = 1; i < index; i++) {
        uglyNum[i] = Math.min(uglyNum[factor2] * 2, uglyNum[factor3] * 3, uglyNum[factor5] * 5);
        if (uglyNum[i] === uglyNum[factor2] * 2) factor2++;
        if (uglyNum[i] === uglyNum[factor3] * 3) factor3++;
        if (uglyNum[i] === uglyNum[factor5] * 5) factor5++;
    }
    return uglyNum[index - 1];
}

在一個(gè)字符串(1<=字符串長(zhǎng)度<=10000，全部由字母組成)中找到第一個(gè)只出現(xiàn)一次的字符,并返回它的位置

function FirstNotRepeatingChar(str){
    if(!str || !str.length){
        return -1;
    }

    var hash = {};
    var tempArr = str.split("");
    var unique = [];
    var len = str.length, temp;
    for(var i = 0; i < len; i++){
        temp = tempArr[i];
        if(hash[temp]){
            hash[temp].push(i);
        } else {
            hash[temp] = [i];
        }
    }
    for(var key in hash){
        if(hash.hasOwnProperty(key)){
            if(hash[key].length === 1){
                unique.push(hash[key].pop());
            }
        }
    }

    return Math.min.apply(null, unique);

}

在數(shù)組中的兩個(gè)數(shù)字，如果前面一個(gè)數(shù)字大于后面的數(shù)字，則這兩個(gè)數(shù)字組成一個(gè)逆序?qū)?。輸入一個(gè)數(shù)組,求出這個(gè)數(shù)組中的逆序?qū)Φ目倲?shù)P。并將P對(duì)1000000007取模的結(jié)果輸出。 即輸出P%1000000007

由于時(shí)間空間復(fù)雜度的限制，js 貌似無(wú)法完成這個(gè)題，所以使用 c++ 完成。

class Solution {
public:
    long long InversePairsCore(vector &data, vector©, int start, int end){
        if(start == end){
            copy[start] = data[start];
            return 0;
        }
        int length = (end - start) / 2;
        long long left = InversePairsCore(copy, data, start, start + length);
        long long right = InversePairsCore(copy, data, start + length + 1, end);

        int i = start + length;
        int j = end;
        int indexCopy = end;
        long long count=0;
        while(i >= start && j >= start + length + 1){
            if(data[i] > data[j]){
                copy[indexCopy--] = data[i--];
                count += j - start - length;
            } else {
                copy[indexCopy--] = data[j--];
            }
        }
        for(; i >= start; --i)
            copy[indexCopy--] = data[i];
        for(;j >= start + length + 1; --j)
            copy[indexCopy--] = data[j];
        return left + right + count;
    }
    int InversePairs(vector data) {
        int length = data.size();
        if(length <= 0)
            return 0;
        vector copy;
        for(int i = 0; i < length; i++)
            copy.push_back(data[i]);
        long long count = InversePairsCore(data, copy, 0, length-1);
        copy.clear();
        return count % 1000000007;
    }
};

輸入兩個(gè)鏈表，找出它們的第一個(gè)公共結(jié)點(diǎn)。

function FindFirstCommonNode(pHead1, pHead2){
    if(!pHead1 || !pHead2){
        return null;
    }
    var len1 = getLength(pHead1);
    var len2 = getLength(pHead2);
    var lenDiff = len1 - len2;

    var curr1 = pHead1;
    var curr2 = pHead2;
    if(len2 > len1){
        curr1 = pHead2;
        curr2 = pHead1;
        lenDiff = len2 - len1;
    }

    for(var i = 0; i < lenDiff; ++i)
        curr1 = curr1.next;

    while(curr1 && curr2 && curr1 != curr2){
        curr1 = curr1.next;
        curr2 = curr2.next;
    }

    return curr1;

    function getLength(node){
        var len = 0;
        curr = node;
        while(curr){
            len++;
            curr = curr.next;
        }
        return len;
    }
}

統(tǒng)計(jì)一個(gè)數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)。

function GetNumberOfK(data, k){
    return data.reduce(function(count, a){
        return a === k ? count+1 :count;
    }, 0);
}

輸入一棵二叉樹(shù)，求該樹(shù)的深度。從根結(jié)點(diǎn)到葉結(jié)點(diǎn)依次經(jīng)過(guò)的結(jié)點(diǎn)（含根、葉結(jié)點(diǎn)）形成樹(shù)的一條路徑，最長(zhǎng)路徑的長(zhǎng)度為樹(shù)的深度。

function TreeDepth(pRoot){
    if(!pRoot){
        return 0;
    }

    var depth = 0;
    var currDepth = 0;
    dfs(pRoot);
    return depth;

    function dfs(node){
        if(!node){
            depth = depth > currDepth ? depth : currDepth;
            return;
        }
        currDepth++;
        dfs(node.left);
        dfs(node.right);
        currDepth--;
    }
}

輸入一棵二叉樹(shù)，判斷該二叉樹(shù)是否是平衡二叉樹(shù)。

function IsBalanced_Solution(pRoot){
    if(!pRoot){
        return true;
    }

    var left = TreeDepth(pRoot.left);
    var right = TreeDepth(pRoot.right);
    var diff = left - right;

    if(diff > 1 || diff < -1)
        return false;

    return IsBalanced_Solution(pRoot.left) && IsBalanced_Solution(pRoot.right);

    function TreeDepth(pRoot){
        if(!pRoot){
            return 0;
        }

        var depth = 0;
        var currDepth = 0;
        dfs(pRoot);
        return depth;

        function dfs(node){
            if(!node){
                depth = depth > currDepth ? depth : currDepth;
                return;
            }
            currDepth++;
            dfs(node.left);
            dfs(node.right);
            currDepth--;
        }
    }
}

一個(gè)整型數(shù)組里除了兩個(gè)數(shù)字之外，其他的數(shù)字都出現(xiàn)了兩次。請(qǐng)寫(xiě)程序找出這兩個(gè)只出現(xiàn)一次的數(shù)字。

function FindNumsAppearOnce(array){
    if (!array || array.length < 2)
        return [];
    return array.sort().join(",").replace(/(d+),1/g,"").replace(/,+/g,",").replace(/^,|,$/, "").split(",").map(Number);
}

小明很喜歡數(shù)學(xué),有一天他在做數(shù)學(xué)作業(yè)時(shí),要求計(jì)算出9~16的和,他馬上就寫(xiě)出了正確答案是100。但是他并不滿足于此,他在想究竟有多少種連續(xù)的正數(shù)序列的和為100(至少包括兩個(gè)數(shù))。沒(méi)多久,他就得到另一組連續(xù)正數(shù)和為100的序列:18,19,20,21,22。現(xiàn)在把問(wèn)題交給你,你能不能也很快的找出所有和為S的連續(xù)正數(shù)序列? Good Luck!

function FindContinuousSequence(sum){
    if(sum < 3){
        return [];
    }
    var small = 1, big = 2;
    var mid = (1 + sum) / 2;
    var curr = small + big;
    var result = [];

    while(small < mid){
        if(curr === sum){
            pushSeq(small, big);
        }
        while(curr > sum && small < mid){
            curr -= small;
            small++;
            if(curr === sum){
                pushSeq(small, big);
            }
        }
        big++;
        curr += big;
    }

    result.sort(function(a,b){return a[0] - b[0];});
    return result;

    function pushSeq(small, big){
        var temp = [];
        for(var i = small; i <= big; i++){
            temp.push(i);
        }
        result.push(temp);
    }
}

輸入一個(gè)遞增排序的數(shù)組和一個(gè)數(shù)字S，在數(shù)組中查找兩個(gè)數(shù)，是的他們的和正好是S，如果有多對(duì)數(shù)字的和等于S，輸出兩個(gè)數(shù)的乘積最小的。

function FindNumbersWithSum(array, sum){
    if(!array || !array.length){
        return [];
    }
    var result = [];
    var product = [];
    var head = 0, tail = array.length - 1;
    while(head < tail){
        var curr = array[head] + array[tail];
        if(curr === sum){
            result.push([array[head], array[tail]]);
            product.push(array[head] * array[tail]);
            tail--;
            head++;
        } else if(curr > sum){
            tail--;
        } else {
            head++;
        }
    }
    if(result.length === 0){
        return [];
    }
    var min = Math.min.apply(null, product);
    var index = product.indexOf(min);
    return result[index];
}

匯編語(yǔ)言中有一種移位指令叫做循環(huán)左移（ROL），現(xiàn)在有個(gè)簡(jiǎn)單的任務(wù)，就是用字符串模擬這個(gè)指令的運(yùn)算結(jié)果。對(duì)于一個(gè)給定的字符序列S，請(qǐng)你把其循環(huán)左移K位后的序列輸出。例如，字符序列S=”abcXYZdef”,要求輸出循環(huán)左移3位后的結(jié)果，即“XYZdefabc”。是不是很簡(jiǎn)單？OK，搞定它！

function LeftRotateString(str, n){
    if(!str){
        return "";
    }
    var len = str.length;
    n = n % len;
    var left = str.slice(0,n);
    var right = str.slice(n);
    return right + left;
}

?？妥罱鼇?lái)了一個(gè)新員工Fish，每天早晨總是會(huì)拿著一本英文雜志，寫(xiě)些句子在本子上。同事Cat對(duì)Fish寫(xiě)的內(nèi)容頗感興趣，有一天他向Fish借來(lái)翻看，但卻讀不懂它的意思。例如，“student. a am I”。后來(lái)才意識(shí)到，這家伙原來(lái)把句子單詞的順序翻轉(zhuǎn)了，正確的句子應(yīng)該是“I am a student.”。Cat對(duì)一一的翻轉(zhuǎn)這些單詞順序可不在行，你能幫助他么？

function ReverseSentence(str){
    return str.split(" ").reverse().join(" ");
}

LL今天心情特別好,因?yàn)樗ベI(mǎi)了一副撲克牌,發(fā)現(xiàn)里面居然有2個(gè)大王,2個(gè)小王(一副牌原本是54張^_^)...他隨機(jī)從中抽出了5張牌,想測(cè)測(cè)自己的手氣,看看能不能抽到順子,如果抽到的話,他決定去買(mǎi)體育彩票,嘿嘿！！“紅心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是順子.....LL不高興了,他想了想,決定大小 王可以看成任何數(shù)字,并且A看作1,J為11,Q為12,K為13。上面的5張牌就可以變成“1,2,3,4,5”(大小王分別看作2和4),“So Lucky!”。LL決定去買(mǎi)體育彩票啦。 現(xiàn)在,要求你使用這幅牌模擬上面的過(guò)程,然后告訴我們LL的運(yùn)氣如何。為了方便起見(jiàn),你可以認(rèn)為大小王是0。

function IsContinuous(numbers){
    if(!numbers || numbers.length < 1){
        return false;
    }
    var len = numbers.length;
    numbers.sort(function(a,b){return a - b;});

    var zeros = 0, gaps = 0;
    for(var i = 0; i < len && numbers[i] == 0; i++){
        zeros++;
    }
    var small = zeros, big = small + 1;
    while(big < len){
        if(numbers[small] == numbers[big]){
            return false;
        }
        gaps += numbers[big] - numbers[small] - 1;
        small = big++;
    }
    return gaps <= zeros;
}

每年六一兒童節(jié),?？投紩?huì)準(zhǔn)備一些小禮物去看望孤兒院的小朋友,今年亦是如此。HF作為牛客的資深元老,自然也準(zhǔn)備了一些小游戲。其中,有個(gè)游戲是這樣的:首先,讓小朋友們圍成一個(gè)大圈。然后,他隨機(jī)指定一個(gè)數(shù)m,讓編號(hào)為0的小朋友開(kāi)始報(bào)數(shù)。每次喊到m-1的那個(gè)小朋友要出列唱首歌,然后可以在禮品箱中任意的挑選禮物,并且不再回到圈中,從他的下一個(gè)小朋友開(kāi)始,繼續(xù)0...m-1報(bào)數(shù)....這樣下去....直到剩下最后一個(gè)小朋友,可以不用表演,并且拿到?？兔F的“名偵探柯南”典藏版(名額有限哦!!^_^)。請(qǐng)你試著想下,哪個(gè)小朋友會(huì)得到這份禮品呢？(注：小朋友的編號(hào)是從0到n-1)

function LastRemaining_Solution(n, m){
    if(n < 1 || m < 1){
        return -1;
    }
    var last = 0;
    for(var i = 2; i <= n; i++){
        last = (last + m) % i;
    }
    return last;
}

求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等關(guān)鍵字及條件判斷語(yǔ)句（A?B:C）。

function Sum_Solution(n){
  var sum = 0;
  plus(n);
  return sum;

  function plus(num){
    sum += num;
    num > 0 && plus(--num);
  }
}

寫(xiě)一個(gè)函數(shù)，求兩個(gè)整數(shù)之和，要求在函數(shù)體內(nèi)不得使用+、-、*、/四則運(yùn)算符號(hào)。

function Add(num1, num2){
    var sum, carry;
    do{
        sum = num1 ^ num2;
        carry = (num1 & num2) << 1;
        num1 = sum;
        num2 = carry;
    }while(num2 != 0);
    return num1;
}

將一個(gè)字符串轉(zhuǎn)換成一個(gè)整數(shù)，要求不能使用字符串轉(zhuǎn)換整數(shù)的庫(kù)函數(shù)。 數(shù)值為0或者字符串不是一個(gè)合法的數(shù)值則返回0

function StrToInt(str){
    if(str.length === 0){
        return 0;
    }
    var format = str.match(/^(+?|-?)(d+)$/);
    if(!format){
        return 0;
    }
    var num = 0;
    var temp = format[2];
    var base = 1;
    var flag = format[1];
    for(var i = temp.length - 1; i >= 0; i--){
        num += parseInt(temp[i]) * base;
        base *= 10;
    }

    return flag === "-" ? num * (-1) : num;
}

在一個(gè)長(zhǎng)度為n的數(shù)組里的所有數(shù)字都在0到n-1的范圍內(nèi)。 數(shù)組中某些數(shù)字是重復(fù)的，但不知道有幾個(gè)數(shù)字是重復(fù)的。也不知道每個(gè)數(shù)字重復(fù)幾次。請(qǐng)找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字。 例如，如果輸入長(zhǎng)度為7的數(shù)組{2,3,1,0,2,5,3}，那么對(duì)應(yīng)的輸出是第一個(gè)重復(fù)的數(shù)字2。

function duplicate(numbers, duplication){
    if(!numbers || !numbers.length){
        return false;
    }
    var len = numbers.length;
    for(var i = 0; i < len; i++){
        var curr = numbers[i];
        if(numbers.indexOf(curr) !== i){
            duplication[0] = curr;
            return true;
        }
    }
    return false;
}

給定一個(gè)數(shù)組A[0,1,...,n-1],請(qǐng)構(gòu)建一個(gè)數(shù)組B[0,1,...,n-1],其中B中的元素B[i]=A[0]A[1]...A[i-1]A[i+1]...A[n-1]。不能使用除法。

function multiply(array){
    if(!array || !array.length){
        return [];
    }
    var result = [];
    var len1 = array.length, len2 = result.length;
    result[0] = 1;
    for(var i = 1; i < len1; i++){
        result[i] = array[i - 1] * result[i - 1];
    }
    var temp = 1;
    for(var i = len1 - 2; i >= 0;--i){
        temp *=array[i + 1];
        result[i] *= temp
    }
    return result;
}

請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)用來(lái)匹配包括"."和""的正則表達(dá)式。模式中的字符"."表示任意一個(gè)字符，而""表示它前面的字符可以出現(xiàn)任意次（包含0次）。 在本題中，匹配是指字符串的所有字符匹配整個(gè)模式。例如，字符串"aaa"與模式"a.a"和"abaca"匹配，但是與"aa.a"和"ab*a"均不匹配

function match(s, pattern)
{
    if(s === "" && pattern === ""){
        return true;
    }
    if(!pattern || pattern.length === 0){
        return false
    }
    var reg = new RegExp("^" + pattern + "$");
    return reg.test(s);
}

請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)用來(lái)判斷字符串是否表示數(shù)值（包括整數(shù)和小數(shù)）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示數(shù)值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。

function isNumeric(s){
    var reg = /^[+-]?(?:(d+)(.d+)?|(.d+))([eE][+-]?d+)?$/;
    return reg.test(s);
}

請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)用來(lái)找出字符流中第一個(gè)只出現(xiàn)一次的字符。例如，當(dāng)從字符流中只讀出前兩個(gè)字符"go"時(shí)，第一個(gè)只出現(xiàn)一次的字符是"g"。當(dāng)從該字符流中讀出前六個(gè)字符“google"時(shí)，第一個(gè)只出現(xiàn)一次的字符是"l"。

function Init(){
    streamNums = [];   //定義一個(gè)全局變量, 不用var
    streamNumsLen = 256;   //定義一個(gè)全局變量, 不用var
    streamNumsIndex = 0;   //定義一個(gè)全局變量, 不用var

    for(var i = 0; i < streamNumsLen; i++){
        streamNums[i] = -1;
    }
}

function Insert(ch){
    var code = ch.charCodeAt();
    if(streamNums[code] == -1){
        streamNums[code] = streamNumsIndex;
    } else if(streamNums[code] >= 0){
        streamNums[code] = -2;
    }
    streamNumsIndex++;
}

function FirstAppearingOnce(){
    result = "";
    var ch = "";
    var minIndex = Infinity;
    for(var i = 0; i < streamNumsLen; i++){
        if(streamNums[i] >= 0 && streamNums[i] < minIndex){
            ch = String.fromCharCode(i);
            minIndex = streamNums[i];
        }
    }
    return ch == "" ? "#" : ch;
}

一個(gè)鏈表中包含環(huán)，請(qǐng)找出該鏈表的環(huán)的入口結(jié)點(diǎn)。

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function EntryNodeOfLoop(pHead){
    if(!pHead){
        return null;
    }
    var meeting = meetingNode(pHead);
    if(!meeting){
        return null;
    }
    var nodeLoop = 1;
    var node1 = meeting;
    while(node1.next != meeting){
        node1 = node1.next;
        nodeLoop++;
    }
    node1 = pHead;
    for(var i = 0; i < nodeLoop; i++){
        node1 = node1.next;
    }
    var node2 = pHead;
    while(node1 != node2){
        node1 = node1.next;
        node2 = node2.next;
    }
    return node1;

    function meetingNode(node){
        if(!node || !node.next){
            return null;
        }
        var slow = node.next;
        var fast = slow.next;

        while(fast && slow){
            if(fast === slow){
                return fast;
            }
            slow = slow.next;
            fast = fast.next;
            if(fast){
                fast = fast.next;
            }
        }
        return null;
    }
}

在一個(gè)排序的鏈表中，存在重復(fù)的結(jié)點(diǎn)，請(qǐng)刪除該鏈表中重復(fù)的結(jié)點(diǎn)，重復(fù)的結(jié)點(diǎn)不保留，返回鏈表頭指針。 例如，鏈表1->2->3->3->4->4->5 處理后為 1->2->5

function deleteDuplication(pHead){
    if(!pHead){
        return null;
    }
    var tempHead = new ListNode(-1);
    tempHead.next = pHead;
    var preNode = tempHead;
    var curr1 = preNode.next;
    var curr2 = curr1.next;

    while(curr1){
        if(!curr2 || curr2.val !== curr1.val){
            if(curr1.next !== curr2){
                clear(curr1, curr2);
                preNode.next = curr2;
            } else {
              preNode = curr1;
            }

            curr1 = curr2;
            if(curr2){
              curr2 = curr2.next;
            }
        } else {
          if(curr2){
            curr2 = curr2.next;
          }
        }
    }
    return tempHead.next;

    function clear(node, stop){
        var temp;
        while(node !== stop){
            temp = node.next;
            node.next = null;
            node = temp;
        }
    }
}

給定一個(gè)二叉樹(shù)和其中的一個(gè)結(jié)點(diǎn)，請(qǐng)找出中序遍歷順序的下一個(gè)結(jié)點(diǎn)并且返回。注意，樹(shù)中的結(jié)點(diǎn)不僅包含左右子結(jié)點(diǎn)，同時(shí)包含指向父結(jié)點(diǎn)的指針。

function GetNext(pNode){
    if (!pNode){
        return pNode;
    }
    if (pNode.right){
        pNode = pNode.right;
        while (pNode.left) {
            pNode = pNode.left;
        }
        return pNode;
    } else if(pNode.next && pNode.next.left == pNode){
        return pNode.next;
    } else if(pNode.next && pNode.next.right == pNode){
        while(pNode.next && pNode.next.left != pNode){
            pNode = pNode.next ;
        }
        return pNode.next;
    } else {
        return pNode.next;
    }
}

請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，用來(lái)判斷一顆二叉樹(shù)是不是對(duì)稱的。注意，如果一個(gè)二叉樹(shù)同此二叉樹(shù)的鏡像是同樣的，定義其為對(duì)稱的。

function isSymmetrical(pRoot){
    if(!pRoot){
      return true;
    }
    return symmetrical(pRoot, pRoot);

    function symmetrical(node1,node2){
        if(!node1 && !node2)
            return true;
        if(!node1 || !node2)
            return false;
        if(node1.val != node2.val)
            return false;
        return symmetrical(node1.left, node2.right) && symmetrical(node1.right, node2.left);
    }
}

請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)按照之字形打印二叉樹(shù)，即第一行按照從左到右的順序打印，第二層按照從右至左的順序打印，第三行按照從左到右的順序打印，其他行以此類推。

function Print(pRoot) {
    var res = [];
    if(!pRoot){
        return res;
    }
    var que = [];
    que.push(pRoot);
    var flag = false;
    while(que.length > 0){
        var vec = [];
        var len = que.length;
        for(var i = 0; i < len; i++){
            var tmp = que.shift(); //front
            vec.push(tmp.val);
            if(tmp.left)
                que.push(tmp.left);
            if(tmp.right)
                que.push(tmp.right);
        }
        if(flag){
            vec.reverse();
        }
        res.push(vec);
        flag = !flag;
    }
    return res;
}

從上到下按層打印二叉樹(shù)，同一層結(jié)點(diǎn)從左至右輸出。每一層輸出一行。

function Print(pRoot) {
    var res = [];
    if(!pRoot){
        return res;
    }
    var que = [];
    que.push(pRoot);
    while(que.length > 0){
        var vec = [];
        var len = que.length;
        for(var i = 0; i < len; i++){
            var tmp = que.shift(); //front
            vec.push(tmp.val);
            if(tmp.left)
                que.push(tmp.left);
            if(tmp.right)
                que.push(tmp.right);
        }
        res.push(vec);
    }
    return res;
}

請(qǐng)實(shí)現(xiàn)兩個(gè)函數(shù)，分別用來(lái)序列化和反序列化二叉樹(shù)

function Serialize(pNode) {
    var str = [];
    ser(pNode);

    for(var i = str.length - 1; i >= 0; i--){
      if(str[i] !== "#"){
        break;
      }
      str.pop();
    }

    return str.join();

    function ser(node){
        if(!node){
            str.push("#");
            return;
        }
        str.push(node.val);
        ser(node.left);
        ser(node.right);
    }
}
function Deserialize(str) {
    var index = -1;
    var len = str.length;
    if(index >= len){
        return null;
    }
    var arr = str.split(",");
    var head = des();

    return head;

    function des(node){
        index++;
        if(arr[index] && arr[index] !== "#"){
            var temp = new TreeNode(arr[index]);
            node = temp;
            node.left = des();
            node.right = des();
        }
        return node;
    }
}

給定一顆二叉搜索樹(shù)，請(qǐng)找出其中的第k大的結(jié)點(diǎn)。例如， 5 / 3 7 / / 2 4 6 8 中，按結(jié)點(diǎn)數(shù)值大小順序第三個(gè)結(jié)點(diǎn)的值為4。

function KthNode(pRoot, k){
    if(!pRoot || !k){
        return null;
    }
    return KthCore(pRoot);

    function KthCore(node){
        var target = null;

        if(node.left){
            target = KthCore(node.left);
        }
        if(!target){
            if(k === 1)
                target = node;
            k--;
        }

        if(!target && node.right)
            target = KthCore(node.right);

        return target;
    }
}

如何得到一個(gè)數(shù)據(jù)流中的中位數(shù)？如果從數(shù)據(jù)流中讀出奇數(shù)個(gè)數(shù)值，那么中位數(shù)就是所有數(shù)值排序之后位于中間的數(shù)值。如果從數(shù)據(jù)流中讀出偶數(shù)個(gè)數(shù)值，那么中位數(shù)就是所有數(shù)值排序之后中間兩個(gè)數(shù)的平均值。

var arr = [];
function Insert(num){
    arr.push(num);
    arr.sort(function(a,b){
        return a - b;
    });
    return arr;
}
function GetMedian(){
    var mid = Math.floor(arr.length / 2);
    if((arr.length & 1) === 0){
        var n1 = arr[mid];
        var n2 = arr[mid - 1];
        return (n1 + n2) / 2;
    } else {
        return arr[mid]
    }
}

給定一個(gè)數(shù)組和滑動(dòng)窗口的大小，找出所有滑動(dòng)窗口里數(shù)值的最大值。例如，如果輸入數(shù)組{2,3,4,2,6,2,5,1}及滑動(dòng)窗口的大小3，那么一共存在6個(gè)滑動(dòng)窗口，他們的最大值分別為{4,4,6,6,6,5}； 針對(duì)數(shù)組{2,3,4,2,6,2,5,1}的滑動(dòng)窗口有以下6個(gè)： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

function maxInWindows(num, size){
    if(!num || num.length === 0){
        return null;
    }
    var max = [];
    if(num.length >= size && size >= 1){
        var index = [];

        for(var i = 0; i < size; ++i){
            while(index.length > 0 && num[i] >= num[index[index.length - 1]])
                index.pop();
            index.push(i);
        }

        for(var i = size; i < num.length; ++i){
            max.push(num[index[0]]);
            while(index.length > 0 && num[i] >= num[index[index.length - 1]])
                index.pop();
            if(index.length > 0 && index[0] <= i - size)
                index.shift();
            index.push(i);
        }
        max.push(num[index[0]]);
    }
    return max;
}

請(qǐng)?jiān)O(shè)計(jì)一個(gè)函數(shù)，用來(lái)判斷在一個(gè)矩陣中是否存在一條包含某字符串所有字符的路徑。路徑可以從矩陣中的任意一個(gè)格子開(kāi)始，每一步可以在矩陣中向左，向右，向上，向下移動(dòng)一個(gè)格子。如果一條路徑經(jīng)過(guò)了矩陣中的某一個(gè)格子，則該路徑不能再進(jìn)入該格子。 例如 a b c e s f c s a d e e 矩陣中包含一條字符串"bcced"的路徑，但是矩陣中不包含"abcb"路徑，因?yàn)樽址牡谝粋€(gè)字符b占據(jù)了矩陣中的第一行第二個(gè)格子之后，路徑不能再次進(jìn)入該格子。

function hasPath(matrix, rows, cols, path){
    var visited = [];
    for(var i = 0; i < rows * cols; i++){
        visited[i] = false;
    }
    var pathLen = 0;
    try{
        for(var i = 0; i < rows; i++){
            for(var j = 0; j < cols; j++){
                if(core(i,j)){
                    return true;
                }
            }
        }
    } finally {
        visited.length = 0;
    }

    return false;

    function core(row, col){
        if(path.length === pathLen){
            return true;
        }
        var hasPath = false;
        if(row >= 0 && row < rows && col >= 0 && col < cols && matrix[row * cols + col] === path[pathLen] && !visited[row * cols + col]){
            pathLen++;
            visited[row * cols + col] = true;
            hasPath = core(row - 1, col)+ core(row, col - 1)
                    + core(row + 1, col) + core(row, col + 1);
            if(!hasPath){
                pathLen--;
                visited[row * cols + col] = false;
            }
        }
        return hasPath;
    }
}

地上有一個(gè)m行和n列的方格。一個(gè)機(jī)器人從坐標(biāo)0,0的格子開(kāi)始移動(dòng)，每一次只能向左，右，上，下四個(gè)方向移動(dòng)一格，但是不能進(jìn)入行坐標(biāo)和列坐標(biāo)的數(shù)位之和大于k的格子。 例如，當(dāng)k為18時(shí)，機(jī)器人能夠進(jìn)入方格（35,37），因?yàn)?+5+3+7 = 18。但是，它不能進(jìn)入方格（35,38），因?yàn)?+5+3+8 = 19。請(qǐng)問(wèn)該機(jī)器人能夠達(dá)到多少個(gè)格子？

function movingCount(threshold, rows, cols){
    var visited = [];
    for(var i = 0; i < rows * cols; ++i)
        visited[i] = false;
    var count = movingCountCore(0, 0);
    visited.length = 0;
    return count;

    function getDigitSum(number){
        var sum = 0;
        while(number > 0){
            sum += number % 10;
            number = Math.floor(number / 10);
        }
        return sum;
    }

    function check(row, col){
        if(row >= 0 && row < rows && col >= 0 && col < cols && getDigitSum(row) + getDigitSum(col) <= threshold && !visited[row * cols + col])
            return true;
        return false;
    }

    function movingCountCore(row, col){
        var count = 0;
        if(check(row, col)) {
            visited[row * cols + col] = true;
            count = 1 + movingCountCore(row - 1, col)
                    + movingCountCore(row, col - 1)
                    + movingCountCore(row + 1, col)
                    + movingCountCore(row, col + 1);
        }
        return count;
    }
}

二叉樹(shù)構(gòu)造

function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
}
function Tree(arr, node, num = 1){
    if(!arr || arr.length === 0){
        return new TreeNode(null);
    }
    node = node || new TreeNode(arr[num - 1]);
    var curr = node;
    if(num * 2 - 1 < arr.length && arr[num * 2 - 1]){
      curr.left = new TreeNode(arr[num * 2 - 1]);
      Tree(arr, curr.left, num * 2);
    }
    if(num * 2 < arr.length && arr[num * 2]){
      curr.right = new TreeNode(arr[num * 2]);
      Tree(arr, curr.right, num * 2 + 1);
    }
    return node;
}
// 根據(jù)數(shù)組生成二叉樹(shù)
var tree = new Tree([3,2,4,8,7,null,10,null,null,5,9]);
console.log(tree);

單向鏈表構(gòu)造

function ListNode(x){
    this.val = x;
    this.next = null;
}
function LinkedList(arr){
    if(!arr || arr.length === 0){
        return new ListNode(null);
    }
    var head = new ListNode(arr[0]);
    var len = arr.length;
    var curr = head;
    for(var i = 1; i < len; i++){
        var temp = new ListNode(arr[i]);
        curr.next = temp;
        curr = curr.next;
    }
    return head;
}
var ll = new LinkedList([3,2,4,8,7,10,5,9]);
console.log(ll);

?？途W(wǎng) Node.js 多行輸入測(cè)試 (如果不能運(yùn)行請(qǐng)更新瀏覽器來(lái)支持 es6 語(yǔ)法)

(function(){

  /* Todo: This Array contains the input lines in sequence. Each of the elements is like a line of input. */
  var test_lines =["5","1 2 3 3 5","3","1 2 1","2 4 5","3 5 3"];   // Do not change the name of this array if you don"t like bugs.

  /****************************************************************
  Todo: Add your code here including the callback function of event "rl.on()" and
  global variables except the statements and definitions of "readline" and "rl".
  *****************************************************************/

  /* global variables here */
  var lines = 1;

  /* callback function of "rl.on()" */
  function main(line) {    // Do not change the name of this function if you don"t like bugs.
    var str = line.trim();
    console.log("lines",lines++,":",str);
  }

  /**************** End of Your Code *****************/

  (function(){
    var test_len = test_lines.length;
    var test_it = gen(test_lines);
    var test_val = test_it.next();
    while(test_len){
       main(test_val.value);
       test_val = test_it.next();
       test_len--;
     }
    function* gen(test_lines){
      var len = test_lines.length;
      var i = 0;
      while(len){
        yield test_lines[i];
        i++;
      }
    }
  }())
}());