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

本文為8月牛客網《劍指 offer》刷題做得，現整理出來作為參考。
雖然是算法題，但本文用 JavaScript 編寫，看了《劍指 offer》以后發現很多問題處理的過程并不是最好的，所以本文僅供參考。以前全部代碼 AC 通過，但即便是 AC 的代碼也不見得就是最好的，比如有的內存分配了卻沒有釋放，這樣的問題牛客網是查不出來的。

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

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;
}

請實現一個函數，將一個字符串中的空格替換成“%20”。例如，當字符串為We Are Happy.則經過替換之后的字符串為We%20Are%20Happy。

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

輸入一個鏈表，從尾到頭打印鏈表每個節點的值。

/*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();
    }
}

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

/* 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;
}

用兩個棧來實現一個隊列，完成隊列的Push和Pop操作。 隊列中的元素為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;
}

把一個數組最開始的若干個元素搬到數組的末尾，我們稱之為數組的旋轉。 輸入一個非遞減排序的數組的一個旋轉，輸出旋轉數組的最小元素。 例如數組{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉，該數組的最小值為1。 NOTE：給出的所有元素都大于0，若數組大小為0，請返回0。

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

大家都知道斐波那契數列，現在要求輸入一個整數n，請你輸出斐波那契數列的第n項。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級臺階，也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法。

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級臺階，也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的臺階總共有多少種跳法。

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

我們可以用21的小矩形橫著或者豎著去覆蓋更大的矩形。請問用n個21的小矩形無重疊地覆蓋一個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;
}

輸入一個整數，輸出該數二進制表示中1的個數。其中負數用補碼表示。

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);
}

給定一個double類型的浮點數base和int類型的整數exponent。求base的exponent次方。

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

輸入一個整數數組，實現一個函數來調整該數組中數字的順序，使得所有的奇數位于數組的前半部分，所有的偶數位于位于數組的后半部分，并保證奇數和奇數，偶數和偶數之間的相對位置不變。

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);
}

輸入一個鏈表，輸出該鏈表中倒數第k個結點。

/*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;
}

輸入一個鏈表，反轉鏈表后，輸出鏈表的所有元素。

/*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;
}

輸入兩個單調遞增的鏈表，輸出兩個鏈表合成后的鏈表，當然我們需要合成后的鏈表滿足單調不減規則。

/*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;
    }

    //防止內存泄露
    curr = result.next;
    result.next = null;
    result = curr;
    curr = curr1 = curr2 = null;

    return result;
}

輸入兩棵二叉樹A，B，判斷B是不是A的子結構。（ps：我們約定空樹不是任意一個樹的子結構）

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;
        }

    }
}

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

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);
    }
}

輸入一個矩陣，按照從外向里以順時針的順序依次打印出每一個數字，例如，如果輸入如下矩陣： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 則依次打印出數字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;
}

定義棧的數據結構，請在該類型中實現一個能夠得到棧最小元素的min函數。

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);
}

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

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;
}

從上往下打印出二叉樹的每個節點，同層節點從左至右打印。

/* 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;
}

輸入一個整數數組，判斷該數組是不是某二叉搜索樹的后序遍歷的結果。如果是則輸出Yes,否則輸出No。假設輸入的數組的任意兩個數字都互不相同。(測試用例用的是 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));
    }
}

輸入一顆二叉樹和一個整數，打印出二叉樹中結點值的和為輸入整數的所有路徑。路徑定義為從樹的根結點開始往下一直到葉結點所經過的結點形成一條路徑。

/* 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;
    }
}

輸入一個復雜鏈表（每個節點中有節點值，以及兩個指針，一個指向下一個節點，另一個特殊指針指向任意一個節點），返回結果為復制后復雜鏈表的head。（注意，輸出結果中請不要返回參數中的節點引用，否則判題程序會直接返回空）

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

輸入一棵二叉搜索樹，將該二叉搜索樹轉換成一個排序的雙向鏈表。要求不能創建任何新的結點，只能調整樹中結點指針的指向。

將左子樹構成雙向鏈表，返回的是左子樹的尾結點，將其連接到root的左邊；
將右子樹構成雙向鏈表，將其追加到root結點之后，并返回尾結點；
向左遍歷返回的鏈表至頭結點處，即為所求雙向鏈表的首結點。

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;
    }
}

輸入一個字符串,按字典序打印出該字符串中字符的所有排列。例如輸入字符串abc,則打印出由字符a,b,c所能排列出來的所有字符串abc,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);   //回溯
        }
    }
}

數組中有一個數字出現的次數超過數組長度的一半，請找出這個數字。例如輸入一個長度為9的數組{1,2,3,2,2,2,5,4,2}。由于數字2在數組中出現了5次，超過數組長度的一半，因此輸出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個整數，找出其中最小的K個數。例如輸入4,5,1,6,2,7,3,8這8個數字，則最小的4個數字是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偶爾會拿些專業問題來忽悠那些非計算機專業的同學。今天測試組開完會后,他又發話了:在古老的一維模式識別中,常常需要計算連續子向量的最大和,當向量全為正數的時候,問題很好解決。但是,如果向量中包含負數,是否應該包含某個負數,并期望旁邊的正數會彌補它呢？例如:{6,-3,-2,7,-15,1,2,2},連續子向量的最大和為8(從第0個開始,到第3個為止)。你會不會被他忽悠住？(子向量的長度至少是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的整數中1出現的次數,并算出100~1300的整數中1出現的次數？為此他特別數了一下1~13中包含1的數字有1、10、11、12、13因此共出現6次,但是對于后面問題他就沒轍了。ACMer希望你們幫幫他,并把問題更加普遍化,可以很快的求出任意非負整數區間中1出現的次數。

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;
}

輸入一個正整數數組，把數組里所有數字拼接起來排成一個數，打印能拼接出的所有數字中最小的一個。例如輸入數組{3，32，321}，則打印出這三個數字能排成的最小數字為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的數稱作丑數（Ugly Number）。例如6、8都是丑數，但14不是，因為它包含因子7。 習慣上我們把1當做是第一個丑數。求按從小到大的順序的第N個丑數。

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];
}

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

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);

}

在數組中的兩個數字，如果前面一個數字大于后面的數字，則這兩個數字組成一個逆序對。輸入一個數組,求出這個數組中的逆序對的總數P。并將P對1000000007取模的結果輸出。 即輸出P%1000000007

由于時間空間復雜度的限制，js 貌似無法完成這個題，所以使用 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;
    }
};

輸入兩個鏈表，找出它們的第一個公共結點。

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;
    }
}

統計一個數字在排序數組中出現的次數。

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

輸入一棵二叉樹，求該樹的深度。從根結點到葉結點依次經過的結點（含根、葉結點）形成樹的一條路徑，最長路徑的長度為樹的深度。

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--;
    }
}

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

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--;
        }
    }
}

一個整型數組里除了兩個數字之外，其他的數字都出現了兩次。請寫程序找出這兩個只出現一次的數字。

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

小明很喜歡數學,有一天他在做數學作業時,要求計算出9~16的和,他馬上就寫出了正確答案是100。但是他并不滿足于此,他在想究竟有多少種連續的正數序列的和為100(至少包括兩個數)。沒多久,他就得到另一組連續正數和為100的序列:18,19,20,21,22。現在把問題交給你,你能不能也很快的找出所有和為S的連續正數序列? 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);
    }
}

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

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];
}

匯編語言中有一種移位指令叫做循環左移（ROL），現在有個簡單的任務，就是用字符串模擬這個指令的運算結果。對于一個給定的字符序列S，請你把其循環左移K位后的序列輸出。例如，字符序列S=”abcXYZdef”,要求輸出循環左移3位后的結果，即“XYZdefabc”。是不是很簡單？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;
}

牛客最近來了一個新員工Fish，每天早晨總是會拿著一本英文雜志，寫些句子在本子上。同事Cat對Fish寫的內容頗感興趣，有一天他向Fish借來翻看，但卻讀不懂它的意思。例如，“student. a am I”。后來才意識到，這家伙原來把句子單詞的順序翻轉了，正確的句子應該是“I am a student.”。Cat對一一的翻轉這些單詞順序可不在行，你能幫助他么？

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

LL今天心情特別好,因為他去買了一副撲克牌,發現里面居然有2個大王,2個小王(一副牌原本是54張^_^)...他隨機從中抽出了5張牌,想測測自己的手氣,看看能不能抽到順子,如果抽到的話,他決定去買體育彩票,嘿嘿！！“紅心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是順子.....LL不高興了,他想了想,決定大小 王可以看成任何數字,并且A看作1,J為11,Q為12,K為13。上面的5張牌就可以變成“1,2,3,4,5”(大小王分別看作2和4),“So Lucky!”。LL決定去買體育彩票啦。 現在,要求你使用這幅牌模擬上面的過程,然后告訴我們LL的運氣如何。為了方便起見,你可以認為大小王是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;
}

每年六一兒童節,牛客都會準備一些小禮物去看望孤兒院的小朋友,今年亦是如此。HF作為牛客的資深元老,自然也準備了一些小游戲。其中,有個游戲是這樣的:首先,讓小朋友們圍成一個大圈。然后,他隨機指定一個數m,讓編號為0的小朋友開始報數。每次喊到m-1的那個小朋友要出列唱首歌,然后可以在禮品箱中任意的挑選禮物,并且不再回到圈中,從他的下一個小朋友開始,繼續0...m-1報數....這樣下去....直到剩下最后一個小朋友,可以不用表演,并且拿到牛客名貴的“名偵探柯南”典藏版(名額有限哦!!^_^)。請你試著想下,哪個小朋友會得到這份禮品呢？(注：小朋友的編號是從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等關鍵字及條件判斷語句（A?B:C）。

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

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

寫一個函數，求兩個整數之和，要求在函數體內不得使用+、-、*、/四則運算符號。

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

將一個字符串轉換成一個整數，要求不能使用字符串轉換整數的庫函數。 數值為0或者字符串不是一個合法的數值則返回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;
}

在一個長度為n的數組里的所有數字都在0到n-1的范圍內。 數組中某些數字是重復的，但不知道有幾個數字是重復的。也不知道每個數字重復幾次。請找出數組中任意一個重復的數字。 例如，如果輸入長度為7的數組{2,3,1,0,2,5,3}，那么對應的輸出是第一個重復的數字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;
}

給定一個數組A[0,1,...,n-1],請構建一個數組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;
}

請實現一個函數用來匹配包括"."和""的正則表達式。模式中的字符"."表示任意一個字符，而""表示它前面的字符可以出現任意次（包含0次）。 在本題中，匹配是指字符串的所有字符匹配整個模式。例如，字符串"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);
}

請實現一個函數用來判斷字符串是否表示數值（包括整數和小數）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示數值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。

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

請實現一個函數用來找出字符流中第一個只出現一次的字符。例如，當從字符流中只讀出前兩個字符"go"時，第一個只出現一次的字符是"g"。當從該字符流中讀出前六個字符“google"時，第一個只出現一次的字符是"l"。

function Init(){
    streamNums = [];   //定義一個全局變量, 不用var
    streamNumsLen = 256;   //定義一個全局變量, 不用var
    streamNumsIndex = 0;   //定義一個全局變量, 不用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;
}

一個鏈表中包含環，請找出該鏈表的環的入口結點。

/*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;
    }
}

在一個排序的鏈表中，存在重復的結點，請刪除該鏈表中重復的結點，重復的結點不保留，返回鏈表頭指針。 例如，鏈表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;
        }
    }
}

給定一個二叉樹和其中的一個結點，請找出中序遍歷順序的下一個結點并且返回。注意，樹中的結點不僅包含左右子結點，同時包含指向父結點的指針。

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;
    }
}

請實現一個函數，用來判斷一顆二叉樹是不是對稱的。注意，如果一個二叉樹同此二叉樹的鏡像是同樣的，定義其為對稱的。

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);
    }
}

請實現一個函數按照之字形打印二叉樹，即第一行按照從左到右的順序打印，第二層按照從右至左的順序打印，第三行按照從左到右的順序打印，其他行以此類推。

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;
}

從上到下按層打印二叉樹，同一層結點從左至右輸出。每一層輸出一行。

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;
}

請實現兩個函數，分別用來序列化和反序列化二叉樹

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;
    }
}

給定一顆二叉搜索樹，請找出其中的第k大的結點。例如， 5 / 3 7 / / 2 4 6 8 中，按結點數值大小順序第三個結點的值為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;
    }
}

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

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]
    }
}

給定一個數組和滑動窗口的大小，找出所有滑動窗口里數值的最大值。例如，如果輸入數組{2,3,4,2,6,2,5,1}及滑動窗口的大小3，那么一共存在6個滑動窗口，他們的最大值分別為{4,4,6,6,6,5}； 針對數組{2,3,4,2,6,2,5,1}的滑動窗口有以下6個： {[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;
}

請設計一個函數，用來判斷在一個矩陣中是否存在一條包含某字符串所有字符的路徑。路徑可以從矩陣中的任意一個格子開始，每一步可以在矩陣中向左，向右，向上，向下移動一個格子。如果一條路徑經過了矩陣中的某一個格子，則該路徑不能再進入該格子。 例如 a b c e s f c s a d e e 矩陣中包含一條字符串"bcced"的路徑，但是矩陣中不包含"abcb"路徑，因為字符串的第一個字符b占據了矩陣中的第一行第二個格子之后，路徑不能再次進入該格子。

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;
    }
}

地上有一個m行和n列的方格。一個機器人從坐標0,0的格子開始移動，每一次只能向左，右，上，下四個方向移動一格，但是不能進入行坐標和列坐標的數位之和大于k的格子。 例如，當k為18時，機器人能夠進入方格（35,37），因為3+5+3+7 = 18。但是，它不能進入方格（35,38），因為3+5+3+8 = 19。請問該機器人能夠達到多少個格子？

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;
    }
}

二叉樹構造

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;
}
// 根據數組生成二叉樹
var tree = new Tree([3,2,4,8,7,null,10,null,null,5,9]);
console.log(tree);

單向鏈表構造

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);

牛客網 Node.js 多行輸入測試 (如果不能運行請更新瀏覽器來支持 es6 語法)

(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++;
      }
    }
  }())
}());