剑指offer —— javaScript解（持续更新）

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

思路：从最后一个一维数组的第一个元素开始向上/向右进行遍历，若整数比数组中该位置的元素小，则向上遍历，否则向右遍历该一维数组。

 function Find(target, array)
    {
        // write code here
        for(let i=array.length-1,j=0;i>=0 && j<array[0].length;){
            if(target>array[i][j]){
                j++;
            }else if(target<array[i][j]){
                i++;
            }else{
                return true;
            }
        }
        return false;
    }

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

思想：直接采用replace方法进行替换

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

3. 输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

思想：对链表进行正向遍历，并将每一个结点的值push进数组中，最终返回翻转后的该数组。

 function printListFromTailToHead(head)
    {
        // write code here
        let now = head;
        let arr=[];
        while(now){
            arr.push(now.val);
            now = now.next;
        }
        return arr.reverse();
    }

4. 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

思想：取出前序遍历序列中的第一个元素，该元素为二叉树的根，在中序遍历序列中查找该元素

• 对于中序遍历序列而言，该元素左边的所有元素构成的集合是根元素的左子树所有结点构成的集合，该元素右边的所有元素构成的集合是根元素的右子树所有结点构成的集合。
• 对于前序遍历序列而言，该元素后的x个元素为根结点对应的左子树所有结点构成的集合（此处的x为中序遍历序列中该元素对应的索引位置）,剩下元素为根结点对应的右子树的所有结点构成的集合。
• 对新找出来的左右子树进行以上重复操作，最终可得到二叉树。

function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
}
function reConstructBinaryTree(pre, vin)
{
    // write code here
    if(pre.length==0 || vin.length==0){
        return null;
    }
    let root = new TreeNode(pre[0]);
    for(let i=0;i<vin.length;i++){
        if(vin[i]==pre[0]){
            root.left = reConstructBinaryTree(pre.slice(1,i+1),vin.slice(0,i));
            root.right = reConstructBinaryTree(pre.slice(i+1,pre.length),vin.slice(i+1,vin.length))
        }
    }
    return root;
}

5. 用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

思想：对于两个栈，其中一个（outArr）保存一次pop之前push的所有元素，一个(inArr)用来保存一次pop之后push的所有元素，当调用队列的push操作时将其push进inArr，当调用队列的pop操作时将outArr的栈顶元素pop出来。

let inArr=[];
let outArr=[];
function push(node)
{
    inArr.push(node);
}
function pop()
{
    if(!outArr.length){
        while(inArr.length){
            outArr.push(inArr.pop());
        }
    }
    return outArr.pop();
}