0

今天面试遇到的两个问题,用JS写出:
1、找出二叉树节点的最长距离
2、找出数组中的最长递增序列

想了半天是在没想出来,求大佬们赐教(代码来点注释可好,算法渣很无力呀。。。)

6个回答

0

希望你去看一下动态规划算法...

0

这2题目稍微百度一下都有,而且带注释。

0

其实细想一下题目并不复杂,二叉树计算一下每个节点左边最大深度和右边最大深度之和,最后选择最大的就可以。
数组题计算每个节点之前最长递增序列,再加上本节点,就是包括当前节点之前的最长子序列,记住长度和前一个节点的下标,从第一个节点开始遍历到最后一个,选择计算出的所有的节点最大长度,就是最长的了。
方法比代码重要

0

我写过最长递增子序列,仅作参考,二叉树问题应该类似,都是动态规划问题,可以看看左程云的《程序员代码面试指南》

// 给定数组arr,返回arr的最长递增子序列的长度,比如arr=[2,1,5,3,6,4,8,9,7],最长递增子序列为[1,3,4,8,9]返回其长度为5.
// dp[i]表示以必须arr[i]这个数结束的情况下产生的最大递增子序列的长度。对于第一个数来说,很明显dp[0]为1,当我们计算dp[i]的时候,
// 我们去考察i位置之前的所有位置,找到i位置之前所有比arr[i]小的位置中最大的那个值,记为dp[j](0=<j<i),
// dp[j]代表以arr[j]结尾的最长递增序列,而dp[j]又是之前计算过的最大的那个值,
// 则dp[i]=dp[j]+1.计算完dp之后,我们找出dp中的最大值,即为这个串的最长递增序列
let arr=[2,1,5,3,6,4,8,9,7];
function search(arr) {
    let temp=[1];
    for(let i=1;i<arr.length;i++){
        let temp_arr=arr.slice(0,i);
        let flag=[];
        for(let j=0;j<temp_arr.length;j++){
            if(arr[j]<arr[i]){
                flag.push(temp[j])
            }
        }
        if(flag.length===0){
            temp.push(1)
        }else{
            temp.push(Math.max(...flag)+1)
        }
    }
    return Math.max(...temp)
}

撰写答案