ARTS #43

Algorithm

本周选择的算法题是：Network Delay Time

规则如下：

There are N network nodes, labelled 1 to N.

Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.

Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.

Example 1:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
Output: 2

Note:

N will be in the range [1, 100].
K will be in the range [1, N].
The length of times will be in the range [1, 6000].
All edges times[i] = (u, v, w) will have 1 <= u, v <= N and 0 <= w <= 100.

Solution

我实现的方案：

Runtime：504 ms，快过 62.40%。

Memory：14.4 MB，低于 92.31%。

class Solution:
    def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
        queue, graph, dt = [(0, K)], collections.defaultdict(list), {}
        for u, v, w in times:
            graph[u].append((v, w))

        while queue:
            time, vertex = heapq.heappop(queue)
            if vertex not in dt:
                dt[vertex] = time
                for v, w in graph[vertex]:
                    heapq.heappush(queue, (time + w, v))

        time = max(dt.values())
        return time if len(dt) == N else -1

有向带权图的解法普遍采用 Dijkstra’s algorithm，此为优化后的版本。

原始版本：

class Solution:
    def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
        dt, graph, seen = {}, collections.defaultdict(list), {}
        for u, v, w in times:
            graph[u].append((v, w))
            dt[u], dt[v] = float('inf'), float('inf')
            seen[u], seen[v] = False, False
        if len(dt) < N: return -1
        dt[K] = 0
        while True:
            vertex, min_distance = 0, float('inf')
            for num in graph:
                if not seen[num] and dt[num] < min_distance:
                    min_distance, vertex = dt[num], num
            if vertex == 0: break
            seen[vertex] = True
            for v, w in graph[vertex]:
                dt[v] = min(dt[vertex] + w, dt[v])

        time = max(dt.values())
        return time if time != float('inf') else -1

可以看出优化主要是在寻找最小距离上。

再附上一个使用队列的版本：

class Solution:
    def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
        dt, graph, queue = {}, collections.defaultdict(list), [(0, K)]
        for u, v, w in times:
            graph[u].append((v, w))
            dt[u], dt[v] = float('inf'), float('inf')
        if len(dt) < N: return -1
        
        while queue:
            time, vertex = queue.pop(0)
            if time < dt[vertex]:
                dt[vertex] = time
                for v, w in graph[vertex]:
                    queue.append((time + w, v))

        time = max(dt.values())
        return time if time != float('inf') else -1

队列版本会存在重复计算的问题，但也是可以接受的答案。

Review

The Coordinator

Coordinators Redux

Coordinator 面向 View 层，能够很好地对 View 代码进行重新组织。其优势是：

ViewController 之间形成孤岛，专注于展示
ViewController 变得可重用
Coordinator 作为 View 的控制器，由事件/状态驱动，逻辑易于维护，完全可控
提高了可测试性
和路由是天生一对

Tip

Xcode 需要周期性更新，如果是 CI/CD 服务器得有自动化更新/部署的方案。

从 Apple Developer Portal 找指定的版本
获取 ADCDownloadAuth
用 aria2 下载
1. 通过 Homebrew 安装 aria2
2. 用这个 Ruby 脚本下载
使用 xip 在终端解压：
```
xip -x Xcode11.xip
```
删除并移动 Xcode 到 /Applications 目录下

关于 Thunk。

抽象的说，Thunk 是一种代码重定向技术，它不属于特定的语言或平台。

In computer programming, a thunk is a subroutine that is created, often automatically, to assist a call to another subroutine. Thunks are primarily used to represent an additional calculation that a subroutine needs to execute, or to call a routine that does not support the usual calling mechanism. They have a variety of other applications to compiler code generation and modular programming.
Thunk程序中文翻译为形实转换程序，简而言之Thunk程序就是一段代码块，这段代码块可以在调用真正的函数前后进行一些附加的计算和逻辑处理，或者提供将对原函数的直接调用转化为间接调用的能力。
Thunk程序在有的地方又被称为跳板(trampoline)程序，Thunk程序不会破坏原始被调用函数的栈参数结构，只是提供了一个原始调用的hook的能力。Thunk技术可以在编译时和运行时两种场景下被使用。
Thunk 程序的实现原理以及在 iOS 中的应用

是不是看着很像 AOP？我觉得 Thunk 和 AOP 主要是侧重点的不同：

Thunk 侧重于 Hook
AOP 侧重于模块化/能力

Algorithm

Solution

Review

Tip

Share