牛客——剑指Offer编程题练习总结（js版）

港控/mmm° 2024-04-17 14:13 51阅读 0赞

### 文章目录 ###

*   *   *   *   *   *  1 二维数组查找整数
                     *  2 字符串的空格替换
                     *  3 链表的遍历输出
                     *  4 二叉树的重建
                     *  5 两个栈实现队列
                     *  6 查找最小值
                     *  7 斐波那契数列
                     *  8 青蛙跳
                     *  9 超级青蛙跳
                     *  10 矩阵覆盖
                     *  11 二进制1的个数
                     *  12 次方求解
                     *  13 调整数组顺序使奇数位于偶数前面
                     *  14 链表中倒数第k个结点
                     *  15 反转链表
                     *  16 合并两个排序的链表
                     *  17 树的子结构
                     *  18 二叉树的镜像
                     *  19 顺时针打印矩阵
                     *  20 包含min函数的栈
                     *  21 栈的压入、弹出序列
                     *  22 从上往下打印二叉树（层序遍历）
                     *  23 二叉搜索树的后序遍历序列
                     *  24 二叉树中和为某一值的路径
                     *  25 复杂链表的复制
                     *  26 二叉搜索树与双向链表
                     *  27 字符串的排列
                     *  28 数组中出现次数超过一半的数字
                     *  29 最小的K个数
                     *  30 连续子数组的最大和
                     *  31 整数中1出现的次数（从1到n整数中1出现的次数）
                     *  32 把数组排成最小的数
                     *  33 丑数
                     *  34 第一个只出现一次的字符
                     *  35 数组中的逆序对（难）
                     *  36 两个链表的第一个公共结点
                     *  37 数字在排序数组中出现的次数
                     *  38 二叉树的深度
                     *  39 平衡二叉树
                     *  40 数组中只出现一次的数字
                     *  41 和为S的连续正数序列
                     *  42 和为S的两个数字
                     *  43 左旋转字符串
                     *  44 翻转单词顺序列
                     *  45 扑克牌顺子
                     *  46 孩子们的游戏(圆圈中最后剩下的数)
                     *  47 求1+2+3+...+n
                     *  48 不用加减乘除做加法
                     *  49 把字符串转换成整数
                     *  50 数组中重复的数字
                     *  51 构建乘积数组
                     *  52 正则表达式匹配
                     *  53 表示数值的字符串
                     *  54 字符流中第一个不重复的字符
                     *  55 链表中环的入口结点
                     *  56 删除链表中重复的结点
                     *  57 二叉树的下一个结点
                     *  58 对称的二叉树
                     *  59 按之字形顺序打印二叉树
                     *  60 把二叉树打印成多行
                     *  61序列化二叉树
                     *  62 二叉搜索树的第k个结点
                     *  63 数据流中的中位数
                     *  64 滑动窗口的最大值
                     *  65 矩阵中的路径
                     *  66 机器人的运动范围
                     *  67 剪绳子

> ——可内推网易，具体看牛客帖子： [点击此处或复制后面的网址][Link 1]，https://www.nowcoder.com/discuss/457173?type=7&order=0&pos=57&page=0&source\_id=discuss\_center\_7&channel=666

**[剑指offer(点击此处)][offer]的题目在牛客网上可以看**

--------------------

###### 1 二维数组查找整数 ######

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

// 方式一（暴力循环）：
    // 解题思路：使用双重循环，外层表示当前第几行的数组，内层表示对每行的一维数组的遍历，直到找到需要查找的那个整数
    function Find(target, array)
    {
        // write code here
        var arrLen = array.length
        var arrChildLen = array[0].length
        for (let i = 0; i < arrLen; i++) {
            for (let j = 0; j < arrChildLen; j++) {
                if (array[i][j] === target) {
                    return true
                }
            }
        }
        return false
    }

// 方式二：
    // 解题思路：以二维数组的左下角这个值开始和需要查找的整数比较，比整数大则行下标减一，比整数小则列下标加一，直至找到退出
    function Find(target, array)
    {
        // write code here
        var arrLen = array.length
        var arrChildLen = array[0].length
        var rowIndex = arrLen - 1
        var colIndex = 0
        
        while (rowIndex >= 0 && colIndex <= arrChildLen - 1) {
            if (array[rowIndex][colIndex] === target) {
                return true
            } else if (array[rowIndex][colIndex] > target) {
                rowIndex -= 1
            } else {
                colIndex += 1
            }
        }
        return false
    }

###### 2 字符串的空格替换 ######

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

方法一（正则）：
    function replaceSpace(str)
    {
        // write code here
        var r = /\s/g
        // 或 var r = new RegExp('\\s','g')
        var newStr = str.replace(r, '%20')
        return newStr
    }

// 方法二： 数组和字符串转换
    function replaceSpace(str)
    {
        // write code here
        var arr = str.split(' ')
        var newStr = arr.join('%20')
        return newStr
    }

###### 3 链表的遍历输出 ######

题目描述:  
输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

/*function ListNode(x){
        this.val = x;
        this.next = null;
    }*/
    // 将链表的值从头到尾依次压入从前面压入数组
    function printListFromTailToHead(head)
    {
        // write code here
        var node = head
        var arrList = []
        while (node != null) {
            arrList.unshift(node.val)
            node = node.next
        }
        return arrList
    }

###### 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)
    {
        // write code here
        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)
        }
    }

###### 5 两个栈实现队列 ######

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

// 第一个数组做入栈，第二个数组做出栈（第一个数组中的元素pop出的是最后入栈的，第二个数组在压入第一个pop出的，最后再pop的时候就是最开始压入第一个数组的元素）这样即实现了先入先出
    function push(node)
    {
        // write code here
        inStack.push(node)
    }
    function pop()
    {
        // write code here
        if (outStack.length === 0) {
            while (inStack.length) {
                outStack.push(inStack.pop())
            }
        }
        return outStack.pop()
    }
    var inStack = []
    var outStack = []

###### 6 查找最小值 ######

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

// 方法一：
    // 二分查找的思想找到最大和最小分界的地方
    function minNumberInRotateArray(rotateArray)
    {
        // write code here
        var left = 0
        var right = rotateArray.length - 1
        while (right - left > 1) {
            var mid = Math.floor((left + right) / 2)
            if (rotateArray[mid] > rotateArray[right]) {
                left = mid
            } else {
                right = mid
            }
        }
        return Math.min(rotateArray[left],rotateArray[right])
    }

// 方法二：
    // 不用算法思想，直接将数组排序，取出最小的数
    function minNumberInRotateArray(rotateArray)
    {
        // write code here
        return rotateArray.sort((a, b) => a - b)[0]
    }

###### 7 斐波那契数列 ######

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

// 使用动态规划的算法思想
    function Fibonacci(n)
    {
        // write code here
        let a = 0
        let b = 1
        while (n > 0) {
            b += a
            a = b - a
            n--
        }
        return a
    }

###### 8 青蛙跳 ######

题目描述:  
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

// 斐波那契数列的变形
    function jumpFloor(number)
    {
        // write code here
        let a = 1
        let b = 2
        while (--number) {
            b = a + b
            a = b - a
        }
        return a
    }

###### 9 超级青蛙跳 ######

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

// 青蛙跳的变形
    // 其中n级台阶为 a[n] = a[n-1] + a[n-2] + ... + a[1]
    //             a[n-1] = a[n-2] + ... + a[1]
    // 则两式相减 a[n] = 2*a[n-1] 从而得知上n级台阶是n-1级跳法的2倍
    function jumpFloorII(number)
    {
        // write code here
        let i = 1
        while (--number) {
            i *= 2
        }
        return i
    }

###### 10 矩阵覆盖 ######

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

// 斐波那契的变形
    function rectCover(number)
    {
        // write code here
        if (number === 0 ) return 0
        let x = 1
        let y = 2
        while (--number) {
            y += x
            x = y - x
        }
        return x
    }

###### 11 二进制1的个数 ######

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

// 法一
    // 二进制的数当自己与自己-1 相与，则会将最右边的1变为0，直到循环至最左边的1
    function NumberOf1(n)
    {
        // write code here
        let count = 0
        while (n) {
            n = n & n - 1
            count++
        }
        return count
    }

// 法二
    // 使用32位二进制表示的1111 1111 1111 1111左移位并依次与传入的二进制数相与，直到相与之后为0，则表示1的个数
    function NumberOf1(n)
    {
        // write code here
        let count = 0
        let flag = 1
        while (flag) {
            if (flag & n) count++
            flag = flag << 1
        }
        return count
    }

###### 12 次方求解 ######

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

保证base和exponent不同时为0

// 法一：（估计面试的时候这样写就没了！）
    function Power(base, exponent)
    {
        // write code here
        return Math.pow(base, exponent)
    }

// 法二：（快速幂求解）
    function Power(base, exponent)
    {
        // write code here
        let res = 1
        let n
        if (exponent > 0) {
            n = exponent
        } else if (exponent < 0) {
            if (base === 0) return -1
            n = -exponent
        } else {
            return 1
        }
        while (n) {
            if (n & 1) {
                res *= base
            }
            base *= base
            n >>= 1
        }
        return exponent > 0 ? res : 1 / res
    }

###### 13 调整数组顺序使奇数位于偶数前面 ######

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

// 方法一：
    // 定义奇偶两个数组以此判断并存入相应数组，最后将两个数组连接起来
    function reOrderArray(array)
    {
        // write code here
        var jiArr = []
        var ouArr = []
        for (let i = 0; i < array.length; i++) {
            if (array[i] & 1) {
                jiArr.push(array[i])
            } else {
                ouArr.push(array[i])
            }
        }
        return jiArr.concat(ouArr)
    }

// 方法二：
    // 使用filter过滤
    function reOrderArray(array)
    {
        // write code here
        var jiArr = array.filter(x => x & 1)
        var ouArr = array.filter(x => !(x & 1))
        return jiArr.concat(ouArr)
    }

###### 14 链表中倒数第k个结点 ######

题目描述:  
输入一个链表，输出该链表中倒数第k个结点。

// 方法一：
    // 将链表元素用unshift()存入数组，使后面的链表元素存在数组前面
    /*function ListNode(x){
        this.val = x;
        this.next = null;
    }*/
    function FindKthToTail(head, k)
    {
        // write code here
        var arr = []
        var node = head
        while (node) {
            arr.unshift(node)
            node = node.next
        }
        return arr[k-1]
    }

// 方法二：
    //  用两个指针来跑，两个指针中间相距k-1个节点,第一个指针先跑，跑到了第k个节点时，第二个指针则是第一个节点。这时候两个一起跑。当第一个跑到了最后一个节点时，这时候第二个指针则是倒数第k个节点。
    /*function ListNode(x){
        this.val = x;
        this.next = null;
    }*/
    function FindKthToTail(head, k)
    {
        // write code here
        let node1 = head,
            node2 = head
        while (k--) {
            if (node1) {
                node1 = node1.next
            } else {
                return null
            }
        }
        while (node1) {
            node1 = node1.next
            node2 = node2.next
        }
        return node2
    }

###### 15 反转链表 ######

题目描述:  
输入一个链表，反转链表后，输出新链表的表头。

// 方法一：
    // unshift存入数组并改变链表指针反向，输出第一个值
    /*function ListNode(x){
        this.val = x;
        this.next = null;
    }*/
    function ReverseList(pHead)
    {
        // write code here
        var node = pHead,
            arr = []
        while (node) {
            arr.unshift(node)
            node = node.next
        }
        arr.forEach((el, index) => {
            if (index !== arr.length - 1) {
                el.next = arr[index + 1]
            } else {
                el.next = null
            }
        })
        return arr[0]
    }

// 方法二：  
// 用三个指针pPre（指向前一个结点）、pCurrent（指向当前的结点，在代码中就是pHead）、pPnext（指向后一个结点）。将当前节点pHead的next指向前一个节点pPre，前一个节点pPre等于当前节点pHead，当前节点pHead等于下一个节点pNext（相当于将前后指针互换）

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

###### 16 合并两个排序的链表 ######

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

// 方法一：
    // 还是使用数组的方法排序并连接链表指针
    /*function ListNode(x){
        this.val = x;
        this.next = null;
    }*/
    function Merge(pHead1, pHead2)
    {
        // write code here
        var arr = []
        while (pHead1) {
            arr.push(pHead1)
            pHead1 = pHead1.next
        }
        while (pHead2) {
            arr.push(pHead2)
            pHead2 = pHead2.next
        }
        arr.sort((x, y) => x.val - y.val)
        arr.forEach((node,index) => {
            if (index !== arr.length - 1) {
                node.next = arr[index + 1]
            } else {
                node.next = null
            }
        })
        return arr[0]
    }

// 方法二：
    // 不断地比较他们的头结点，谁大将谁取出到新链表表头(也有两种：递归和非递归)
    // 递归
    /*function ListNode(x){
        this.val = x;
        this.next = null;
    }*/
    function Merge(pHead1, pHead2)
    {
        // write code here
        let newHead = null
        if (pHead1 === null) return pHead2
        if (pHead2 === null) return pHead1
        if (pHead1.val < pHead2.val) {
            newHead = pHead1
            newHead.next = Merge(pHead1.next, pHead2)
        } else {
            newHead = pHead2
            newHead.next = Merge(pHead1, pHead2.next)
        }
        return newHead
    }
    
    // 非递归
    /*function ListNode(x){
        this.val = x;
        this.next = null;
    }*/
    function Merge(pHead1, pHead2)
    {
        // write code here
        let newHead = null
        let newNode = null
        if (pHead1 === null) return pHead2
        if (pHead2 === null) return pHead1
        while (pHead1 && pHead2) {
            if (pHead1.val < pHead2.val) {
                if (newNode) {
                    newHead.next = pHead1
                    newHead = newHead.next
                } else {
                    newNode = newHead = pHead1
                }
                pHead1 = pHead1.next
            } else {
                if (newNode) {
                    newHead.next = pHead2
                    newHead = newHead.next
                } else {
                    newNode = newHead = pHead2
                }
                pHead2 = pHead2.next
            }
        }
        while (pHead1 !== null) {
            newHead.next = pHead1
            newHead = newHead.next
            pHead1 = pHead1.next
        }
        while (pHead2 !== null) {
            newHead.next = pHead2
            newHead = newHead.next
            pHead2 = pHead2.next
        }
        return newNode
    }

###### 17 树的子结构 ######

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

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

###### 18 二叉树的镜像 ######

题目描述:  
操作给定的二叉树，将其变换为源二叉树的镜像。

// 递归到叶子节点后逐层交换节点的值
    /* function TreeNode(x) {
        this.val = x;
        this.left = null;
        this.right = null;
    } */
    function Mirror(root)
    {
        // write code here
        if (root !== null) {
            Mirror(root.left)
            Mirror(root.right)
        } else {
            return
        }
        [root.left, root.right] = [root.right, root.left]
        return root
    }

###### 19 顺时针打印矩阵 ######

题目描述:  
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 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.

// 模拟魔方逆时针解法。
    // 例如 
    // 1 2 3
    // 4 5 6
    // 7 8 9
    // 输出并删除第一行后，再进行一次逆时针旋转，就变成：
    // 6 9 
    // 5 8
    // 4 7
    // 继续重复上述操作即可
    (即定义一个翻转矩阵的函数再重复去掉第一行)
    function printMatrix(matrix)
    {
        // write code here
        var list = [...matrix.shift()]
        while (matrix.length) {
            matrix = rotateMatrix(matrix)
            list = list.concat(matrix.shift())
        }
        return list
    }
    function rotateMatrix (matrix) {
        if (!matrix[0]) {
            return matrix
        }
        rowLen = matrix[0].length
        colLen = matrix.length
        let newMatrix = []
        for (let i = rowLen - 1; i >= 0 ; i--) {
            let newArr = []
            for (let j = 0; j < colLen; j++) {
                newArr.push(matrix[j][i])
            }
            newMatrix.push(newArr)
        }
        return newMatrix
    }

// 方法二：
    // 分解一下步骤是从左到右，从上到下，从右到左，从下到上。不过要注意下边界条件，也就是最后一圈构成不了一个完整的圈的一些条件。
    // 需要思考从第一圈到第二圈的条件是什么或者说他们有什么共同的特征。我们注意4X4的矩阵，只有两圈，到从第一圈到第二圈，起点从（0,0）变为了（1,1），我们发现4>1*2,类似的对于一个5X5的矩阵而言，最后一圈只有一个数字，起点坐标为（2,2），满足5>2*2,同理对于6X6的矩阵也是类似。故可以得出循环的条件就是columns>startX*2并且rows>startY*2
    function printMatrix(matrix) {
      if (matrix === null) return null;
      const rows = matrix.length,
        cols = matrix[0].length;
      let start = 0,
        res = [];
      while (rows > start * 2 && cols > start * 2) {
        res = res.concat(printMatrixInCircle(matrix, rows, cols, start));
        start++;
      }
      return res;
    }
    function printMatrixInCircle(matrix, rows, cols, start) {
      const endX = cols - 1 - start,
        endY = rows - 1 - start,
        res = [];
      for (let i = start; i <= endX; i++) {
        res.push(matrix[start][i]);
      }
      for (let i = start + 1; i <= endY; i++) {
        res.push(matrix[i][endX]);
      }
      for (let i = endX - 1; i >= start && endY > start; i--) {
        res.push(matrix[endY][i]);
      }
      for (let i = endY - 1; i >= start + 1 && endX > start; i--) {
        res.push(matrix[i][start]);
      }
      return res;
    }

###### 20 包含min函数的栈 ######

题目描述:  
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

// 增加一个辅助栈，每次压入栈时，和辅助栈栈顶值比较，小则压入辅助栈当中，大则再次压入辅助栈栈顶的值。这样辅助栈的栈顶数据一直是数据栈中最小的值。
    var stack = []
    var minstack = []
    function push(node)
    {
        // write code here
        stack.unshift(node)
        if (minstack.length === 0) {
            minstack.unshift(node)
        } else {
            if (minstack[0] > stack[0]) {
                minstack.unshift(node)
            } else {
                minstack.unshift(minstack[0])
            }
        }
    }
    function pop()
    {
        // write code here
        stack.shift()
        minstack.shift()
    }
    function top()
    {
        // write code here
        return stack[0]
    }
    function min()
    {
        // write code here
        return minstack[0]
    }

###### 21 栈的压入、弹出序列 ######

题目描述:  
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

// 使用一个辅助栈，先将pushV中的值依次压入辅助栈，在压入后将压入的值比对popV中的值，若有则弹出此时压入的值，并继续比较popV中的下一个值在辅助栈中是否还有，有则继续弹出辅助栈，直到比对到最后，若辅助栈为空，则是该压栈序列的弹出序列，反之亦然
    function IsPopOrder(pushV, popV)
    {
        // write code here
        let stack = []
        if (pushV.length === 0) return false
        for (let i = 0, j = 0; i < pushV.length; i++) {
            stack.push(pushV[i])
            while (j < popV.length && stack[stack.length - 1] === popV[j]) {
                stack.pop()
                j++
            }
        }
        if (stack.length === 0) {
            return true
        } else {
            return false
        }
    }

###### 22 从上往下打印二叉树（层序遍历） ######

题目描述：  
从上往下打印出二叉树的每个节点，同层节点从左至右打印。

// 二叉树的层序遍历，使用队列来帮助实现
    /* function TreeNode(x) {
        this.val = x;
        this.left = null;
        this.right = null;
    } */
    function PrintFromTopToBottom(root)
    {
        // write code here
        var queue = []
        var result = []
        if (root === null) {
            return result
        }
        queue.unshift(root)
        while (queue.length) {
            const pRoot = queue.pop()
            if (pRoot.left !== null) {
                queue.unshift(pRoot.left)
            }
            if (pRoot.right !== null) {
                queue.unshift(pRoot.right)
            }
            result.push(pRoot.val)
        }
        return result
    }

###### 23 二叉搜索树的后序遍历序列 ######

题目描述：  
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

// 二叉搜索树：左子节点小于父节点，右子节点大于父节点
    // 方法一：递归实现，判断数组最右边的值（即父节点）是否大于左子树，小于又子树
    function VerifySquenceOfBST(sequence)
    {
        // write code here
        if (sequence.length === 0) return false
        return judgeBitTree(sequence, 0, sequence.length - 1)
    }
    function judgeBitTree (arr, left, right) {
        if (left > right) return true
        let i = right
        while (arr[i - 1] > arr[right] && i > left) {
            i--
        }
        for (let j = i - 1; j >= left; j--) {
            if (arr[j] > arr[right]) {
                return false
            }
        }
        return judgeBitTree(arr, left + 1, right) && judgeBitTree(arr, left, right - 1)
    }

// 方法二： 非递归实现，思路和递归差不多,定义了i从头开始和最后一个值比较，如果中间的值不对，则i最终比maxIndex小。
    function VerifySquenceOfBST(sequence)
    {
        // write code here
        let maxIndex = sequence.length
        if (maxIndex === 0) return false
        while (maxIndex--) {
            let i = 0
            while (sequence[i] < sequence[maxIndex]) i++
            while (sequence[i] > sequence[maxIndex]) i++
            if (i < maxIndex) return false
        }
        return true
    }

###### 24 二叉树中和为某一值的路径 ######

题目描述：  
输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

// 深度优先遍历思想，将沿途的值相加若等于传入的整数，则此条路通，放入listAll
    /* function TreeNode(x) {
        this.val = x;
        this.left = null;
        this.right = null;
    } */
    function FindPath(root, expectNumber)
    {
        // write code here
        let list = []
        let listAll = []
        return dfs(root, expectNumber, list, listAll)
    }
    function dfs (root, expectNumber, list, listAll) {
        if (root === null) return listAll
        list.push(root.val)
        expectNumber -= root.val
        if (expectNumber === 0 && root.left === null && root.right === null) {
            listAll.push(Array.of(...list))
        }
        dfs(root.left, expectNumber, list ,listAll)
        dfs(root.right, expectNumber, list ,listAll)
        list.pop()
        return listAll
    }

###### 25 复杂链表的复制 ######

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

// 用map来保存<N，N`>，这样就很容易设置p.random了，比如我们在节点S处和节点S`处，我们通过S可以得到N，那么<N，N`>对应，就可以就可以使得S`的next指向N`了。这是通过空间换时间
    function RandomListNode(x){
        this.label = x;
        this.next = null;
        this.random = null;
    }
    function Clone(pHead)
    {
        // write code here
        if (pHead === null) return null
        const map = new Map()
        var p1 = pHead
        var p2 = new RandomListNode(pHead.label)
        var pHead2 = p2
        while (p1) {
            if (p1.next) p2.next = new RandomListNode(p1.next.label)
            else p2.next = null
            if (p1.random) p2.random = new RandomListNode(p1.random.label)
            else p2.random = null
            p1 = p1.next
            p2 = p2.next
        }
        return pHead2
    }

###### 26 二叉搜索树与双向链表 ######

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

// 方法一：（非递归）
    // 核心是中序遍历的非递归算法。
    // 修改当前遍历节点与前一遍历节点的指针指向。
    /* function TreeNode(x) {
        this.val = x;
        this.left = null;
        this.right = null;
    } */
    function Convert(pRootOfTree)
    {
        // write code here
        if (!pRootOfTree) return null
        let stack = [],
            p = pRootOfTree,
            pre = null,
            isFirst = true
        while (p || stack.length) {
            while (p) {
                stack.push(p)
                p = p.left
            }
            p = stack.pop()
            if (isFirst) {
                pRootOfTree = p
                pre = pRootOfTree
                isFirst = false
            } else {
                pre.right = p
                p.left = pre
                pre = p
            }
            p = p.right
        }
        return pRootOfTree
    }

// 方法二：（递归）
    // 先对左子数调整为双向链表，并用变量pLast指向最后一个节点
    // 再将中间节点和pLast连起来
    // 再去调整右子树
     /* function TreeNode(x) {
        this.val = x;
        this.left = null;
        this.right = null;
    } */
    function Convert(pRootOfTree)
    {
        // write code here
        if (!pRootOfTree) return null
        let pLast = null
        pLast = convertNode(pRootOfTree, pLast)
        let pHead = pLast
        while (pHead && pHead.left) {
            pHead = pHead.left
        }
        return pHead
    }
    function convertNode (pNode, pLast) {
        if (!pNode) return
        if (pNode.left) {
            pLast = convertNode(pNode.left, pLast)
        }
        pNode.left = pLast
        if (pLast) {
            pLast.right = pNode
        }
        pLast = pNode
        if (pNode.right) {
            pLast = convertNode(pNode.right, pLast)
        }
        return pLast
    }

###### 27 字符串的排列 ######

题目描述:  
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。  
*输入描述:  
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。*

// 方法一：（递归）
    // 把字符串分为两部分：第一部分为第一个字符，第二部分为第一个字符以后的字符串。
    // 然后接下来求后面那部分的全排列。
    // 再将第一个字符与后面的那部分字符逐个交换
    function Permutation(str) {
      let res = [];
      if (str.length <= 0) return res;
      arr = str.split(''); // 将字符串转化为字符数组
      res = permutate(arr, 0, res);
      res = [...new Set(res)]; // 去重
      res.sort(); // 排序
      return res;
    }
    function permutate(arr, index, res) {
      if (arr.length === index) {
        let s = '';
        for (let i = 0; i < arr.length; i++) {
          s += arr[i];
        }
        return res.push(s);
      }
      for (let i = index; i < arr.length; i++) {
        [arr[index], arr[i]] = [arr[i], arr[index]]; // 交换
        permutate(arr, index + 1, res);
        [arr[index], arr[i]] = [arr[i], arr[index]]; // 交换
      }
    
      return res;
    }

// 方法二：回溯法
    //利用树去尝试不同的可能性，不断地去字符串数组里面拿一个字符出来拼接字符串，当字符串数组被拿空时，就把结果添加进结果数组里，然后回溯上一层。（通过往数组加回去字符以及拼接的字符串减少一个来回溯。）
    function Permutation(str) {
      let res = [];
      const pStr = '';
      if (str.length <= 0) return res;
      arr = str.split(''); // 将字符串转化为字符数组
      res = permutate(arr, pStr, res);
      return res;
    }
    function permutate(arr, pStr, res) {
      if (arr.length === 0) {
        return res.push(pStr);
      }
      const isRepeated = new Set();
      for (let i = 0; i < arr.length; i++) {
        if (!isRepeated.has(arr[i])) {
          // 避免相同的字符交换
          const char = arr.splice(i, 1)[0];
          pStr += char;
          permutate(arr, pStr, res);
          arr.splice(i, 0, char); // 恢复字符串，回溯
          pStr = pStr.slice(0, pStr.length - 1); // 回溯
          isRepeated.add(char);
        }
      }
      return res;
    }

// 方法3：用字符串的每个字符插入字符串的前中后里
    function Permutation(str) { 
        if (str.length === 0) return []
        var arr = [str[0]]
        for (let j = 1; j < str.length; j++) { 
            arr = fp(arr, str[j])
        }
        return [...new Set(arr)].sort()
    }
    
    function fp (arr, ch) { 
        var tmp = []
        for (let i = 0; i <= arr[0].length; i++) { 
            tmp = tmp.concat(arr.map(x => x.slice(0, i) + ch + x.slice(i)))
        }
        return [...new Set(tmp)]
    }

###### 28 数组中出现次数超过一半的数字 ######

题目描述:  
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组\{1,2,3,2,2,2,5,4,2\}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

// 准备一个辅助数组等于传入的数组，将传入数组的每个值在辅助数组中查找，查找到则次数+1，直到其出现的次数大于数组的一半时，则返回此值
    function MoreThanHalfNum_Solution(numbers)
    {
        // write code here
        let arr = [...numbers]
        for (let i = 0; i < numbers.length; i++) {
            let  count = 0
            for (let j = 0; j < arr.length; j++) {
                if (arr.indexOf(numbers[i]) !== -1) {
                    arr.splice(arr.indexOf(numbers[i]), 1)
                    count++
                }
            }
            arr = [...numbers]
            if (count > Math.floor(numbers.length / 2)) {
                return numbers[i]
            }
        }
        return 0
    }

###### 29 最小的K个数 ######

题目描述:  
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

// 方法一：
    // 非算法题思想--!
    function GetLeastNumbers_Solution(input, k)
    {
        // write code here
        if (k > input.length) return []
        return input.sort((a, b) => a - b).splice(0, k)
    }

// 方法二：
    // 基于partition快排的思想来查找第k大的数
    function GetLeastNumbers_Solution(input, k) {
      if (input.length === 0 || k > input.length || k < 1) return [];
      const left = 0,
        right = input.length - 1;
      let key = partition(input, left, right);
      while (key !== k - 1) {
        if (key > k - 1) {
          key = partition(input, left, key - 1);
        } else {
          key = partition(input, key + 1, right);
        }
      }
      const res = input.slice(0, key + 1);
      res.sort((a, b) => a - b);
      return res;
    }
    function partition(a, left, right) {
      const key = a[left]; // 一开始让key为第一个数
      while (left < right) {
        // 扫描一遍
        while (key <= a[right] && left < right) {
          // 如果key小于a[right]，则right递减，继续比较
          right--;
        }
        [a[left], a[right]] = [a[right], a[left]]; // 交换
        while (key >= a[left] && left < right) {
          // 如果key大于a[left]，则left递增，继续比较
          left++;
        }
        [a[left], a[right]] = [a[right], a[left]]; // 交换
      }
      return left; // 把key现在所在的下标返回
    }

###### 30 连续子数组的最大和 ######

题目描述:  
HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:\{6,-3,-2,7,-15,1,2,2\},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)

> 动态规划思路  
> F（i）：以array\[i\]为末尾元素的子数组的和的最大值，子数组的元素的相对位置不变  
> F（i）=max（F（i-1）+array\[i\] ， array\[i\]）  
> res：所有子数组的和的最大值  
> res=max（res，F（i））  
> 如数组\[6, -3, -2, 7, -15, 1, 2, 2\]  
> 初始状态：  
> F（0）=6  
> res=6  
> i=1：  
> F（1）=max（F（0）-3，-3）=max（6-3，3）=3  
> res=max（F（1），res）=max（3，6）=6  
> i=2：  
> F（2）=max（F（1）-2，-2）=max（3-2，-2）=1  
> res=max（F（2），res）=max（1，6）=6  
> i=3：  
> F（3）=max（F（2）+7，7）=max（1+7，7）=8  
> res=max（F（2），res）=max（8，6）=8  
> i=4：  
> F（4）=max（F（3）-15，-15）=max（8-15，-15）=-7  
> res=max（F（4），res）=max（-7，8）=8  
> 以此类推  
> 最终res的值为8

// （动态规划解法）
    // 解析如上（两种写法）
    // 写法1 
    function FindGreatestSumOfSubArray(array)
    {
        // write code here
        let res = array[0],
            max = array[0]
        for (let i = 1; i < array.length; i++) {
            max = Math.max(max + array[i], array[i])
            res = Math.max(max, res)
        }
        return res
    }
    // 写法2
    function FindGreatestSumOfSubArray(array)
    {
        // write code here
        if (array.length === 0) return 0
        else {
            let res = array[0],
            max = array[0]
            for (let i = 1; i < array.length; i++) {
                if (max <= 0) {
                    max = array[i]
                } else {
                    max += array[i]
                }
                if (res < max) {
                    res = max
                }
            }
            return res
        }
    }

###### 31 整数中1出现的次数（从1到n整数中1出现的次数） ######

题目描述:  
求出113的整数中1出现的次数,并算出1001300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。

// 方法一： （正则匹配）
    function NumberOf1Between1AndN_Solution(n)
    {
        // write code here
        if (n < 1) return 0
        let str = ''
        for (let i = 1; i <= n; i++) {
            str += String(i)
        }
        let arrNum = str.match(/(1)/g)
        return arrNum.length
    }

// 方法二：
    // 暴力解法，也就是逐个判断
    function NumberOf1Between1AndN_Solution(n){
        let ones = 0
        for (let i = 0;i <= n; i++) {
            let num = i
            while (num) {
                if (num %10 === 1) {
                    ones++
                }
                num = ~~(num / 10)
            }
        }
        return ones
    }

> // 方法三主要思路：设定整数点（如1、10、100等等）作为位置点i（对应n的各位、十位、百位等等），分别对每个数位上有多少包含1的点进行分析  
> // 根据设定的整数位置，对n进行分割，分为两部分，高位n/i，低位n%i  
> // 当i表示百位，且百位对应的数>=2,如n=31456,i=100，则a=314,b=56，此时百位为1的次数有a/10+1=32（最高两位0~31），每一次都包含100个连续的点，即共有(a%10+1)*100个点的百位为1  
> // 当i表示百位，且百位对应的数为1，如n=31156,i=100，则a=311,b=56，此时百位对应的就是1，则共有a%10(最高两位0-30)次是包含100个连续点，当最高两位为31（即a=311），本次只对应局部点00~56，共b+1次，所有点加起来共有（a%10*100）+(b+1)，这些点百位对应为1  
> // 当i表示百位，且百位对应的数为0,如n=31056,i=100，则a=310,b=56，此时百位为1的次数有a/10=31（最高两位0~30）  
> // 综合以上三种情况，当百位对应0或>=2时，有(a+8)/10次包含所有100个点，还有当百位为1(a%101)，需要增加局部点b+1  
> // 之所以补8，是因为当百位为0，则a/10(a+8)/10，当百位>=2，补8会产生进位位，效果等同于(a/10+1)

// 方法三： 
    // 运用了根据位数来做，逐位求解，并且对于特殊情况做下判断。
    // 主要注意下每位0,1，>2三种情况。并且通过+8处理可以很好地把>2情况归在一起。
    
    function NumberOf1Between1AndN_Solution(n){
        if(n <=0 ) return 0
        let count = 0
        for (let i = 1; i <= n; i *= 10) {
            let a = ~~(n / i),b = n % i
            count = count + ~~((a + 8) / 10) * i + (a % 10 === 1) * (b + 1)
        }
        return count
    }

###### 32 把数组排成最小的数 ######

题目描述:  
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组\{3，32，321\}，则打印出这三个数字能排成的最小数字为321323。

// 比较数组每个元素的字典序
    function PrintMinNumber(numbers)
    {
        // write code here
        if (numbers.length === 0) return ''
        numbers.sort((a, b) => {
            let s1 = String(a) + String(b)
            let s2 = String(b) + String(a)
            return s1 - s2
        })
        return numbers.join('')
    }

###### 33 丑数 ######

题目描述：  
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

// 动态规划思想
    function GetUglyNumber_Solution(index)
    {
        // write code here
        if (index < 7) return index
        let t1 = 0,
            t2 = 0,
            t3 = 0
        let res = []
        res[0] = 1
        for (let i = 1; i < index; i++) {
            res[i] = Math.min(res[t1] * 2, Math.min(res[t2] * 3, res[t3] * 5))
            if (res[i] === res[t1] * 2) t1++
            if (res[i] === res[t2] * 3) t2++
            if (res[i] === res[t3] * 5) t3++
        }
        return res[index - 1]
    }

// 牛客网运行超时（暴力循环）
    function GetUglyNumber_Solution(index) {
      if (index <= 1) return 0;
      let count = 0;
      let num = 0;
      while (count < index) {
        num++;
        if (isUgly(num)) {
          count++;
        }
      }
      return num;
    }
    function isUgly(num) {
      while (num % 2 === 0) num /= 2;
      while (num % 3 === 0) num /= 3;
      while (num % 5 === 0) num /= 5;
      return num === 1;
    }

###### 34 第一个只出现一次的字符 ######

题目描述：  
在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.

// 方法一：
    // 正则匹配比较个数
    function FirstNotRepeatingChar(str)
    {
        // write code here
        for (let i = 0; i < str.length; i++) {
            let r = `/${str[i]}/g`
            let arr = str.match(eval(r))
            if (arr.length === 1) {
                return i
            }
        }
        return -1
    }

// 方法二：
    // 用Map()的结构来实现每个字符串对应的个数（用对象也可以）
    function FirstNotRepeatingChar(str)
    {
        // write code here
        let map = new Map()
        for (let i = 0; i < str.length; i++) {
            if (map.get(str[i]) === undefined) {
                map.set(str[i], 1)
            } else {
                let count = map.get(str[i])
                map.set(str[i], ++count)
            }
        }
        for (let i = 0; i < str.length; i++) {
            if (map.get(str[i]) === 1) {
                return i
            }
        }
        return -1
    }

###### 35 数组中的逆序对（难） ######

题目描述：  
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

> 输入描述: 题目保证输入的数组中没有的相同的数字  
> 数据范围：  
> 对于%50的数据,size<=10^4  
> 对于%75的数据,size<=10^5  
> 对于%100的数据,size<=2\*10^5  
> 示例1  
> 输入1,2,3,4,5,6,7,0  
> 输出7

// 第一反应是没思路，然后想到采用暴力解法,不过肯定会超时,所以我们需要用时间复杂度更低的解法.
    // 说实话这道题有点难，我也是参考別人的。那么难点在哪呢？
    // 难点一：要想到基于归并排序去解决。
    // 难点二：参数的问题，这里很巧妙地用了一个copy数组作为data参数。
    // 难点三：合并时，count如何计数。
    // 不过只要注意这些小细节,多花点时间想明白还是能做出来的.
    function InversePairs(data) {
      if (!data || data.length < 2) return 0;
      const copy = data.slice();
      let count = 0;
      count = mergeCount(data, copy, 0, data.length - 1);
      return count % 1000000007;
    }
    function mergeCount(data, copy, start, end) {
      if (start === end) return 0;
      const mid = end - start >> 1,
        left = mergeCount(copy, data, start, start + mid), // 注意参数，copy作为data传入
        right = mergeCount(copy, data, start + mid + 1, end); // 注意参数，copy作为data传入
      let [p, q, count, copyIndex] = [start + mid, end, 0, end];
      while (p >= start && q >= start + mid + 1) {
        if (data[p] > data[q]) {
          copy[copyIndex--] = data[p--];
          count = count + q - start - mid;
        } else {
          copy[copyIndex--] = data[q--];
        }
      }
      while (p >= start) {
        copy[copyIndex--] = data[p--];
      }
      while (q >= start + mid + 1) {
        copy[copyIndex--] = data[q--];
      }
      return count + left + right;
    }

###### 36 两个链表的第一个公共结点 ######

题目描述：  
输入两个链表，找出它们的第一个公共结点。

// 用两个指针扫描”两个链表“，最终两个指针到达 null 或者到达公共结点。
    /*function ListNode(x){
        this.val = x;
        this.next = null;
    }*/
    function FindFirstCommonNode(pHead1, pHead2)
    {
        // write code here
        let p1 = pHead1
        let p2 = pHead2
        while (p1 !== p2) {
            p1 = (p1 === null ? pHead2 : p1.next)
            p2 = (p2 === null ? pHead1 : p2.next)
        }
        return p1
    }

###### 37 数字在排序数组中出现的次数 ######

题目描述：  
统计一个数字在排序数组中出现的次数。

// 方法一：（循环依次判断个数）
    function GetNumberOfK(data, k)
    {
        // write code here
        let count = 0
        for (let i = 0; i < data.length; i++) {
            if (data[i] === k) {
                count++
            }
            if (data[i] > k) break
        }
        return count
    }

// 方法二：（二分查找法）
    function GetNumberOfK(data, k) {
      if (getEnd(data, k) === -1 && getBegin(data, k) === -1) return 0;
      return getEnd(data, k) - getBegin(data, k) + 1;
    }
    function getBegin(data, k) {
      let [left, right] = [0, data.length - 1];
      let mid = left + right >> 1;
      while (left <= right) {
        if (data[mid] > k) {
          right = mid - 1;
        } else if (data[mid] < k) {
          left = mid + 1;
        } else if (mid - 1 >= 0 && data[mid - 1] === k) {
          right = mid - 1;
        } else return mid;
        mid = left + right >> 1;
      }
      return -1;
    }
    function getEnd(data, k) {
      let [left, right] = [0, data.length - 1];
      let mid = left + right >> 1;
      while (left <= right) {
        if (data[mid] > k) {
          right = mid - 1;
        } else if (data[mid] < k) {
          left = mid + 1;
        } else if (mid + 1 < data.length && data[mid + 1] === k) {
          left = mid + 1;
        } else return mid;
        mid = left + right >> 1;
      }
      return -1;
    }

###### 38 二叉树的深度 ######

题目描述：  
输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

// 方法一：
    // 递归实现（层序遍历）
    /* function TreeNode(x) {
        this.val = x;
        this.left = null;
        this.right = null;
    } */
    function TreeDepth(pRoot)
    {
        // write code here
        if (pRoot === null) return 0
        let leftDeep = TreeDepth(pRoot.left) + 1
        let rightDeep = TreeDepth(pRoot.right) + 1
        return Math.max(leftDeep, rightDeep)
    }

// 方法二：
    // 队列实现
    /* function TreeNode(x) {
        this.val = x;
        this.left = null;
        this.right = null;
    } */
    function TreeDepth(pRoot)
    {
        // write code here
        if (pRoot === null) return 0
        let deep = 0,
            queue = []
        queue.unshift(pRoot)
        let count = 0,
            nextCount = 1
        while(queue.length) {
            let top = queue.pop()
            count++
            if (top.left) {
                queue.unshift(top.left)
            }
            if (top.right) {
                queue.unshift(top.right)
            }
            if (count === nextCount) {
                nextCount = queue.length
                count = 0
                deep++
            }
        }
        return deep
    }

###### 39 平衡二叉树 ######

题目描述：  
输入一棵二叉树，判断该二叉树是否是平衡二叉树。

// 结合二叉树深度的递归来判断是否为平衡二叉树
    // 平衡二叉树：是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树
    /* function TreeNode(x) {
        this.val = x;
        this.left = null;
        this.right = null;
    } */
    function IsBalanced_Solution(pRoot)
    {
        // write code here
        if (!pRoot) return true
        let leftDeep = treeDeep(pRoot.left)
        let rightDeep = treeDeep(pRoot.right)
        return Math.abs(leftDeep - rightDeep) <= 1 && IsBalanced_Solution(pRoot.left) && IsBalanced_Solution(pRoot.right)
    }
    function treeDeep (pRoot) {
        if (!pRoot) return 0
        let leftTree = treeDeep(pRoot.left)
        let rightTree = treeDeep(pRoot.right)
        return Math.max(leftTree, rightTree) + 1
    }
    
    // 但是这种做法有很明显的问题，在判断上层结点的时候，会多次重复遍历下层结点，增加了不必要的开销。如果改为从下往上遍历，如果子树是平衡二叉树，则返回子树的高度；如果发现子树不是平衡二叉树，则直接停止遍历，这样至多只对每个结点访问一次。
    
    function IsBalanced_Solution(pRoot) {
        return treeDeep(pRoot) !== -1;
    }
    function treeDeep(pRoot) {
        if (pRoot === null) return 0;
        const leftLen = treeDeep(pRoot.left);
        if (leftLen === -1) return -1;
        const rightLen = treeDeep(pRoot.right);
        if (rightLen === -1) return -1;
        return Math.abs(leftLen - rightLen) > 1 ? -1 : Math.max(leftLen, rightLen) + 1;
    }

###### 40 数组中只出现一次的数字 ######

题目描述:  
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

// 方法一：（暴力循环）
    // 循环将需要查找的数字从原数组中删除，然后在查找是否含有相同值，没有则只有一次
    function FindNumsAppearOnce(array)
    {
        // write code here
        if (!array.length) return null
        let arr = []
        for (let i = 0; i < array.length; i++) {
            let newA = [...array]
            newA.splice(i,1)
            if (newA.indexOf(array[i]) === -1) {
              arr.push(array[i])
            }
        }
        return arr
        // return list, 比如[a,b]，其中ab是出现一次的两个数字
    }
    // 更简洁的写法 （用indexOf和lastIndexOf判断是否相等得到）
    function FindNumsAppearOnce(array)
    {
        // write code here
        if (!array.length) return null
        let arr = []
        for (let i = 0; i < array.length; i++) {
            if (array.indexOf(array[i]) === array.lastIndexOf(array[i])) {
              arr.push(array[i])
            }
        }
        return arr
        // return list, 比如[a,b]，其中ab是出现一次的两个数字
    }

// 方法二：
    // 思路和第34题方法二相同，这次我使用对象来实现数组中每个值对应的个数
    function FindNumsAppearOnce(array)
    {
        // write code here
        if (!array.length) return null
        let arrObj = {}
        let list = []
        let len = array.length
        for (let i = 0; i < len; i++) {
            if (!arrObj[array[i]]) {
                arrObj[array[i]] = 1
            } else {
                arrObj[array[i]]++
            }
        }
        for (let i = 0; i < len; i++) {
            if (arrObj[array[i]] === 1) {
                list.push(array[i])
            }
        }
        return list
        // return list, 比如[a,b]，其中ab是出现一次的两个数字
    }

> **第三种方法**，根据异或结果中1所在的二进制位数，把数组中数分成两种不同类别，分别异或得出结果。  
> 位运算中异或的性质：**两个相同数字异或=0，一个数和0异或还是它本身。**  
> –  
> **当只有一个数出现一次时**，我们把数组中所有的数，依次异或运算，最后剩下的就是落单的数，因为成对儿出现的都抵消了。  
> 依照这个思路，我们来看两个数（我们假设是AB）出现一次的数组。我们首先还是先异或，剩下的数字肯定是A、B异或的结果，  
> **这个结果的二进制中的1，表现的是A和B的不同的位。**  
> 我们就取异或的结果中第一个1所在的位数，假设是第3位，接着把原数组分成两组，通过比较第3位是否为1来分成两组。  
> 如此，**相同的数肯定在一个组**，因为相同数字所有位都相同，而**不同的数，肯定不在一组。**  
> 然后把这两个组按照最开始的思路，依次异或，剩余的两个结果就是这两个只出现一次的数字。

// 方法三:
    function FindNumsAppearOnce3(array) {
      let tmp = array[0];
      for (let i = 1; i < array.length; i++) {
        tmp = tmp ^ array[i];
      }
      if (tmp === 0) return;
      let index = 0; // 记录第几位是1
      while ((tmp & 1) === 0) {
        tmp = tmp >> 1;
        index++;
      }
      let num1 = 0,
        num2 = 0;
      for (let i = 0; i < array.length; i++) {
        if (isOneAtIndex(array[i], index)) num1 = num1 ^ array[i];
        else num2 = num2 ^ array[i];
      }
      return [num1, num2];
    }
    function isOneAtIndex(num, index) {
      num = num >> index;
      return num & 1;
    }

###### 41 和为S的连续正数序列 ######

题目描述:  
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!

输出描述:  
输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序

// 方法一：
    // 双指针技术，就是相当于有一个窗口，窗口的左右两边就是两个指针，我们根据窗口内值之和来确定窗口的位置和宽度
    function FindContinuousSequence(sum)
    {
        // write code here
        // 两个起点，相当于动态窗口的两边，根据其窗口内的值的和来确定窗口的位置和大小
        let plow = 1,
            phigh = 2,
            // 存放结果
            result = []
        while(plow < phigh) {
            // 由于是连续的，差为1的一个序列，那么求和公式是(a0+an)*n/2
            let curSum = (plow + phigh) * (phigh - plow + 1) / 2
            // 相等，那么就将窗口范围的所有数添加进结果集
            if (curSum === sum) {
                let list = []
                for (let i = plow; i <= phigh; i++) {
                    list.push(i)
                }
                result.push(list)
            }
            // 如果当前窗口内的值之和小于sum，那么右边窗口右移一下
            if (curSum < sum) {
                phigh++
            } else {		// 如果当前窗口内的值之和大于sum，那么左边窗口右移一下
                plow++
            }
        }
        return result
    }

方法二：
    // 假设序列的开始数字为a,结束数字为a+i，那么有(a+i-a+1)*(a+a+i)/2=sum
    // 也就是(i+1)*(2*a+i)=2*sum
    // 那么我们只需要找出这样的a和i就行了，最后再根据a和i得出序列。
    function FindContinuousSequence(sum) {
      let a = 0,
        half = sum >> 1;
      const res = [];
      while (half--) {
        a++;
        let i = 1;
        while ((i + 1) * (2 * a + i) < 2 * sum) {
          i++;
        }
        if ((i + 1) * (2 * a + i) === 2 * sum) {
          const tmp = [];
          tmp.push(a);
          tmp.push(i);
          res.push(tmp);
        }
      }
      for (let i = 0; i < res.length; i++) {
        let num = res[i][1],
          k = 1;
        const tmp = [];
        tmp.push(res[i][0]);
        while (num--) {
          tmp.push(res[i][0] + k);
          k++;
        }
        res[i] = tmp;
      }
      return res;
    }

###### 42 和为S的两个数字 ######

题目描述：  
输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

输出描述:  
对应每个测试案例，输出两个数，小的先输出。

// 依旧使用双指针做。此外相距最远，乘积最小。(思路和上题类似)
    // 注：因为相距最远乘积最小，所以我们从两头往中间夹窗口，永远是最远的两个数，所以不用多判断乘积的情况
    function FindNumbersWithSum(array, sum)
    {
        // write code here
        let plow = 0,
            phigh = array.length - 1
        while (phigh > plow) {
            if (array[plow] + array[phigh] === sum) {
                return [array[plow], array[phigh]]
            } else if (array[plow] + array[phigh] < sum) {
                plow++
            } else {
                phigh--
            }
        }
        return -1
    }

###### 43 左旋转字符串 ######

题目描述：  
汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！

// 方法一：
    // 数组方法splice()和concat()配合使用实现左移效果
    function LeftRotateString(str, n)
    {
        // write code here
        if (!str) return ''
        let arr = str.split('')
        let leftArr = arr.splice(0, n)
        str = arr.concat(leftArr).join('')
        return str
    }
    // 不转换为数组使用string的slice方法
    function LeftRotateString(str, n) {
      if (str === null || str.length === 0) return ''
      return str.slice(n) + str.slice(0, n)
    }

// 方法二：（牛客网运行超内存，本地编辑器运行可以）
    // 原理：YX = (XTY T)T
    function LeftRotateString(str, n) {
      if (!str.length) return ''
      let len = str.length
      for(let i = 0, j = n - 1; i < j; ++i, --j) str = swapStr(str, i, j)
      for(let i = n, j = len - 1; i < j; ++i, --j) str = swapStr(str, i, j)
      for(let i = 0, j = len - 1; i < j; ++i, --j) str = swapStr(str, i, j)
      return str
    }
    function swapStr(str, i, j) {
      let arr = str.split('')
      let temp = arr[i]
      arr[i] = arr[j]
      arr[j] = temp
      str = arr.join('')
      return str
    }

###### 44 翻转单词顺序列 ######

题目描述:  
牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？

// 方法一：
    // 使用数组方法
    function ReverseSentence(str)
    {
        // write code here
        let arr = str.split(' ')
        str = arr.reverse().join(' ')
        return str
    }

// 方法二
    // 不借助数组的方法，使用栈来实现
    function ReverseSentence(str)
    {
        // write code here
        let stack = []
        let newStr = ''
        for (let i = 0; i < str.length; i++) {
            if (str[i] !== ' ') {
                newStr += str[i]
            } else {
                stack.unshift(newStr)
                newStr = ''
            }
        }
        stack.unshift(newStr)
        newStr = ''
        for (let i = 0; i < stack.length; i++) {
            if (i === 0) {
                newStr += stack[i]
            } else {
                newStr += ' ' + stack[i]
            }
        }
        return newStr
    }

###### 45 扑克牌顺子 ######

题目描述：  
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的运气如何， 如果牌能组成顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。

// 细点：按&运算判断奇偶，左移<<扩大，右移>>缩小
    // 满足以下两个条件：
    // 1.最大和最小之差不超过5。
    // 2.这5个数当中不能有重复的数字。
    // 而以下的代码就是根据这两个条件来展开写的。
    // 其中利用了位运算的技巧来判断是否有数字重复。
    function IsContinuous(numbers)
    {
        // write code here
        let max = 0,
        min = 14,
        flag = 0
      if (numbers.length !== 5) return false
      for (let i = 0; i < numbers.length; i++) {
        if (numbers[i] > 13 || numbers[i] < 0) return false
        if (numbers[i] === 0) continue
        if ((flag >> numbers[i] & 1) === 1) return false
        flag = flag | 1 << numbers[i]
        if (numbers[i] > max) max = numbers[i]
        if (numbers[i] < min) min = numbers[i]
      }
      if (max - min >= 5) return false
      return true
    }

###### 46 孩子们的游戏(圆圈中最后剩下的数) ######

题目描述:  
每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数…这样下去…直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!\_)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)

如果没有小朋友，请返回-1

// 方法一：
    // 用数组来模拟圆环，思路还是比较简单，但是各种下标要理清
    function LastRemaining_Solution(n, m)
    {
        // write code here
        if (!n) return -1
        let arrChild = Array(n).fill(1),
            step = 0,
            i = -1,
            num = n
        while (num > 0) { // 跳出循环时将最后一个元素也设置为了-1
            i++
            if (i >= n) i = 0  // 模拟环
            if (arrChild[i] === -1) continue  // 跳过被删除的对象。
            step++  // 记录已走过的。
            if (step === m) {  // 找到待删除的对象。
                arrChild[i] = -1
                step = 0
                num--
            }
        }
        return i  // 返回跳出循环时的i,即最后一个被设置为-1的元素
    }

// 方法二：（牛客网运行超时）
    // 先将孩子编号存入数组，依次循环删除第m-1个孩子（此时下标容易出错，所以用del来记录下标）
    function LastRemainingSolution(n, m) {
      if (n === 0 || m === 0) return -1;
      const child = [];
      let del = 0;
      for (let i = 0; i < n; i++) {
        child[i] = i;
      }
      while (child.length > 1) {
        const k = m - 1;
        del = (del + k) % child.length;
        child.splice(del, 1);
      }
      return child[0];
    }

> 方法三思路：  
> 如果只求最后一个报数胜利者的话，我们可以用数学归纳法解决该问题，为了讨论方便，先把问题稍微改变一下，并不影响原意：
> 
> 问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人 继续从0开始报数。求胜利者的编号。
> 
> 我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）:
> 
> k k+1 k+2 … n-2, n-1, 0, 1, 2, … k-2并且从k开始报0。
> 
> 现在我们把他们的编号做一下转换：
> 
> k --> 0
> 
> k+1 --> 1
> 
> k+2 --> 2
> 
> …
> 
> …
> 
> k-2 --> n-2
> 
> k-1 --> n-1
> 
> 变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：  
> 例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情  
> 况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x’=(x+k)%n。
> 
> 令f\[i\]表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f\[n\]。
> 
> 递推公式
> 
> f\[1\]=0;
> 
> f\[i\]=(f\[i-1\]+m)%i; (i>1)
> 
> 有了这个公式，我们要做的就是从1-n顺序算出f\[i\]的数值，最后结果是f\[n\]。 因为实际生活中编号总是从1开始，我们输出f\[n\]+1。

// 方法三：（约瑟夫环公式）
    // 由上分析使用递归实现
    function LastRemaining_Solution(n, m) {
        if(n==0)
            return -1
        if(n==1)
            return 0
        else
            return (LastRemaining_Solution(n - 1, m) + m) % n
    }

###### 47 求1+2+3+…+n ######

题目描述：  
求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

// 方法一：
    // 递归短路求值，即&&前面如果判断为假则不执行后面的语句
    function Sum_Solution(n)
    {
        // write code here
        let sum = n
        sum && (sum += Sum_Solution(n - 1))
        return sum
    }

// 方法二：
    // 因为这种计算公式为n*(n+1)/2借助Math.pow()来实现n*(n+1)用>>来实现/
    function Sum_Solution(n)
    {
        // write code here
        return (Math.pow(n, 2) + n) >> 1
    }

###### 48 不用加减乘除做加法 ######

题目描述：  
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、\*、/四则运算符号。

> 首先看十进制是如何做的： 5+7=12，三步走 第一步：相加各位的值，不算进位，得到2。 第二步：计算进位值，得到10.  
> 如果这一步的进位值为0，那么第一步得到的值就是最终结果。
> 
> 第三步：重复上述两步，只是相加的值变成上述两步的得到的结果2和10，得到12。
> 
> 同样我们可以用三步走的方式计算二进制值相加： 5-101，7-111  
> 第一步：相加各位的值，不算进位，得到010，二进制每位相加就相当于各位做异或操作，101^111。
> 
> 第二步：计算进位值，得到1010，相当于各位做与操作得到101，再向左移一位得到1010，(101&111)<<1。
> 
> 第三步重复上述两步， 各位相加 010^1010=1000，进位值为100=(010&1010)<<1。  
> 继续重复上述两步：1000^100 = 1100，进位值为0，跳出循环，1100为最终结果。

// 解析如上：
    function Add(num1, num2)
    {
        // write code here
        while (num2) {
            let res = num1 ^ num2
            num2 = (num1 & num2) << 1
            num1 = res
        }
        return num1
    }

###### 49 把字符串转换成整数 ######

题目描述：  
将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能，但是string不符合数字要求时返回0)，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。

输入描述:  
输入一个字符串,包括数字字母符号,可以为空

输出描述:  
如果是合法的数值表达则返回该数字，否则返回0

> 示例1  
> 输入：  
> \+2147483647  
> 1a33  
> 输出 ：  
> 2147483647  
> 0

// 方法一：
    // 将保存的数按位放大，即乘以10的第几位次方然后相加每个数
    function StrToInt(str)
    {
        // write code here
        if (str.length === 0) return 0
        let arr = str.split('')
        let sum = 0
        let j = arr[0] === '+' || arr[0] === '-' ? arr.length - 2 : arr.length - 1
        for (let i = arr[0] === '+' || arr[0] === '-' ? 1 : 0; i < arr.length; i++) {
            arr[i] = arr[i] * 1
            sum += arr[i] * Math.pow(10, j)
            j--
        }
        if (isNaN(sum)) return 0
        if (arr[0] === '-') return -sum
        return sum
    }

// 方法二（和方法一思路想通）： 
    // 运用数组的方法 map()将每个元素*1 变为数字，用reduce()将数字加起来公式为a*10+b算出来即为转换结果（牛客网运行超时，本地编辑器可以过）
    function StrToInt(str)
    {
        // write code here
        if (str.length === 0) return 0
        let arr = str.split('')
        if (arr[0] === '+' || arr[0] === '-') {
            var symb = arr.shift()
        }
        let res =  arr.map((x) => {
            return x * 1
        }).reduce((a, b) => {
            return a * 10 + b
        })
        if (isNaN(res)) {
            return 0
        }
        if (symb === '-') {
            return -res
        }
        return res
    }

// 方法三：
    function StrToInt(str) {
      let res = 0,
          flag = 1
      const n = str.length
      if (!n) return 0
      if (str[0] === '-') {
        flag = -1
      }
      for (let i = str[0] === '+' || str[0] === '-' ? 1 : 0; i < n; i++) {
        if (!(str[i] >= '0' && str[i] <= '9')) return 0
        res = (res << 1) + (res << 3) + (str[i] - '0')
        // res<<1即res*2，而res<<3即res*8 ，此式类似于res = (res * 10) + (str[i] - '0')
      }
      return res * flag
    }

###### 50 数组中重复的数字 ######

题目描述：  
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组\{2,3,1,0,2,5,3\}，那么对应的输出是第一个重复的数字2。

// 方法一：
    // 查找数组中最后一次出现的位置是否和当前位置一样，一样则不重复，反之重复
    function duplicate(numbers, duplication)
    {
        // write code here
        for (let i = 0; i < numbers.length; i++) {
            if (numbers.lastIndexOf(numbers[i]) !== i) {
                duplication[0] = numbers[i]
                return true
            }
        }
        return false
        //这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
        //函数返回True/False
    }

// 方法二：
    // 用额外的数组或者hash记录下次数，然后再判断次数大于1的即为重复的
    function duplicate(numbers, duplication) {
      const map = {}
      let flag = false
      for (let i = 0; i < numbers.length; i++) {
        if (!map[numbers[i]]) {
          map[numbers[i]] = 1
        } else {
          duplication[0] = numbers[i]
          flag = true
          break
        }
      }
      return flag
    }

###### 51 构建乘积数组 ######

题目描述：  
给定一个数组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\]。不能使用除法。

> <分析>：  
> 设有数组大小为5。  
> 对于第一个for循环  
> 第一步：b\[0\] = 1;  
> 第二步：b\[1\] = b\[0\] \* a\[0\] = a\[0\]  
> 第三步：b\[2\] = b\[1\] \* a\[1\] = a\[0\] \* a\[1\];  
> 第四步：b\[3\] = b\[2\] \* a\[2\] = a\[0\] \* a\[1\] \* a\[2\];  
> 第五步：b\[4\] = b\[3\] \* a\[3\] = a\[0\] \* a\[1\] \* a\[2\] \* a\[3\];  
> 然后对于第二个for循环  
> 第一步 temp \*= a\[4\] = a\[4\]; b\[3\] = b\[3\] \* temp = a\[0\] \*a\[1\] \* a\[2\] \* a\[4\];  
> 第二步 temp \*= a\[3\] = a\[4\] \* a\[3\]; b\[2\] = b\[2\] \* temp = a\[0\] \* a\[1\] \* a\[4\] \* a\[3\];  
> 第三步 temp \*= a\[2\] = a\[4\] \* a\[3\] \* a\[2\]; b\[1\] = b\[1\] \* temp = a\[0\] \* a\[4\] \* a\[3\] \* a\[2\];  
> 第四步 temp \*= a\[1\] = a\[4\] \* a\[3\] \* a\[2\] \* a\[1\]; b\[0\] = b\[0\] \* temp = a\[4\] \* a\[3\] \* a\[2\] \* a\[1\];  
> 由此可以看出从b\[4\]到b\[0\]均已经得到正确计算。

// 由上解析:
    function multiply(array)
    {
        // write code here
        let len = array.length
        const b = []
        if (len === 0) return b
        b[0] = 1
        for (let i = 1; i < len; i++) {
            b[i] = array[i - 1] * b[i - 1]
        }
        let temp = 1
        for (let i = len - 2; i >= 0; i--) {
            temp *= array[i + 1]
            b[i] *= temp
        }
        return b
    }

###### 52 正则表达式匹配 ######

题目描述：  
请实现一个函数用来匹配包括’.‘和’*‘的正则表达式。模式中的字符’.‘表示任意一个字符，而’*'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab\*a"均不匹配

方法一： （直接调用原生正则匹配）
    function match(s, pattern)
    {
        // write code here
        let r = `/^${pattern}$/`
        // 或 let  r = new RegExp(`^${pattern}$`)
        return eval(r).test(s)
    }

> **当模式中的第二个字符不是“\*”时**
> 
> 1.如果字符串中的第一个字符和模式中的第一个字符相匹配，那么在字符串和模式上都向后移动一个字符，然后匹配剩余的字符串和模式。
> 
> 2.如果字符串中的第一个字符和模式中的第一个字符不相匹配，则直接返回false。  
> ————————————————————————  
> **当模式中第二个字符是“\*”时，有多种不同匹配方式。**
> 
> 1.在模式上上向后移动两个字符，相当于x*被忽略。因为“*”可以匹配字符串中的0个字符。
> 
> 2.如果模式中第一个字符和字符串中的第一个字符相匹配，则在字符串上向后移动一个字符。  
> 　　这种情况下可以有两种选择：  
> 　　　　a.模式上向后移动两个字符  
> 　　　　b.模式保持不变
> 
> 对于JS语言来说，我们的递归函数除了字符串和模式外，还需要两个额外参数来记录下当前在字符串和模式上移动的位置索引。

// 方法二：（自己实现正则匹配）
    // 思路如上
    function match(s, pattern)
    {
        // write code here
      if (s === null || pattern === null) {
        return false
      }
      return matchCore(s, 0, pattern, 0)
    }
    function matchCore(s, istr, pattern, ipattern) {
      if (istr === s.length && ipattern === pattern.length) {
        return true
      }
    
      if (istr !== s.length && ipattern === pattern.length) {
        return false
      }
      if (pattern[ipattern + 1] === '*') {
        if (pattern[ipattern] === '.' && istr !== s.length || pattern[ipattern] === s[istr]) {
          return (
            matchCore(s, istr + 1, pattern, ipattern + 2) ||
            matchCore(s, istr + 1, pattern, ipattern) ||
            matchCore(s, istr, pattern, ipattern + 2)
          )
        }
        return matchCore(s, istr, pattern, ipattern + 2)
      }
    
      if (s[istr] === pattern[ipattern] || pattern[ipattern] === '.' && istr !== s.length) {
        return matchCore(s, istr + 1, pattern, ipattern + 1)
      }
      return false
    }

###### 53 表示数值的字符串 ######

题目描述：  
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100",“5e2”,"-123",“3.1416"和”-1E-16"都表示数值。 但是"12e",“1a3.14”,“1.2.3”,"±5"和"12e+4.3"都不是。

// 方法一：（依旧原生js方法，但是此题考察如何实现isNaN()函数）
    function isNumeric(s)
    {
        // write code here
        return !isNaN(Number(s))
    }

// 方法二：
    //正则表达式匹配判断
    // 第一种
    function isNumeric(s)
    {
        // write code here
        return s.match(/[+-]?\d*(\.\d+)?([eE][+-]?\d+)?/g)[0] === s
    }
    // 第二种
    function isNumeric2(s) {
      return s.search(/^[+-]?\d*(\.\d*)?$/) === 0 || s.search(/^[+-]?\d+(\.\d*)?[Ee]{1}[+-]?\d+$/) === 0
    }

// 方法三：（纯逻辑判断）
    function isNumeric(s)
    {
        // write code here
        let sign = false, decimal = false, hasE = false
        for (let i = 0; i < s.length; i++) {
            if (s[i] === 'e' || s[i] === 'E') {
                if (i === s.length - 1) return false // e后面一定要接数字
                if (hasE) return false  // 不能同时存在两个e
                hasE = true
            } else if (s[i] === '+' || s[i] === '-') {
                // 第二次出现+-符号，则必须紧接在e之后
                if (sign && s[i-1] !== 'e' && s[i-1] !== 'E') return false
                // 第一次出现+-符号，且不是在字符串开头，则也必须紧接在e之后
                if (!sign && i > 0 && s[i-1] !== 'e' && s[i-1] !== 'E') return false
                sign = true
            } else if (s[i] === '.') {
                // e后面不能接小数点，小数点不能出现两次
                if (hasE || decimal) return false
                decimal = true
            } else if (s[i] < '0' || s[i] > '9') // 不合法字符
                return false
        }
        return true
    }

###### 54 字符流中第一个不重复的字符 ######

题目描述：  
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。

输出描述:  
如果当前字符流没有存在出现一次的字符，返回\#字符。

// 思路和第40题方法二相同，定义map对象存储出现的次数
    var map = {}
    //Init module if you need
    function Init()
    {
        // write code here
        map = {}
    }
    //Insert one char from stringstream
    function Insert(ch)
    {
        // write code here
        if (!map[ch]) map[ch] = 1
        else map[ch]++
    }
    //return the first appearence once char in current stringstream
    function FirstAppearingOnce()
    {
        // write code here
        for (let i in map) {
            if (map[i] === 1) return i
        }
        return '#'
    }

// 方法二： （用indexOf和lastIndexOf判断）
    //Init module if you need
    let arr = []
    function Init()
    {
        // write code here
        arr = []
    }
    //Insert one char from stringstream
    function Insert(ch)
    {
        // write code here
        arr.push(ch)
        
    }
    //return the first appearence once char in current stringstream
    function FirstAppearingOnce()
    {
        // write code here
        for (let i = 0; i < arr.length; i++) {
            if (arr.lastIndexOf(arr[i]) === arr.indexOf(arr[i])) {
                return arr[i]
            }
        }
        return '#'
    }

###### 55 链表中环的入口结点 ######

题目描述：  
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

> **先看一个链表中环的相关定理**：  
> 给定一个单链表，只给出头指针h：  
> 1、如何判断是否存在环？  
> 2、如何知道环的长度？  
> 3、如何找出环的连接点在哪里？  
> 4、带环链表的长度是多少？  
> ————————————————————————————  
> 解法：  
> 1、对于问题1，使用追赶的方法，设定两个指针slow、fast，从头节点开始，每次分别前进1步、2步。如存在环，则两者相遇；如不存在环，fast遇到NULL退出。并且碰撞点到头节点的距离为环中结点数n。  
> 2、对于问题2，记录下问题1的碰撞点p，碰撞点p肯定是在环中的，从这个结点出发，一边移动一边计数，再次回到这个结点时就得到了环中结点数n。  
> 3、问题3：有定理：碰撞点p到连接点的距离=头节点到连接点的距离，因此，分别从碰撞点、头节点相同速度开始走，相遇的那个点就是连接点。  
> 　　该定理的证明如下： 设头节点到连接点的距离为x,连接点到碰撞点的距离为y，碰撞点到连接点的距离为z，环的长度为n，  
> (1)碰撞点到头节点的距离为n,则有x+y=n  
> (2)又因为环的长度为n,则有y+z=n  
> (3)由(1)(2)可得z=x，也就是碰撞点p到连接点的距离=头节点到连接点的距离
> 
> 4、问题3中已经求出连接点距离头指针的长度，加上问题2中求出的环的长度，二者之和就是带环单链表的长度

// 思路：
    // 1.一快一慢指针，先找到碰撞点。
    // 2.然后碰撞点到入口节点的距离就是头结点到入口节点的距离。
    /*function ListNode(x){
        this.val = x;
        this.next = null;
    }*/
    function EntryNodeOfLoop(pHead)
    {
        // write code here
        if (pHead === null) return null
        let pSlow = pHead
        let pFast = pHead
        while (pFast !== null && pFast.next !== null) {
            pSlow = pSlow.next
            pFast = pFast.next.next
            if (pSlow === pFast) {
                pFast = pHead
                while (pSlow !== pFast) {
                    pSlow = pSlow.next
                    pFast = pFast.next
                }
                return pFast
            }
        }
        return null
    }

###### 56 删除链表中重复的结点 ######

题目描述：  
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

// 方法一： 
    // 1.因为链表是单向的，如果是第一个、第二个节点就重复的话，删除就比较麻烦。因此额外添加头节点来解决
    // 2.因为重复的节点不一定是重复两个，可能重复很多个，需要循环处理下。
    function ListNode(x){
        this.val = x;
        this.next = null;
    }
    function deleteDuplication(pHead)
    {
        // write code here
        let head = new ListNode(0)
        head.next = pHead
        let pNode = head
        let pCur = head.next
        while (pCur !== null) {
            if (pCur.next !== null && pCur.val === pCur.next.val) {
                while (pCur.next !== null && pCur.val === pCur.next.val) {
                    pCur = pCur.next
                }
                pNode.next = pCur.next
                pCur = pCur.next
            } else {
                pNode = pNode.next
                pCur = pCur.next
            }
        }
        return head.next
    }

// 方法二：（递归）
    /*function ListNode(x){
        this.val = x;
        this.next = null;
    }*/
    function deleteDuplication(pHead)
    {
        // write code here
        if (pHead === null) return null
        if (pHead !== null && pHead.next === null) return pHead
        let pCur = null
        if (pHead.val === pHead.next.val) {
            pCur = pHead.next.next
            while (pCur !== null && pCur.val === pHead.val) {
                pCur = pCur.next
            }
            return deleteDuplication(pCur)
        } else {
            pCur = pHead.next
            pHead.next = deleteDuplication(pCur)
            return pHead
        }
    }

###### 57 二叉树的下一个结点 ######

题目描述：  
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

// 方法一：
    // 先找出根节点然后中序遍历压入数组，在数组中找到需要找出的那个节点的下一个节点（index+1）
    // 第一种(非递归方法)
    /*function TreeLinkNode(x){
        this.val = x;
        this.left = null;
        this.right = null;
        this.next = null;
    }*/
    function GetNext(pNode)
    {
        // write code here
        let pHead = pNode
        while (pHead.next !== null) {
            pHead = pHead.next
        }
        var stack = []
        let p = pHead
        let arr = []
        while (p || stack.length !== 0) {
            while (p) {
                stack.push(p)
                p = p.left
            }
            p = stack.pop()
            arr.push(p)
            p = p.right
        }
        return arr[arr.indexOf(pNode) + 1]
    }
    
    // 第二种(递归方法)
    function GetNext(pNode)
    {
        // write code here
        let pHead = pNode
        while (pHead.next !== null) {
            pHead = pHead.next
        }
        let arr = []
        midTra(pHead, arr)
        return arr[arr.indexOf(pNode) + 1]
    }
    function midTra(pNode, arr) {
        if (!pNode) return
        midTra(pNode.left, arr)
        arr.push(pNode)
        midTra(pNode.right, arr)
    }

![在这里插入图片描述][20190919143459704.png]

// 方法二：
    // 由上图结合以下思路：
    // 1.如果一个节点有右子树，那么它的下一个节点就是它的右子树中的最左子节点。也就是说，从右子节点出发一直沿着指向左子节点的指针，我们就能找到下一个节点。
    //2.如果没有右子树，又可以分为两种情况
    //		如果节点是它父节点的左子节点，那么它的下一个节点就是它的父节点。
    //		如果一个节点既没有右子树，并且它还是父节点的右子节点，那么需要沿着指向父节点的指针一直向上便利，直到找到一个是它父节点的左子节点的节点。
    /*function TreeLinkNode(x){
        this.val = x;
        this.left = null;
        this.right = null;
        this.next = null;
    }*/
    function GetNext(pNode)
    {
        // write code here
        if (!pNode) return null
        while (pNode.right !== null) {  // 如果有右子树，则找右子树的最左节点
            pNode = pNode.right
            while (pNode.left !== null) pNode = pNode.left
            return pNode
        }
        while (pNode.next !== null) {  // 没右子树，则找第一个当前节点是父节点左孩子的节点
            if (pNode.next.left === pNode) return pNode.next
            pNode = pNode.next
        }
        return null  // 退到了根节点仍没找到，则返回null
    }

###### 58 对称的二叉树 ######

题目描述：  
请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

// 方法一：
    // 递归实现：
    // 1.只要pRoot.left和pRoot.right是否对称即可
    // 2.左右节点的值相等且对称子树left.left， right.right ;left.rigth,right.left也对称
    /* function TreeNode(x) {
        this.val = x;
        this.left = null;
        this.right = null;
    } */
    function isSymmetrical(pRoot)
    {
        // write code here
        if(pRoot === null) return true
        return issymmetrical(pRoot.left, pRoot.right)
    }
    function issymmetrical (left, right) {
        if (!left && !right) return true
        if (!left || !right) return false
        return right.val === left.val && issymmetrical(left.left, right.right) && issymmetrical (left.right, right.left)
    }

// 方法二：
    // 非递归：使用栈来实现（思路和递归相似）
    // 即依次左右两边成对入栈，比较两边元素是否一致，直到为空都相同的话则为对称
    /* 1.出栈的时候也是成对成对的 ，
    1.若都为空，继续；
    2.一个为空，返回false;
    3.不为空，比较当前值，值不等，返回false；
    * 2.确定入栈顺序，每次入栈都是成对成对的，如left.left， right.right ;left.rigth,right.left
    */
    /* function TreeNode(x) {
        this.val = x;
        this.left = null;
        this.right = null;
    } */
    function isSymmetrical(pRoot)
    {
        // write code here
        if(pRoot === null) return true
        let stack = []
        stack.push(pRoot.left)
        stack.push(pRoot.right)
        while (stack.length) {
            let right = stack.pop()
            let left = stack.pop()
            if (!right && !left) continue
            if (!right || !left) return false
            if (right.val !== left.val) return false
            stack.push(left.right)
            stack.push(right.left)
            stack.push(left.left)
            stack.push(right.right)
        }
        return true
    }
    
    // 使用queue队列来实现（和上面基本一致）
    function isSymmetrical(pRoot)
    {
        // write code here
        if(pRoot === null) return true
        let queue = []
        queue.unshift(pRoot.left)
        queue.unshift(pRoot.right)
        while (queue.length) {
            let left = queue.pop()
            let right = queue.pop()
            if (!right && !left) continue
            if (!right || !left) return false
            if (right.val !== left.val) return false
            queue.unshift(left.left)
            queue.unshift(right.right)
            queue.unshift(left.right)
            queue.unshift(right.left)
        }
        return true
    }

###### 59 按之字形顺序打印二叉树 ######

题目描述：  
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

// 正常的广度遍历的话，都是同样的顺序，从左到右，而我们要在广度遍历的基础上改造为之字形遍历。
    // 也就是我们需要在奇数行从左至右，在偶数行从右至左，因为是先进后出，分析可得我们需要的数据结构是栈。
    // 为了避免顺序错误，我们需要的不只是一个栈，而是两个栈，这个大家画图研究下就能想到。
    // 两个栈是这么用的，这个栈保存这一行的数据，另一个栈保存下一行的数据，然后一行打印完后交替。
    // 当然可以在广度遍历的基础上加个临时数组，然后对偶数行的数据reverse，但是reverse效率太低，所以就不用这种方法了
    /* function TreeNode(x) {
        this.val = x;
        this.left = null;
        this.right = null;
    } */
    function Print(pRoot) {
        // write code here
      const lists = []
    
      if (pRoot === null) {
        return lists
      }
    
      const stack1 = []
      const stack2 = []
    
      stack2.push(pRoot)
      let i = 1
      while (stack1.length !== 0 || stack2.length !== 0) {
        const list = []
    
        // 为奇数层
        if ((i & 1) === 1) {
          while (stack2.length !== 0) {
            const tmp = stack2[stack2.length - 1]
            stack2.pop()
            list.push(tmp.val)
            if (tmp.left !== null) stack1.push(tmp.left)
            if (tmp.right !== null) stack1.push(tmp.right)
          }
        }
        // 为偶数层
        else {
          while (stack1.length !== 0) {
            const tmp = stack1[stack1.length - 1]
            stack1.pop();
            list.push(tmp.val);
            if (tmp.right !== null) stack2.push(tmp.right)
            if (tmp.left !== null) stack2.push(tmp.left)
          }
        }
        ++i
        lists.push(list)
      }
      return lists
    }

###### 60 把二叉树打印成多行 ######

题目描述：  
从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

// 方法一：（递归实现）
    // 利用递归的方法进行先序遍历，传递深度，递归深入一层扩容一层数组，先序遍历又保证了同层节点按从左到右入数组
    /* function TreeNode(x) {
        this.val = x;
        this.left = null;
        this.right = null;
    } */
    function Print(pRoot)
    {
        // write code here
        let list = []
        depth(pRoot, 1, list)
        return list
    }
    
    function depth (root, deepth, list) {
        if (!root) return
    	// 为什么判断深度大于数组长度？ 假如现在元素是[1,2,3]，当进入2时会创建一个 数组,此时 depth = 2,size=2；当2遍历完后会进入3，此时3 就不用创建数组了，因为 2,3是同一层的，并且此时 depth==size 。这个判断是用来让最左的元素创建新数组就行了，而同一层后边的元素共用这个数组
        if (deepth > list.length) list.push(new Array())
        list[deepth - 1].push(root.val)
        depth(root.left, deepth + 1, list)
        depth(root.right, deepth + 1, list)
    }

// 方法二： （非递归）
    // 采用队列进行层次遍历
    /* function TreeNode(x) {
        this.val = x;
        this.left = null;
        this.right = null;
    } */
    function Print(pRoot)
    {
        // write code here
        let res = []
        if (!pRoot) return res
        let queue = []
        queue.push(pRoot)
        while (queue.length) {
            let count = 0, num = queue.length
            let arr = []
            // num相当于同一行内节点的个数，当count小于num时代表这一行元素还未全部压入数组，当count等于num时代表这一行节点已经全部压入数组。
            while (count++ < num) {
                let pCur = queue.shift()
                arr.push(pCur.val)
                if (pCur.left) queue.push(pCur.left)
                if (pCur.right) queue.push(pCur.right)
            }
            res.push(arr)
        }
        return res
    }

###### 61序列化二叉树 ######

题目描述：  
请实现两个函数，分别用来序列化和反序列化二叉树

二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（\#），以 ！ 表示一个结点值的结束（value!）。

二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

// 方法一：（JSON的方法）
    // 简单粗暴
    /* function TreeNode(x) {
        this.val = x;
        this.left = null;
        this.right = null;
    } */
    function Serialize(pRoot)
    {
        // write code here
        return JSON.stringify(pRoot)
    }
    function Deserialize(s)
    {
        // write code here
        return JSON.parse(s)
    }

// 方法二：（使用数组的来保存前序遍历的值）
    // 反序列化递归构建二叉树。
    // 只用前序遍历重构二叉树时必须是一颗完全二叉树，所以节点为null的值我们使用'#'来模拟一棵完全二叉树的前序遍历。
    function TreeNode(x) {
        this.val = x;
        this.left = null;
        this.right = null;
    }
    let arr = []
    function Serialize(pRoot)
    {
        // write code here
        if (!pRoot) arr.push('#')
        else {
            arr.push(pRoot.val)
            Serialize(pRoot.left)
            Serialize(pRoot.right)
        }
    }
    function Deserialize(s)
    {
        // write code here
        let node = null
        if (arr.length < 1) return null
        let number = arr.shift()
        if (typeof number === 'number') {
            node = new TreeNode(number)
            node.left = Deserialize()
            node.right = Deserialize()
        }
        return node
    }

###### 62 二叉搜索树的第k个结点 ######

题目描述：  
给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。

// 方法一：（递归）
    // 二叉搜索树中序遍历的结果为从小到大排列。输出第k-1即为结果
    /* function TreeNode(x) {
        this.val = x;
        this.left = null;
        this.right = null;
    } */
    function KthNode(pRoot, k)
    {
        // write code here
        let arr = []
        treeTra(pRoot, arr)
        if (k > 0 && k <= arr.length) {
            return arr[k - 1];
        }
        return null
    }
    function treeTra (pRoot, arr) {
        if (!pRoot) return
        treeTra(pRoot.left, arr)
        arr.push(pRoot)
        treeTra(pRoot.right, arr)
    }

// 方法二：（非递归）
    // 思路和递归一样先将中序遍历压入数组，返回k-1的值
    /* function TreeNode(x) {
        this.val = x;
        this.left = null;
        this.right = null;
    } */
    function KthNode(pRoot, k)
    {
        // write code here
        let res = []
        let stack = []
        while (stack.length || pRoot) {
            while (pRoot) {
                stack.push(pRoot)
                pRoot = pRoot.left
            }
            pRoot = stack.pop()
            res.push(pRoot)
            pRoot = pRoot.right
        }
        if (res.length < k || k < 1) return null
        return res[k - 1]
    }

###### 63 数据流中的中位数 ######

题目描述：  
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

// 对插入的值排序后输出对应的中位数
    let arr = []
    function Insert(num)
    {
        // write code here
        arr.push(num)
        arr.sort((a, b) => a - b)
    }
    function GetMedian(){
    	// write code here
        if (arr.length % 2 === 0) return (arr[arr.length / 2] + arr[arr.length / 2 - 1]) / 2
        else return arr[(arr.length - 1)/2]
    }

###### 64 滑动窗口的最大值 ######

题目描述：  
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组\{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\]\}。

// 如果我们以滑动窗口为对象，那么就是数组在滑动窗口上移动。
    // 显然，可以看出滑动窗口就是一个队列，数组中的一个一个的数先进去，先出来。
    // 此外这题还有一个可以优化的一点就是不一定需要把所有数字存进去队列里，只需要把以后有可能成为最大值的数字存进去。
    // 还有一点要注意的是队列里保存的是下标，而不是实际的值，因为窗口移动主要是下标的变化
    // 当然还有其他解法，比如利用两个栈去实现这个队列，从而使得查询时间复杂度降低到O(n)
    function maxInWindows(num, size)
    {
        // write code here
        let res = []
        if(size == 0){
            return res
        }
        let begin
        let queue = []
        for(let i = 0; i < num.length; i++){
            begin = i - size + 1 // 代表滑动窗口的左边界
            if(queue.length == 0){
                queue.push(i)
            }else if(begin > queue[0]){
                queue.shift()
            }
            while((queue.length != 0) && (num[queue[queue.length - 1]] <= num[i])){
                queue.pop()
            }
            queue.push(i)
            if(begin >= 0){
                res.push(num[queue[0]])
            }
        }
        return res
    }

###### 65 矩阵中的路径 ######

题目描述：  
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 a b c e s f c s a d e e 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

> 分析题意，我们可以知道这道题用回溯法解决最好，因为我们需要一个一个字母的匹配，当发现不行时，就要回溯上个步骤，选择另一步。
> 
> 回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
> 
> 回溯法的基本思想：
> 
> 在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。
> 
> 若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。
> 
> 而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。
> 
> 字典树也有点和回溯法的解空间树类似。

// 思路如上
    function hasPath(matrix, rows, cols, path) {
      const pathLength = 0;
      const visited = new Array(rows * cols);
      for (let row = 0; row < rows; row++) {
        for (let col = 0; col < cols; col++) {
          // 遍历，遍历的点为起点。
          if (hasPathCore(matrix, rows, cols, row, col, path, pathLength, visited)) {
            return true;
          }
        }
      }
      return false;
    }
    function hasPathCore(matrix, rows, cols, row, col, path, pathLength, visited) {
      let hasPath = false;
      if (pathLength === path.length) return true;
      if (
        row >= 0 &&
        row < rows &&
        col >= 0 &&
        col < cols &&
        matrix[row * cols + col] === path[pathLength] &&
        !visited[row * cols + col]
      ) {
        ++pathLength;
        visited[row * cols + col] = true;
        // 因为||为短路运算符，只要第一个满足就会返回，而不会去计算后面的，所以有些路径可以不用去走。
        hasPath =
          hasPathCore(matrix, rows, cols, row - 1, col, path, pathLength, visited) ||
          hasPathCore(matrix, rows, cols, row, col - 1, path, pathLength, visited) ||
          hasPathCore(matrix, rows, cols, row + 1, col, path, pathLength, visited) ||
          hasPathCore(matrix, rows, cols, row, col + 1, path, pathLength, visited);
        if (!hasPath) {
          --pathLength;
          visited[row * cols + col] = false;
        }
      }
      return hasPath;
    }

###### 66 机器人的运动范围 ######

题目描述：  
地上有一个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) {
      const visited = [];
      for (let i = 0; i < rows; i++) {
        visited.push([]);
        for (let j = 0; j < cols; j++) {
          visited[i][j] = false;
        }
      }
      return move(0, 0, rows, cols, visited, threshold);
    }
    function move(i, j, rows, cols, visited, threshold) {
      if (i < 0 || i === rows || j < 0 || j === cols || visited[i][j]) {
        return 0;
      }
      let sum = 0;
      const tmp = `${i}${j}`;
      for (let k = 0; k < tmp.length; k++) {
        sum += tmp.charAt(k) / 1; // 转成数字
      }
      if (sum > threshold) {
        return 0;
      }
      visited[i][j] = true;
      return (
        1 +
        move(i + 1, j, rows, cols, visited, threshold) +
        move(i, j + 1, rows, cols, visited, threshold) +
        move(i - 1, j, rows, cols, visited, threshold) +
        move(i, j - 1, rows, cols, visited, threshold)
      );
    }

###### 67 剪绳子 ######

题目描述：  
给你一根长度为n的绳子，请把绳子剪成m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k\[0\],k\[1\],…,k\[m\]。请问k\[0\]xk\[1\]x…xk\[m\]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

输入描述:  
输入一个数n，意义见题面。（2 <= n <= 60）  
输出描述:  
输出答案。

> 示例1：  
> 输入  
> 8  
> 输出  
> 18

/**
     * 题目分析：
     * 先举几个例子，可以看出规律来。
     * 4 ： 2*2
     * 5 ： 2*3
     * 6 ： 3*3
     * 7 ： 2*2*3 或者4*3
     * 8 ： 2*3*3
     * 9 ： 3*3*3
     * 10：2*2*3*3 或者4*3*3
     * 11：2*3*3*3
     * 12：3*3*3*3
     * 13：2*2*3*3*3 或者4*3*3*3
     *
     * 下面是分析：
     * 首先判断k[0]到k[m]可能有哪些数字，实际上只可能是2或者3。
     * 当然也可能有4，但是4=2*2，我们就简单些不考虑了。
     * 5<2*3,6<3*3,比6更大的数字我们就更不用考虑了，肯定要继续分。
     * 其次看2和3的数量，2的数量肯定小于3个，为什么呢？因为2*2*2<3*3，那么题目就简单了。
     * 直接用n除以3，根据得到的余数判断是一个2还是两个2还是没有2就行了。
     * 由于题目规定m>1，所以2只能是1*1，3只能是2*1，这两个特殊情况直接返回就行了。
     *
     * 乘方运算的复杂度为：O(log n)，用动态规划来做会耗时比较多。
     */
     方法一：（思路如上）
    function cutRope(number)
    {
        // write code here
        if (number === 2) return 1
        if (number === 3) return 2
        let x = number % 3
        let y = Math.floor(number / 3)
        if (x === 0) return Math.pow(3, y)
        else if (x === 1) return 2 * 2 * Math.pow(3, y - 1)
        else return 2 * Math.pow(3, y)
    }

// 方法二：（动态规划）
    动态规划求解问题的四个特征： 
    // ①求一个问题的最优解； 
    // ②整体的问题的最优解是依赖于各个子问题的最优解； 
    // ③小问题之间还有相互重叠的更小的子问题； 
    // ④从上往下分析问题，从下往上求解问题；
    function cutRope(number)
    {
        // write code here
        if(number === 2) return 1
        if(number === 3) return 2
        let dp = new Array()
        /*
            下面3行是n>=4的情况，跟n<=3不同，4可以分很多段，比如分成1、3，
            这里的3可以不需要再分了，因为3分段最大才2，不分就是3。记录最大的。
             */
        dp[1] = 1
        dp[2] = 2
        dp[3] = 3
        let res = 0;//记录最大的
        for (let i = 4; i <= number; i++) {
            for (let j = 1; j <= i / 2 ; j++) {
                res = Math.max(res, dp[j] * dp[i-j])
            }
            dp[i]=res
        }
        return dp[number];
    }

// 方法三：（贪婪解法）
    // 当n大于等于5时，我们尽可能多的剪长度为3的绳子；当剩下的绳子长度为4时，把绳子剪成两段长度为2的绳子。 为什么选2，3为最小的子问题？因为2，3包含于各个问题中，如果再往下剪得话，乘积就会变小。 为什么选长度为3？因为当n≥5时，3(n−3)≥2(n−2)
    function cutRope(number)
    {
        // write code here
        if (number < 2) return 0
        if (number == 2) return 1
        if (number == 3) return 2
     
        let timesOf3 = number / 3
     
        /*  当最后绳子长度为 4 时，这时候分割成 2，2 而不是 3，1 因为2*2=4 > 3=3*1  */
        if (number - timesOf3 * 3 === 1) timesOf3--
        let timesOf2 = (number - timesOf3 * 3) / 2;
        return parseInt(Math.pow(3, timesOf3)) * parseInt(Math.pow(2, timesOf2));
    }

> PS:本文多数算法思想参考 [此篇博文][Link 2] 及牛客网每题的讨论贴，若某题思路描述不清晰请详细查看

[Link 1]: https://www.nowcoder.com/discuss/457173?type=7&order=0&pos=57&page=0&source_id=discuss_center_7&channel=666
[offer]: https://www.nowcoder.com/ta/coding-interviews
[20190919143459704.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/6498ccd58d8d4c2d9dc0f35274e09d22.png
[Link 2]: https://www.cnblogs.com/wuguanglin/p/code-interview.html