乐趣区

关于leetcode:ARTS-第19周-LeetCode-51-N皇后问题-如何避免软件系统的过度设计

jiezi

ARTS

ARTS 是陈浩（网名左耳朵耗子）在极客工夫专栏里发动的一个流动，目标是通过分享的形式来保持学习。

每人每周写一个 ARTS：Algorithm 是一道算法题，Review 是读一篇英文文章，Technique/Tips 是分享一个小技术，Share 是分享一个观点。

本周内容

这周的 ARTS 你将看到:

  1. N 皇后网网红题.
  2. 什么是软件系统适度设计?

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 灵光一闪

实践学习只能晋升认知, 只有实际能力出真知.

退出移动版