CodingTour
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:

img

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:

img

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

一篇关于如何学习软件架构设计的文章,作者给了软件一个非常容易理解的定义:软件的目标是不断生产满足用户需求的产品,同时最大限度地减少为此付出的努力。

给出的 “学习地图” 很棒,分为八类:

  1. 学习如何写出 clean code
  2. 理解不同的编程范式以及为什么 OOP 对架构更有益
  3. 用模型驱动设计的理念重新学习面向对象编程
  4. 学习面向对象的设计原则,保持代码的弹性和可测试性
  5. 学习解决常见问题的设计模式以及如何在 class 级应用它们
  6. 学习如何管理组件之间的关系、表达策略和识别架构边界
  7. 学习将代码组织为高级模块的不同方式以及定义它们之间的关系
  8. 学习用不同的架构模式解决问题

整体观点精炼,值得一读。

Tip

一个面向开发者每日一读的产品:daily.dev

Share

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

大宝看小宝

以后就是四口之家了~