class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right # 提示: # 二叉树搜索:分别查找 node->left 和 node->right # 最长的路径长度包含左右两个方向之和 # 两个节点之间的路径长度由它们之间的边数表示 (节点数-1) # 用递归方式的dfs实现,不需要考虑运行效率 def longestPath(root): if not root: return 0 res = [0] def dfs(tree): if not tree: return 0 left_len, right_len = dfs(tree.left), dfs(tree.right) if tree.left and tree.left.val == tree.val: left = left_len + 1 else: left = 0 if tree.right and tree.right.val == tree.val: right = right_len + 1 else: right = 0 res[0] = max(res[0], left + right) return max(left, right) dfs(tree) return res[0] # testing cases tree = TreeNode(1, TreeNode(1, TreeNode(1)), TreeNode(1)) print(longestPath(tree)) tree = TreeNode(3, TreeNode(2, TreeNode(1), TreeNode(2)), TreeNode(3, None, TreeNode(3))) print(longestPath(tree)) tree = TreeNode(3, TreeNode(2, TreeNode(2), TreeNode(2)), TreeNode(4, None, TreeNode(4))) print(longestPath(tree))作业2. 数组连乘:给定一个整数数组A=[a0, a1, …, an-1],计算数组中乘积最大的连续子数组B=[ai, ai+1, …, aj]
# 提示:考虑数据全为正的情况, # 定义函数 f(n),表示以第n个数为结束点的子数列乘积最大值 # 递推关系为 f(n,k) = max(f(n-1) * A[n], A[n]) # 故返回f(n)中最大的一个 # 进一步,如果有整数也有负数,可以维护一个n点结束的最正乘积和最负乘积 # TODO: input a list[int], return a list[int] def subArrayMul(a): if not a: return 0 ans = a[0] pre_max = a[0] pre_min = a[0] for num in a[1:]: cur_max = max(pre_max * num, pre_min * num, num) cur_min = min(pre_max * num, pre_min * num, num) ans = max(cur_max, ans) pre_max = cur_max pre_min = cur_min return ans # testing cases a1 = [4, 3, 1, 10, -1, 10, 1, -2, 5, -5, 3, 4] print(subArrayMul(a1)) a2 = [1, 2, -2, 5, -1, -1, 5, 4] print(subArrayMul(a2)) a3 = [2, -2, -1, 10, -1, -5, 4] print(subArrayMul(a3))
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)