字节前端笔试8.28

题型：单选10 多选5 编程2

单选多选

常规题型吧~不多说了，偏简单

编程第一题 (100%)

思路：
注意：检验合法性既要检验数也要检验松果数

1. 松果数不符合条件，即[1,100]直接返回 [flase, 0]
2. 二叉树不符合条件
   （1）没有节点，返回[false, 松果数]
   （2）有节点，返回[false,剩余松果数]
3. 二叉树符合条件，返回[true, 剩余松果数]

// 二叉树构造函数
function TreeNode(val, left, right) {
    this.val = val ? val : undefined;
    this.left = left ? left : null;
    this.right = right ? right : null;
}


function fn(nodes, nums) {
    let root = [...nodes];
    // 边界条件
    if (nums <= 0 || nums > 100) return [false,0];
    if (!nodes) return [false, nums];

    let res = [];
    // 构建二叉树并且检验是否合法
    let flag = constructTree(root);
    res.push(flag);
    //  计算剩余松果数
    let temp = nodes.filter(item => item !== -1);
    let sum = temp.length*5 - temp.reduce((p, v) => p+v);
    if (sum >= nums) {
        res.push(0);
    } else {
        res.push(nums-sum);
    }

    return res.join(' ')
}


// 判断是否能构建二叉树
function constructTree(nodes) {
    if (!nodes.length) return null; 

    let root = new TreeNode(nodes.shift());
    let queue = [root];   // 队列存储

    while (nodes.length) {
        let node = queue.shift();   // 获取节点
        if (node.val === -1 && nodes.shift() !== -1) {
            return false;
        }

        let left = new TreeNode(nodes.shift());
        node.left = left;
        queue.push(left);


        let right = new TreeNode(nodes.shift());
        node.right = right;
        queue.push(right);
    }

    return true;

}

编程第二题 (60%) 想到了优化思路但当时没写出来~

关键思路：0在破坏乘积递增的趋势
原思路：
dp获取最大乘积所在index（第一个），根据dp前面的乘积结果逆推start边界（即乘积为0的前一个）
通过了60%，应该是超时了...
优化思路：
（1）解题关键就是0，所以可以把原数组根据0切割成多个子数组，得到最大子数组的乘积，返回相应的索引+1即可
（2）进阶：一次遍历，维护start，end，maxValue，根据nums[end]是否为0且maxValue的值考虑更新end和start的情况
想到了优化思路但当时没写出来！私下补吸取教训
原思路

function fn(n, nums) {
    if (nums.length === 1) return [1,1];

    let dp = [nums[0]*nums[0]];

    for (let i = 1; i < n; i++) {
        dp.push(Math.max(dp[dp.length -1]*nums[i], nums[i]));
    }

    let maxValue = Math.max(...dp);   // 得到最大数字

    let index = dp.indexOf(maxValue);
    let start = index;

    while (start >= 0 ) {
        //console.log(start, nums[start]);
        if (nums[start] !== 0) {
            start--;
            console.log(start);
        } else {
            break;
        }
    }

    return [start+2, index+1];
}

优化思路（待补充...）

有更好的思路欢迎留言！