前端就该用 JS 刷算法8

每日一题 -- 树

完全二叉树的节点数

// https://leetcode-cn.com/problems/count-complete-tree-nodes/

/**
 * @分析 -- 暴力法
 * 1. 层序遍历整棵树，然后就能求得整颗树的节点数了
 * 2. 其实这种是求任意树的节点数都可以这么搞的
 */
var countNodes = function(root) {
    if(!root) return 0
    let queue= []
    let sum = 0
    queue.push(root)
    while(queue.length){
        let len = queue.length
        sum +=len
        while(len--){
            const root = queue.shift()
            if(root.left) queue.push(root.left)
            if(root.right) queue.push(root.right)
        }
    }
    return sum
};

二叉树的最大宽度

朴素的层序遍历+清除左右节点

• 求的是一层的最大宽度，所以无论是 null 还是正常节点，我都让它入队列中
• 但是在每一层开始前，先做一次清除左右 null 节点的操作，这样保证队列的头尾节点都是存在的
• 但是最后超时了

// https://leetcode-cn.com/problems/maximum-width-of-binary-tree/


/**
 * @分析 --- 超时了
 * 1. 层序遍历，然后记住每一层的值的数量，求那个最大的值
 * 2. 宽度是左右节点之间的长度，所以右节点之后的 null 是可以忽略的,每次从队列中出队钱，要先取出队列中右侧的 null
 */
var widthOfBinaryTree = function (root) {
    if (!root) return 0
    let queue = []
    let max = 1
    queue.push(root)
    while (queue.length) {
        queue = deleteNull(queue)
        let len = queue.length
        if (!len) return max
        max = Math.max(max, len)
        while (len--) {
            const root = queue.shift()
            if (!root) {
                queue.push(null, null)
            } else {
                queue.push(root.left, root.right)
            }
        }
    }
    return max
};
//  清除左右节点的 null 节点
const deleteNull = arr => {
    while (arr.length && !arr[0]) {
        arr.shift()
    }
    while (arr.length && !arr[arr.length - 1]) {
        arr.pop()
    }
    return arr
}

基于完全二叉树的特性

• 将树看做是完全二叉树，然后再存储的时候将下标值存一下，酱紫就可以知道每一个节点对应的下标值，然后每一层根据下标值进行比较
• 但是如果按照完全二叉树给节点贴下标，那么最后一层的最右边的节点下标是 Math.pow(2,n)-1,其中 n 是树的层数
• 然后我们又知道当 2^53 之后，精度会丢失，所以坑爹的就是，输入可以是先右树走1个节点53次，然后第 54层开始来真实值，酱紫前面 53 层的宽度都是1，从 54 层开始需要开始计算，但是这个时候，他们的下标已经超出 JS 的 Number 类型的计算极限了
• 这个时候，只能用到 JS 的 bigInt 来计算节点下标了
• 当然最后对标完，还是得转回 Number 类型

/**
 * @分析
 * 1. 用完全二叉树的方式来求
 * 2. 每次除了存节点，还得存一下对应 pos(类似下标的值，根节点是1),
 * 3. 这样求每一层的宽度，只需要求第一个和最后一个非空节点，两者 pos 相减即可。
 * @注意
 * 1. 如果两个炒鸡大的数相减，会得到 NaN，从而报错；
 * 2. 一般情况下是不会出现那么大的树的，但是当树的层级比较高的时候，而每一层的 pos 值都是 2^n-1,就会有概率超出
 * 
 */
var widthOfBinaryTree = function (root) {
    if (!root) return 0
    let res = 0
    let queue = []
    let level = 0 // 记录当前层，用来判断左节点
    let cur_level = 0 // 当前层
    queue.push([1n, root])
    while (queue.length) {
        let len = queue.length // 当前层的长度
        level++ // 每一次循环都是加一层
        // 开始当前层的遍历
        let left
        while (len--) {

            // 弹出节点
            const [pos, root] = queue.shift()
            if (root) {
                queue.push([2n * pos, root.left])
                queue.push([2n * pos + 1n, root.right])
                // 第一个存在节点，就是左节点
                if (level !== cur_level) {
                    // 左节点
                    cur_level = level
                    left = pos
                }
                // 每一个节点都比较一下，就不要判断哪个是最右节点了，因为有可能数组最后节点是 null
                res = Math.max(res, +(pos - left + 1n).toString())

            }
        }
    }
    return res
}

91算法 -- 滑动窗口

新21点

思路是参考大佬的

• 大佬的思路是这个连接 leetcode-cn.com/problems/ne…
• 但是大佬毕竟是用 py 实现的，我用 js 实现一次，也算是一种补充吧。
• 最后会 dp 的真的脑瓜子都很666

// https://leetcode-cn.com/problems/new-21-game/

// 分析的很好 https://leetcode-cn.com/problems/new-21-game/solution/huan-you-bi-zhe-geng-jian-dan-de-ti-jie-ma-tian-ge/


/**
 * 
 * @param {number} N 不超过的值
 * @param {number} K 最少的分数
 * @param {number} W 每一次的抽取范围
 * 
 * @分析
 * 1. 当 x<K 的时候，继续从 [1,W] 中抽取值
 * 2. 当 x >= K 的时候，就停止抽取值，做判断
 *  2.1 如果 x<=N, 记为 1 ;x>N,则是 0
 * 
 * @解题
 * 1. dp[x] 表示牌面为 x 的时候的胜率，其中 x 最大可以是 K+W-1；
 * 2. 因为当 x >= K 的时候，就会停止抽排，所以最大的前一次抽排是 x === K-1,而抽排之后立刻就停止，这个时候牌面就是 [K,K+W-1]
 * 3. 
 */
var new21Game = function(N, K, W) {
    // 如果最小的终止牌面 K 都比目标最大值要大，那么获胜的机会就是 0
    if(K>N) return 0
    // 需要用[0,K+W-1] 的数组来存储胜率，默认胜率都是 1
    const dp = new Array(K+W).fill(1)
    // 在题解中所谓的蓝色格子[K,K+W-1]，就是已经确定好的牌面，这些牌面只和 N 值有关，返回值要不是1，要不就是0
    let temp = K
    let s = 0 // 长度为 W 的窗口的胜率
    while(temp<K+W){
        if(temp>N){
            dp[temp] = 0
        }
        s+=dp[temp]
        // 这个时候都是成功的，所以都是1，默认就是1，所以不用操作
        temp++
    }
    // 然后开始处理 temp<K 的概率
    let downTemp = K-1
    console.log(downTemp,s,W)
    while(downTemp>=0){
        dp[downTemp] = s/W
        // 移动格子
        s = s+dp[downTemp]-dp[downTemp+W]
        downTemp--
    }
    // 为什么最后返回的是 dp[0]呢，是因为所谓的胜率，就是从游戏开始算起的
    // 再直白点，我们就是从游戏开始之处，就考虑到给定的条件下，胜率为多少，所以 dp[0] 代表着的就是开始游戏的胜率
    return dp[0]
};