ARTS
ARTS 是陈浩（网名左耳朵耗子）在极客时间专栏里发起的一个活动，目的是通过分享的方式来坚持学习。
每人每周写一个 ARTS：Algorithm 是一道算法题，Review 是读一篇英文文章，Technique/Tips 是分享一个小技术，Share 是分享一个观点。
本周内容
这周的 ARTS 你将看到:
- N皇后网网红题.
- 什么是软件系统过度设计?
Algorithm
本周的算法题是网红面试题 N皇后问题: LeetCode 51 N-Queens.
这是一道非常经典的使用 回溯 + 剪支 的搜索类题目, 这道题虽然是 hard 难度, 但我感觉最难得地方在于想到使用深度优先搜索的方法.
下面是代码, 思路详见注释.
func solveNQueens(n int) [][]string {
ans := make([][]int, 0)
// 下面是回溯记忆操作, 用于剪支
// 因为每次回溯都按行 row 从上到下进行, 因此同一行的皇后互斥已经在回溯流程被排除了
// 只需要考虑列和两种对角线
col := make(map[int]struct{}, 0) // 代表列中是否已存在皇后
pie := make(map[int]struct{}, 0) // 代表撇(右上到左下)是否已存在皇后
na := make(map[int]struct{}, 0) // 代表捺(左上到右下)是否已存在皇后
queens := make([]int, 0)
// i 表示搜索进行到第 i 行
var dfs func(i int)
dfs = func(i int) {
if i == n {
// 这里必须对 queens 进行深拷贝, 否则后续回溯会影响 ans 中的结果
tmp := make([]int, len(queens))
copy(tmp, queens)
ans = append(ans, tmp)
}
for j := 0; j < n; j++ {
_, a := col[j]; _, b := pie[i+j]; _, c := na[i-j]
// 剪支
if !a && !b && !c {
col[j], pie[i+j], na[i-j] = struct{}{}, struct{}{}, struct{}{}
queens = append(queens, j)
dfs(i+1)
delete(col, j); delete(pie, i+j); delete(na, i-j)
// 因为底层数据没有变, 所以必须删除本次添加的元素, 后续回溯才能正常使用 queens
queens = queens[:len(queens)-1]
}
}
}
dfs(0)
return genMetric(ans, n)
}
func genMetric(ans [][]int, n int) [][]string {
ret := make([][]string, 0)
s := ""
for i := 0; i < n; i++ {
s += "."
}
for _, queens := range ans {
metric := make([]string, 0)
for _, q := range queens {
l := []byte(s)
l[q] = 'Q'
metric = append(metric, string(l))
}
ret = append(ret, metric)
}
return ret
}
Review 文章推荐
本周的文章推荐是关于软件架构中的过度设计的: 十个软件系统过度设计的例子.
- 误区一: 工程师比业务方更聪明.
作者用他十五年的工作经验担保, 绝对不存在收敛的业务. 业务这玩意儿只可能越来越多, 越来越发散. 因为增长就是业务的本质特征, 不能怪业务方.
最好记住一点, 业务方永远是爸爸.
- 误区二: 可重用的业务逻辑.
如果只是单纯的通过重用之前的逻辑来构建新的业务逻辑, 即, 在已有的公共逻辑基础上进行横向的扩展. 那么随着业务功能的增加, 系统会变得越来越复杂, 知道不可维护.
所以, 在依赖公共逻辑进行功能的横向扩展之前, 先对公共部分的逻辑做细分(或者叫纵向划分).
- 误区三: 一切皆泛型.
程序员有时候会被写出优秀的抽象代码的愿望冲昏了头脑, 以至于为了抽象而抽象, 降低了代码的可读性却并没有带来多少可维护性.
有时候, 错误的抽象还不如重复的代码堆叠.
- 误区四: 对第三方依赖库的封装器功能过于单一.
对依赖库的封装一定要考虑更换依赖实现的可能, 同时不要在封装中掺杂具体的业务逻辑.
- 误区五: 盲目使用所谓的高级特性和设计原则并不可取.
给每种对象都抽象除一个接口(或者抽象类), 或者盲目应用某些看似高级的语法特性. 无脑应用那些高级的软件设计原则, 这样的做法并不可取. 如果只是一个非常简单的小逻辑, 以后复用的可能几乎没有, 那么这种情况还是把那些原则和方法忘掉吧. 这些概念不是普通的小工具, 只有场景合适才能发挥作用.
- 误区六: 学会一样技能或者特性就想到处用.
这点有些类似误区五种的意思, 没有场景空谈使用时没有意义的.
- 误区七: 过于信奉各种 "ity".
作者列出的一些 "ity" 的例子, Configurability, Security, Scalability, Maintainability, Extensibility.
落实这些概念之前, 一定要想想目前系统的真实场景.
- 误区八: 谨慎对待企业内部造轮子.
轮子造出来并不是重点, 后期维护的成本也非常高, 决定做这件事情之前一定要想好.
- 误区九: 依赖系统现状却从不想重构.
重构是必然的结果, 不存在动不了的代码.
- 误区十: 过分高估自己和团队.
优秀的系统需要优秀的开发者和时间, 而且无论多优秀的开发者的开发速度都是有极限的, 又快又好是不存在的.
Tip 编程技巧
本周没有技巧...
Share 灵光一闪
理论学习只能提升认知, 只有实践才能出真知.
有疑问加站长微信联系（非本文作者）
