ARTS 第二周

Algorithm

一个机器人位于一个 m x n网格的左上角。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。
说明：*m 和 n*的值均不超过 100。
示例 1:
1
2
3
4
5
6
7
8
9
10
11
12
输入:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

思路：
本题是一道动态规划问题，从这类问题的解法考虑，首先应寻找最优子结构，然后写出状态转义方程并将其翻译为代码。
在本题中，最优子结构应是每个格子的不同可达路径数，边界条件为第一行和第一列中每个格子的可达路径数，因为其中的每个格子都可根据左一个或上一个格子直接得出，而最关键的状态转义方程应为：格子的路径数 = 上一个格子的路径数 + 左一个格子的路径数
注：矩阵默认保存的数据为 0 或 1 即表示是否有障碍，但经算法遍历填充后为每个格子的不同路径数

解答：

class Solution {
    func uniquePathsWithObstacles(_ obstacleGrid: [[Int]]) -> Int {
        var grid = obstacleGrid
        let column = obstacleGrid.count
        let row = obstacleGrid[0].count
        
        guard obstacleGrid[0][0] == 0 else { return 0 }
        grid[0][0] = 1

        for i in 1..<column {
            grid[i][0] = (grid[i][0] == 0 && grid[i-1][0] == 1) ? 1 : 0
        }

        for i in 1..<row {
            grid[0][i] = (grid[0][i] == 0 && grid[0][i-1] == 1) ? 1 : 0
        }

        for c in 1..<column {
            for r in 1..<row {
                if grid[c][r] == 0 {
                    grid[c][r] = grid[c-1][r] + grid[c][r-1]
                } else {
                    grid[c][r] = 0
                }
            }
        }

        return grid[column-1][row-1]
    }

Review

Explaining the WebRTC Secure Real-Time Transport Protocol (SRTP)

本周在准备分享有关 WebRTC 的内容，之前对于 WebRTC 的协议栈并没有做过深入了解，正好趁此机会做一次补充。

本篇文章从 SRTP 协议入手，介绍了 RTP 协议栈的组成，以及 WebRTC 所使用的加密协议等。

SRTP (Secure Real-Time Transport Protocol) 协议是对 RTP 协议的拓展并提供了一系列的加密机制，以提升 RTP 协议的安全性。包括对 RTC 包的加密、数据源认证、密钥管理等。

SRTP 使用 AES （一种被广泛应用的对称加密算法）作为数据加密算法，包含两种加密模式：Segmented Integer Counter Mode 和 f8-mode。

对于消息完整性的保证，SRTP 使用算法为数据包和部分包头创建认证标识（authentication tag），并将其添加到 RTC 包上。该标识用于数据包内容的验证以防止数据伪造。同时，认证还通过为每个数据包提供可序列可比较的下标以防止回复攻击。在 WebRTC 中，SRTP 为保证消息完整性使用了 HMAC-SHA1 算法。

为保障每个 session 的安全性，SRTP 使用密钥派生函数，基于 master key 生成一些派生 keys ，对每个独立 session 使用唯一的 key 以保证 session 的安全。

WebRTC 通过 SRTP-DTLS 协议以保证流的安全性，其中，SRTP 用于媒体流的加密，DTLS 用于用于数据流的加密。

Tip

本周记录一下 Swift 5.2 在语言特性上的更新，本次的两个更新都与函数相关，函数在 Swift 中的地位和作用是非常重要的

函数式的类型调用
无论在类、结构体还是协议中，如果想以函数式的调用方式来调用对象，进而调用对象中的某个方法，可以通过在类型中声明方法：callAsFunction()来做到，以class为例：

class Car {
	var color: UIColor = .white
	var mileAge: UInt = 0
	. . .
	func info(_ band: String) {
		. . .
	}
}

extension Car {
	func callAsFunctions(_ band: String) {
		info(band)
	}
}

let car = Car()
// call as func
car(“BMW”)

使用 key paths 作为函数
在 Swift5.2 中，可使用 key path 作为函数传参：

let fruits: [Fruit] = . . .

// before
fruites.map{ $0.color }

// after
fruites.map(\.color)

为什么流媒体直播的延迟很高

在本周公司内部分享 WebRTC 时被同事问到 WebRTC 与 HLS 的区别，我的理解是从底层的协议到框架的设计和目标应用场景均有不同，前者的目标是点对点的实时通讯，而后者被设计为流媒体传输协议。但 WebRTC 也可被应用到直播场景中，需要额外搭建服务通讯模型。两者在直播场景下的表现如何还需深入了解。

本文从流媒体直播的链路入手分析，分析数据编码、数据传输、缓存等方面可能造成延迟的原因。对了解流媒体直播的链路有一定的帮助。

Algorithm

Review

Tip

Share