Algorithm
本周选择的算法题是:Maximum Difference Between Node and Ancestor。
规则
Given the root
of a binary tree, find the maximum value v
for which there exist different nodes a
and b
where v = |a.val - b.val|
and a
is an ancestor of b
.
A node a
is an ancestor of b
if either: any child of a
is equal to b
or any child of a
is an ancestor of b
.
Example 1:
Input: root = [8,3,10,1,6,null,14,null,null,4,7,13]
Output: 7
Explanation: We have various ancestor-node differences, some of which are given below :
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
Among all possible differences, the maximum value of 7 is obtained by |8 - 1| = 7.
Example 2:
Input: root = [1,null,2,null,0,3]
Output: 3
Constraints:
- The number of nodes in the tree is in the range
[2, 5000]
. 0 <= Node.val <= 105
Solution
class Solution:
def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
ans = [0]
self.traverse(root, root.val, root.val, ans)
return ans[0]
def traverse(self, root, low, high, ans):
if not root: return 0
ans[0] = max(ans[0], abs(root.val-low), abs(root.val-high))
self.traverse(root.left, min(low, root.val), max(high, root.val), ans)
self.traverse(root.right, min(low, root.val), max(high, root.val), ans)
Review
How to Learn Software Design and Architecture
一篇关于如何学习软件架构设计的文章,作者给了软件一个非常容易理解的定义:软件的目标是不断生产满足用户需求的产品,同时最大限度地减少为此付出的努力。
给出的 “学习地图” 很棒,分为八类:
- 学习如何写出 clean code
- 理解不同的编程范式以及为什么 OOP 对架构更有益
- 用模型驱动设计的理念重新学习面向对象编程
- 学习面向对象的设计原则,保持代码的弹性和可测试性
- 学习解决常见问题的设计模式以及如何在 class 级应用它们
- 学习如何管理组件之间的关系、表达策略和识别架构边界
- 学习将代码组织为高级模块的不同方式以及定义它们之间的关系
- 学习用不同的架构模式解决问题
整体观点精炼,值得一读。
Tip
一个面向开发者每日一读的产品:daily.dev。
Share
11号晚上看世界杯到凌晨,随着葡萄牙被淘汰,我老婆的身体也有反应了,紧接着去医院,果然生了,来的就是这么突然,“忽如一夜春风来,千树万树梨花开” 大概就是这种感觉~
大宝看小宝
以后就是四口之家了~