ARTS Week 17

人根本沒辦法在不喜歡的事物上努力啊。

Algoithm

二叉樹的右視圖

概述

給定一棵二叉樹，想象自己站在它的右側，按照從頂部到底部的順序，傳回從右側所能看到的節點值。

示例:

輸入: [1,2,3,null,5,null,4]
輸出: [1, 3, 4]
解釋:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---
           

分析

1. 先遞歸擷取其深度。
2. 同步狀态修改。

codeing

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution(object):
    def rightSideView(self, root):
        # 使用棧的方式進行資料的整體的周遊，實作了層序的周遊
        rightmost_value_at_depth = dict()  # 深度為索引，存放節點的值
        max_depth = -1

        stack = [(root, 0)]
        while stack:
            node, depth = stack.pop()

            if node is not None:
                # 維護二叉樹的最大深度
                max_depth = max(max_depth, depth)

                # 如果不存在對應深度的節點我們才插入
                rightmost_value_at_depth.setdefault(depth, node.val)

                stack.append((node.left, depth + 1))
                stack.append((node.right, depth + 1))

        return [rightmost_value_at_depth[depth] for depth in range(max_depth + 1)]


           

Review

Microservices Design - API Gateway Pattern

概述

“Microservice is a tightly scoped, strongly encapsulated, loosely coupled, independently deployable, and independently scalable application component.”

• Each microservice can be deployed, upgraded, scaled, maintained, and restarted independent of sibling services in the application.
• Agile development & agile deployment with an autonomous cross-functional team.
• Flexibility in using technologies and scalability.

API Gateway

Tip

實戰：“畫圖程式” 的整體架構

全局性功能的架構設計

概述

系統侵入計算方式

畫圖代碼

計算方式：

比如某個接口方法被 N 個周邊子產品引用，那麼每個周邊子產品分擔的傷害值為 1/N。

全局性功能設計

任何功能都是可以正交分解的，即使我目前還沒有找到方法。

業務分解就是最小化的核心系統，加上多個正交分解的周邊系統。核心系統一定要最小化，要穩定。堅持不要往核心系統中增加新功能，這樣你的業務架構就不可能有臭味

Share

樹結構常用算法總結

leetcode 樹

概述

二叉樹常用解法的總結

樹

樹是一種抽象資料類型（ADT）或是實作這種抽象資料類型的資料結構，用來模拟具有樹狀結構性質的資料集合。它是由 n(n>0)n(n>0) 個有限節點組成一個具有層次關系的集合。

把它叫做「樹」是因為它看起來像一棵倒挂的樹，也就是說它是根朝上，而葉朝下的。

它具有以下的特點：

• 每個節點都隻有有限個子節點或無子節點；
• 沒有父節點的節點稱為根節點；
• 每一個非根節點有且隻有一個父節點；
• 除了根節點外，每個子節點可以分為多個不相交的子樹；
• 樹裡面沒有環路。

遞歸

遞歸方式總結

1. 确定終止條件
2. 确定每一個節點可能的情況
3. 确定遞歸的順序

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def recursive(self, root):
        # 遞歸方式同步，大部分的題目
        
        # root.val 節點的判斷
        
        self.recursive(root.left)
        self.recursive(root.right)