ARTS 是陈浩（网名左耳朵耗子）在极客时间专栏里发起的一个活动，目的是经过分享的方式来坚持学习。程序员
每人每周写一个 ARTS：Algorithm 是一道算法题，Review 是读一篇英文文章，Technique/Tips 是分享一个小技术，Share 是分享一个观点。
这周的 ARTS 你将看到:面试
本周的算法题是网红面试题 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
}
本周的文章推荐是关于软件架构中的过分设计的: 十个软件系统过分设计的例子.app
做者用他十五年的工做经验担保, 绝对不存在收敛的业务. 业务这玩意儿只可能愈来愈多, 愈来愈发散. 由于增加就是业务的本质特征, 不能怪业务方.工具
最好记住一点, 业务方永远是爸爸.学习
若是只是单纯的经过重用以前的逻辑来构建新的业务逻辑, 即, 在已有的公共逻辑基础上进行横向的扩展. 那么随着业务功能的增长, 系统会变得愈来愈复杂, 知道不可维护.设计
因此, 在依赖公共逻辑进行功能的横向扩展以前, 先对公共部分的逻辑作细分(或者叫纵向划分).code
程序员有时候会被写出优秀的抽象代码的愿望冲昏了头脑, 以致于为了抽象而抽象, 下降了代码的可读性却并无带来多少可维护性.
有时候, 错误的抽象还不如重复的代码堆叠.
对依赖库的封装必定要考虑更换依赖实现的可能, 同时不要在封装中掺杂具体的业务逻辑.
给每种对象都抽象除一个接口(或者抽象类), 或者盲目应用某些看似高级的语法特性. 无脑应用那些高级的软件设计原则, 这样的作法并不可取. 若是只是一个很是简单的小逻辑, 之后复用的可能几乎没有, 那么这种状况仍是把那些原则和方法忘掉吧. 这些概念不是普通的小工具, 只有场景合适才能发挥做用.
这点有些相似误区五种的意思, 没有场景空谈使用时没有意义的.
做者列出的一些 "ity" 的例子, Configurability, Security, Scalability, Maintainability, Extensibility.
落实这些概念以前, 必定要想一想目前系统的真实场景.
轮子造出来并非重点, 后期维护的成本也很是高, 决定作这件事情以前必定要想好.
重构是必然的结果, 不存在动不了的代码.
优秀的系统须要优秀的开发者和时间, 并且不管多优秀的开发者的开发速度都是有极限的, 又快又好是不存在的.
本周没有技巧...
理论学习只能提高认知, 只有实践才能出真知.