1.
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

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

2.
请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

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

3.
输入一个链表，从尾到头打印链表每个节点的值。

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

4.
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列 {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;
}

5.
用两个栈来实现一个队列，完成队列的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;
}

6.
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{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);
}

7.
大家都知道斐波那契数列，现在要求输入一个整数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;
}

8.
一只青蛙一次可以跳上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;
}

9.
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

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

10.
我们可以用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;
}

11.
输入一个整数，输出该数二进制表示中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);
}

12.
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

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

13.
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

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

14.
输入一个链表，输出该链表中倒数第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;
}

15.
输入一个链表，反转链表后，输出链表的所有元素。

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

16.
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

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

17.
v输入两棵二叉树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;
        }
    }
}

18.
操作给定的二叉树，将其变换为源二叉树的镜像。

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

19.
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下矩阵： 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, col = matrix[0].length;
    var len = rows * cols;
    var i = 0, j = 0;
    var circle = 0;
    while(1) {
        while (j < cols - cirle) {
            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;
}

20.
定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的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);
}

21.
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列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;
}

22.
从上往下打印出二叉树的每个节点，同层节点从左至右打印。

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

23.
输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

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

24.
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

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

25.
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

将左子树构成双向链表，返回的是左子树的尾结点，将其连接到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;
    }
}