ARTS
ARTS 是陈浩（网名左耳朵耗子）在极客时间专栏里发起的一个活动，目的是通过分享的方式来坚持学习。
每人每周写一个 ARTS：Algorithm 是一道算法题，Review 是读一篇英文文章，Technique/Tips 是分享一个小技术，Share 是分享一个观点。
本周内容
本周的 ARTS 你将看到：
- 两道 LeetCode 字符匹配题。
- 关于 Redis 副本 replication 的一些细节。
- Go defer 在回溯问题记忆化中的一个小技巧。
- 文字和视频是否会影响内容的深度？
Algorithm
本周的算法题是两道关于字符串匹配的题目，LeetCode 10.regular-expression-matching 和 LeetCode 44.wildcard-matching.
这两道字符串匹配的题目是非常典型的动态规划题，因此也就是非常典型的回溯题（手动狗头）。如果你还没有做过的话，建议先做 44 题再做第 10 题，因为难度上前者要低很多。具体解释都在注释里，如果有任何问题欢迎评论。
首先是 44.wildcard-matching
/*
* @lc app=leetcode id=44 lang=golang
*
* [44] Wildcard Matching
*/
// @lc code=start
// dp[i][j] 表示 s 和 p 中长度为 i 和 j 的前缀子串能匹配
// 平平无奇动态规划 12 ms, faster than 75.47%
func isMatch(s string, p string) bool {
ls, lp := len(s), len(p)
dp := make([][]bool, ls+1)
for i := range dp {
dp[i] = make([]bool, lp+1)
}
dp[0][0] = true
for j := 0; j < lp; j++ {
if p[j] == '*' {
dp[0][j+1] = true
} else {
break
}
}
for i := 1; i <= ls; i++ {
for j := 1; j <= lp; j++ {
if p[j-1] == '*' {
// * 匹配空串，* 匹配任意一个字符，* 匹配多个字符
dp[i][j] = dp[i][j-1] || dp[i-1][j-1] || dp[i-1][j]
}
if p[j-1] == '?' || p[j-1] == s[i-1] {
dp[i][j] = dp[i-1][j-1]
}
}
}
return dp[ls][lp]
}
// 回溯+记忆 316 ms, faster than 16.04%
func isMatch_Backtracking(s string, p string) bool {
ls, lp := len(s), len(p)
mem := make(map[[2]int]bool, 0) //不加记忆就超时
var f func(sc, pc int) bool
f = func(sc, pc int) (ans bool) {
if ret, ok := mem[[2]int{sc, pc}]; ok {
return ret
}
// 我竟然写出了 Golang 风格的记忆化！
// 这里注意一下 ans 和 mem 都是通过闭包方式引用传递
defer func() {
mem[[2]int{sc, pc}] = ans
}()
if sc == ls && pc == lp {
ans = true
return
}
if pc == lp {
ans = false
return
}
if p[pc] == '*' {
// * 匹配空串，* 匹配任意一个字符，* 匹配多个字符
if sc < ls {
ans = f(sc, pc+1) || f(sc+1, pc+1) || f(sc+1, pc)
} else {
ans = f(sc, pc+1)
}
return
}
if sc < ls && (p[pc] == '?' || p[pc] == s[sc]) {
ans = f(sc+1, pc+1)
return
}
return
}
return f(0, 0)
}
// @lc code=end44 题还是比较简单的，只要注意 * 号可以匹配空白，单个字符和多个字符就可以了。下面来看下 10.regular-expression-matching.
/*
* @lc app=leetcode id=10 lang=golang
*
* [10] Regular Expression Matching
*/
// @lc code=start
// 测试例中不允许 * 号开头，可以不考虑这种 corner case
// 而且实际上以 * 号开头也不符合 * 号本身的定义
// DP
func isMatch(s string, p string) bool {
ls, lp := len(s), len(p)
// dp[i][j] 表示 s[:i] 能被 p[:j] 匹配，表示的是长度为 i j
// 也可以理解成 s 和 p 的下标从 1 开始算，0 表示空串
// 这样设定的原因是什么我也不知道
dp := make([][]bool, ls+1)
for i := 0; i <= ls; i++ {
dp[i] = make([]bool, lp+1)
}
// base case
dp[0][0] = true
for j := 0; j < lp; j++ {
if p[j] == '*' && dp[0][j-1] {
dp[0][j+1] = true
}
}
// j = 0 且 i != 0 肯定是 false
for i := 1; i <= ls; i++ {
for j := 1; j <= lp; j++ {
if p[j-1] == s[i-1] || p[j-1] == '.' {
dp[i][j] = dp[i-1][j-1]
}
if p[j-1] == '*' {
if p[j-2] != s[i-1] {
dp[i][j] = dp[i][j-2]
}
if p[j-2] == s[i-1] || p[j-2] == '.' {
// dp[i-1][j] 表示 * 号匹配多个其左侧的字符，这是最难理解的
// 匹配多个 * 左侧字符的问题等价于查看 s 中与 * 左侧字符相同且连续的字符有几个
// 如果有多个连续的该字符，那么如果 s[i-1] 是比较靠后的几个的话
// 那么通过 dp[i-1][j] 中对 i 向“左移”可以等效的看做 j 匹配了多个 * 左侧的字符
// 比如 aaabc 和 a*bc
// * 匹配到第三个 a 时，通过转换到依赖前几个 a 的匹配结果，相当于重复使用了 * 左侧的 a
// （接上句）因为如果 i-1 能和当前 j 指向的 * 号匹配，那么 i 也能
// （接上句）因为 * 左侧字符和 s 中重复字符相同
// 确实很难理解，不行就靠记忆吧
dp[i][j] = dp[i][j-2] || dp[i][j-1] || dp[i-1][j]
}
}
// 既不相等又不是 * 号的话那就是 false 不用设定这样的 dp[i][j]（默认为 false）
}
}
return dp[ls][lp]
}
// Backtracking
func isMatch_BackTracking(s string, p string) bool {
ls, lp := len(s), len(p)
var f func(sc, pc int) bool
f = func(sc, pc int) bool {
if sc == ls && pc == lp {
return true
}
if pc == lp {
return false
}
if p[pc] == '*' {
var use0P, use1OrMoreP bool
// 正常情况 * 号不会出现在第一个字符位置
// sc < ls 这个条件是因为可能 s 已经走到结尾但是 p 还没有到结尾
// 这时候还是需要继续移动 p 的位置 pc，但不需要再比较 s[sc] 了
// 因为 sc 结束不是真的结束，需要等到 p 也结束
if pc > 0 && sc < ls && (p[pc-1] == s[sc] || p[pc-1] == '.') {
use1OrMoreP = f(sc+1, pc) || f(sc+1, pc+1)
}
use0P = f(sc, pc+1)
return use0P || use1OrMoreP
}
var eq, bfStar bool
if sc < ls && (p[pc] == s[sc] || p[pc] == '.') {
eq = f(sc+1, pc+1)
}
if pc+1 < lp && p[pc+1] == '*' {
bfStar = f(sc, pc+2)
}
return eq || bfStar
}
return f(0, 0)
}
// Backtracking with memo 100%
func isMatch_BackTrackingWithMemory(s string, p string) bool {
ls, lp := len(s), len(p)
var f func(sc, pc int) bool
mem := make(map[[2]int]bool, 0)
f = func(sc, pc int) bool {
if ret, ok := mem[[2]int{sc, pc}]; ok {
return ret
}
if sc == ls && pc == lp {
return true
}
if pc == lp {
return false
}
if p[pc] == '*' {
var use0P, use1OrMoreP bool
// 正常情况 * 号不会出现在第一个字符位置
if pc > 0 && sc < ls && (p[pc-1] == s[sc] || p[pc-1] == '.') {
use1OrMoreP = f(sc+1, pc) || f(sc+1, pc+1)
}
use0P = f(sc, pc+1)
mem[[2]int{sc, pc}] = use0P || use1OrMoreP
return use0P || use1OrMoreP
}
var eq, bfStar bool
if sc < ls && (p[pc] == s[sc] || p[pc] == '.') {
eq = f(sc+1, pc+1)
}
if pc+1 < lp && p[pc+1] == '*' {
bfStar = f(sc, pc+2)
}
mem[[2]int{sc, pc}] = eq || bfStar
return eq || bfStar
}
return f(0, 0)
}
// @lc code=end第 10 题我认为其实回溯反而好理解一些，用动态规划确实时间上要快，但是也更加难理解。尤其是 * 号匹配多个时用dp[i-1][j]来表示这一点，对我来说是很不好理解的一个点。另外就是这两道题如果用回溯的话，记忆化的代码看起来很恶心，需要在每个 return 的位置都加上写 map. 如何优雅一点的实现记忆化呢？这时候 Go 的优势可以体现出来了，这点作为本周的一个技巧放在 Tips 里了。
Review 文章推荐
本周英文文章是 Redis 官方对备份（Replication）功能的介绍：Replication。
这算是一篇官网的科普文章，内容主要包括 Redis 备份功能的基本介绍和使用注意事项，像下面是我认为文中比较重要的一些内容。
- 同步请求由 master 负责想已连接的副本(Replica)实例发起，支持一主多从。
- 主从同步默认使用异步的方式，但也可以使用
WAIT命令让 master 等待 replica 执行当前的备份完成。 - 备份功能不会阻塞 master 的读写请求。
- 但 replica 实例在处理新老数据替换时会有短暂的拒绝请求窗口期。
- 备份功能可以用于实现高可用和读写分离。
- 对于关闭了持久化内存数据到磁盘的 master，重启 Redis 可能造成 replica 实例获取到空备份。
- master 节点负责维护一个
Replication ID和offset的组合来指明当前 master 节点和备份数据的偏移量。 -
Replication ID和offset能够唯一标识备份数据。 - 为了防止出现多个 master 共存导致 8 中的规定失效，当新的 master 被选中后会生成一个新的
Replication ID同时也会将旧的Replication ID作为 secondaryReplication ID保留下来应对某些 replica 节点依旧使用旧的Replication ID的情况。 - 支持读写分离，可以将一个 replica 配置为只读，也可以配置 master 在拥有一定 replica 实例数量且延迟不低于设定值时才可写。
-
replica 实例的 expire 功能不依赖其与 master 的时钟同步，其 expire 通过下面三种方式保证：
- replica 不主动 epxire 一个 key，master 侧 expire 后会向 replica 发送
DEL命令。 - replica 在本地会通过对比时钟来检查已经 expire 的 key，如果该 key 还没有收到来自 master 的
DEL的话，replica 会禁止读请求。 - Lua 脚本执行期间不对 expire 进行处理。
- replica 不主动 epxire 一个 key，master 侧 expire 后会向 replica 发送
Tip 编程技巧
在上面说到的 LeetCode 10 和 44 题中记忆化的一个小技巧就是使用 defer 和命名返回值。
使用命名返回值之后只需要在每个 return 之前给返回值赋值就可以，不需要为了记忆化在每个 return 之前都更新记忆化用的 map. 但是我们在合理的位置加入 defer 来统一的把返回值更新到记忆化 map 中去。详见下面的代码片段。
f = func(sc, pc int) (ans bool) {
if ret, ok := mem[[2]int{sc, pc}]; ok {
return ret
}
// 这里注意一下 ans 和 mem 都是通过闭包方式引用传递
defer func() {
mem[[2]int{sc, pc}] = ans
}()
if sc == ls && pc == lp {
ans = true
return
}
...
}Share 灵光一闪
视频和文字这两种知识内容的载体本身，会对学习效果产生影响吗？
- 文字的优势是方便快速查找定位，视频的优势是更生动形象，作者和读者之间的理解能力间隙更小，对想象力要求低很多。
文字可能更适合读者在获得内容的同时进行思考，更适合学习需要深入理解的东西。
有疑问加站长微信联系（非本文作者）
