文末彩蛋：七月在线干货组最新升级的《2021大厂最新AI面试题 [含答案和解析, 更新到前121题]》免费送！

问题1：算法题:leetcode 687.最长同值路径

方法：递归

可以将任何路径（具有相同值的节点）看作是最多两个从其根延伸出的箭头。具体地说，路径的根将是唯一节点，因此该节点的父节点不会出现在该路径中，而箭头将是根在该路径中只有一个子节点的路径。然后，对于每个节点，我们想知道向左延伸的最长箭头和向右延伸的最长箭头是什么？我们可以用递归来解决这个问题。

令 arrow_length(node) 为从节点 node 延伸出的最长箭头的长度。如果 node.Left 存在且与节点 node 具有相同的值，则该值就会是 1 + arrow_length(node.left)。在 node.right 存在的情况下也是一样。

当我们计算箭头长度时，候选答案将是该节点在两个方向上的箭头之和。我们将这些候选答案记录下来，并返回最佳答案。

代码如下：

时间复杂度： O(N)，其中 N 是树中节点数。

空间复杂度： O(H)，其中 H 是树的高度。

问题2：算法题:leetcode 322.零钱兑换

完全背包问题——填满容量为amount的背包最少需要多少硬币

dp[j]代表含义： 填满容量为j的背包最少需要多少硬币

初始化dp数组： 因为硬币的数量一定不会超过amount，而amount <= 10^4，因此初始化数组值为10001；dp[0] = 0

转移方程： dp[j] = min(dp[j], dp[j - coin] + 1)

当前填满容量j最少需要的硬币 = min( 之前填满容量j最少需要的硬币, 填满容量 j - coin 需要的硬币 + 1个当前硬币）

返回dp[amount]，如果dp[amount]的值为10001没有变过，说明找不到硬币组合，返回-1

代码如下：

\

时间复杂度： O(n * amount)

空间复杂度： O(amount)

评论区回复 “121”，七月在线干货组最新升级的《2021大厂最新AI面试题 [含答案和解析, 更新到前121题]》，免费送！

持续无限期更新大厂最新面试题，AI干货资料，目前干货组汇总了今年3月-6月份，各大厂面试题。