ARTS #184 | 以后就是四口之家了

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。

11号晚上看世界杯到凌晨，随着葡萄牙被淘汰，我老婆的身体也有反应了，紧接着去医院，果然生了，来的就是这么突然，“忽如一夜春风来，千树万树梨花开” 大概就是这种感觉~

大宝看小宝

以后就是四口之家了~

Algorithm

规则

Solution

Review

Tip

Share