《剑指offer》JavaScript版01~06

1.二维数组的查找

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

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

2.替换空格

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

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

3.从尾到头打印链表

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

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function printListFromTailToHead(head)
{let res = [];
 while(head!==null) {
     res.unshift(head.val);
     head = head.next;
 }
 return res;
    
    // write code here
}

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
}
 const index = vin.indexOf(pre[0])
 const left = vin.slice(0, index)
 const right = vin.slice(index + 1)
 return {
     val: pre[0],
     left: reConstructBinaryTree(pre.slice(1,index+1),left),
     right: reConstructBinaryTree(pre.slice(index+1),right)
}
    // write code here
}

5.用两个栈实现队列

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

const inStack = [];
const outStack = [];
function push(node)
{
    inStack.push(node);
    // write code here
}
function pop()
{if(!outStack.length) {
    while(inStack.length) {
        outStack.push(inStack.pop());
    }  
}
 return outStack.pop();
    // write code here
}

6.旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

function minNumberInRotateArray(rotateArray)
{if(rotateArray.length === 0) return 0;
 var length = rotateArray.length;
 var min = rotateArray[length-1];
 for(let i = length - 1;i>=0;i--) {
     if (rotateArray[i] < min) {
         min = rotateArray[i];
     } 
 }
 return min;
    // write code here
}