剑指offer（js版）

客官°小女子只卖身不卖艺 2021-11-23 07:32 280阅读 0赞

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

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

function replaceSpace(str)
    {
        // write code here
        let reg = /\s/g;//正则匹配所有的空格
        return str.replace(reg,'%20');//将空格替换为%20
    }

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

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

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

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

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

function minNumberInRotateArray(rotateArray)
    {
        // write code here
        if(rotateArray.length === 0)
            return 0;
        rotateArray.sort(function(a,b){
            return a-b;
        })
        return rotateArray[0];
    }

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。

n<=39

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。（现在台阶为n阶，青蛙可以从n-1阶跳1级到达n阶，也可以从n-2阶跳2级到达n阶）

function jumpFloor(number)
    {
        // write code here
        let a = 1,
            b = 2,
            c = 0;
        if(number <= 2)
            return number;
        for(let i = 3; i <= number; i++){
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }

我们可以用2\*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2\*1的小矩形无重叠地覆盖一个2\*n的大矩形，总共有多少种方法？

function rectCover(number)
    {
        // write code here
        if(number<=2)
            return number;
        else
            return rectCover(number - 1)+rectCover(number - 2);
    }

10.

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

//solution1
    function NumberOf1(n)
    {
        // write code here
        let cou = 0;
        if(n==0)
            return 0;
        if(n>=0){
            while(n){
                cou+=n%2;
                n/=2;n = parseInt(n);
            }
            return cou;
        }
        else{
            n=-n;
            let i = 0;
             while(n){
                 i++;
                 cou += n%2;
                  n /= 2;
                  n = parseInt(n);
            }
            return 32-i+cou;
        }
    }

//solution2
    function newNumberOf1(n) {
      let count = 0;
      while (n) {
        n = n & n - 1; 
        count++;
      }
      return count;
    }

11.

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

function Power(base, exponent)
    {
        // write code here
        return base**exponent;
    }

12.输入一个链表，输出该链表中倒数第k个结点。

/*function ListNode(x){
        this.val = x;
        this.next = null;
    }*/
    function FindKthToTail(head, k)
    {
        // write code here
        if(head === null||k <= 0)    return null;
        let pNode1 = head,
            pNode2 = head;
        while(--k){
            if(pNode1.next === null)
                return null;
            pNode1 = pNode1.next;
        }
        while(pNode1.next !== null){
            pNode1 = pNode1.next;
            pNode2 = pNode2.next;
        }
        return pNode2;
        
            
    }

13.

输入一个链表，反转链表后，输出新链表的表头。

/*function ListNode(x){
        this.val = x;
        this.next = null;
    }*/
    function ReverseList(pHead)
    {
        // write code here
        let pNode1 = pHead,
            pNode2;
        while(pNode1.next != null){
            pNode2 = pNode1;
            pNode1 = pNode1.next;
        }
        return pNode2;
    }

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

/*function ListNode(x){
        this.val = x;
        this.next = null;
    }*/
    function Merge(pHead1, pHead2)
    {
        // write code here
      let pMergeHead = null;
      // write code here
      if (pHead1 === null) return pHead2;
      if (pHead2 === null) return pHead1;
      if (pHead1.val < pHead2.val) {
        pMergeHead = pHead1;
        pMergeHead.next = Merge(pHead1.next, pHead2);
      } else {
        pMergeHead = pHead2;
        pMergeHead.next = Merge(pHead1, pHead2.next);
      }
      return pMergeHead;
    }

15.

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

/* function TreeNode(x) {
        this.val = x;
        this.left = null;
        this.right = null;
    } */
    function tree1Hastree2(p1,p2){
        if(p2 == null)    return true;
        if(p1 == null)    return false;
        if(p1.val !== p2.val)    return false;
        return tree1Hastree2(p1.left, p2.left) && tree1Hastree2(p1.right, p2.right);
    }
    function HasSubtree(pRoot1, pRoot2)
    {
        // write code here
        let res = 0;
        if(pRoot1 == null || pRoot2 == null)    return false;
        if(pRoot1.val == pRoot2.val){
            res = tree1Hastree2(pRoot1,pRoot2)
        }
        if(!res)
            res = HasSubtree(pRoot1.left, pRoot2);
        if (!res)
            res = HasSubtree(pRoot1.right, pRoot2);
          return res;
    
    }

16.

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

## 输入描述: ##

二叉树的镜像定义：源二叉树 
        	    8
        	   /  \
        	  6   10
        	 / \  / \
        	5  7 9 11
        	镜像二叉树
        	    8
        	   /  \
        	  10   6
        	 / \  / \
        	11 9 7  5

/* function TreeNode(x) {
        this.val = x;
        this.left = null;
        this.right = null;
    } */
    function Mirror(root) {
      if (root === null) return;
      Mirror(root.left);
      Mirror(root.right);
      [root.left, root.right] = [root.right, root.left];//ES6解构解析
      return root;
    }