5.8奇安信笔试
没背过八股，选择题感觉做的挺烂的，2道编程90%，100%
第一个编程题我感觉算法没问题，但只能过90%，有木有大佬帮忙看看呀？
第一题是求二叉树不直接相连节点的和的最大值（父子节点直接相连，子节点之间不直接相连，父节点和子节点的子节点不直接相连）
我是从叶子节点往上求，像动态规划那样一层一层求最大值。
dp函数返回第一个是这个树的最大值，第二个是这个树的子节点和，如果这个树的最大值在叶子节点处取得就返回math.inf来标识
代码是这样的：
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # 帮助夏娃挑选苹果 # @param tree TreeNode类 苹果树 # @return int整型 # import math class Solution: def eating(self , tree ): # write code here def dp(root): if root==None: return 0, math.inf rootval = root.val lval,sublval = dp(root.left) rval,subrval = dp(root.right) if sublval == math.inf and subrval == math.inf: return rootval + lval + rval, lval+rval else: sub = lval+rval if sublval != math.inf and subrval!=math.inf: if rootval>sub: return rootval, sub else: return sub, math.inf elif sublval != math.inf: if rootval+sublval+rval>sub: return rootval+sublval+rval, sub else: return sub, math.inf elif subrval != math.inf: if rootval+subrval+lval>sub: return rootval+subrval+lval, sub else: return sub, math.inf ans,tmp = dp(tree) return ans
哔哩哔哩公司氛围 91人发布
查看5道真题和解析