乐趣区

关于leetcode:ARTS-第15周-LeetCode-最长回文子序列-来自-Uber-的-Go-编程规范

jiezi

ARTS

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

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

本周内容

本周的 ARTS 你将看到:

  1. LeetCode 516 最长回文子序列.
  2. 来自 Uber 的 Golang 编程标准.

Algorithm

本周的算法题是 LeetCode 516.longest-palindromic-subsequence, 最长回文子序列.

回文序列和会问字符串的最大区别就是 序列 是能够不间断的, 然而 串必须是间断的.

所以这道题和之前第 5 题最长回文子串的区别就很显著了, 或者说这道题要求更加宽泛一些.

// 没错我就是抄答案的 https://leetcode-cn.com/problems/longest-palindromic-subsequence/solution/zi-xu-lie-wen-ti-tong-yong-si-lu-zui-chang-hui-wen/
// dp[i][j] 代表 s 的下标冲 i 到 j 范畴内的回文子序列长度
// base case: dp[i][i] 代表一个字符肯定是回文子序列
func longestPalindromeSubseq(s string) int {l := len(s)
    dp := make([][]int, l)
    for i := range dp {dp[i] = make([]int, l)
    }
    for i := 0; i < l; i++ {dp[i][i] = 1
    }

    for i := l - 1; i >= 0; i-- {
        for j := i + 1; j < l; j++ {if s[i] == s[j] {dp[i][j] = dp[i+1][j-1] + 2
            } else {dp[i][j] = max(dp[i+1][j], dp[i][j-1])
            }
        }
    }

    return dp[0][l-1]
}

func max(a, b int) int {
    if a > b {return a}
    return b
}

Review 文章举荐

本周举荐的英文文章是 Uber 公开的外部 Golang 编程标准.

这个标准包含一些 Golang 的编程技巧和常规, 也包含一些代码格局这种更加外表一些的标准. 上面是我认为比拟重要的一些点.

  1. 应用 golint 和 go vet 命令.
  2. 依赖编译对 interface 的实现类型进行判断.
  3. 留神谬误的类型和封装.
  4. 如果应用原子操作但又感觉官网包太捡漏的话, 能够试试 Uber 对原子操作的封装.
  5. 少用全局变量.
  6. 少用匿名组合, 因为匿名组合不得不裸露匿名属性的封装细节, 须要留神的中央比方这些.
  7. 尽量少用 init() 来做初始化的工作.
  8. 用 strconv 代替 Sprintf 来做 string 类型转换.
  9. 少用 string 到 []byte 的类型转换.
  10. 应用 make 创立 slice 和 map 时最好指定 capacity.
  11. 应用小写和复数模式明明 package.
  12. 不对外裸露的包内全局变量, 最好用下划线 _ 结尾.
  13. 应用 if len(s) == 0 而不是 if s == nil 来判断 slice 是否为空
  14. 少用裸参数(字面量参数?)
  15. 多用反单引号包裹的原生字符串来逃逸特殊符号.
  16. 应用打表的形式组建单元测试的数据.
  17. 应用变长函数数组作为配置类型的可选参数

Tip 编程技巧

本周没有技巧.

Share 灵光一闪

本周也没有灵光.

本周浏览列表

  • Go 语言设计与实现 6.5 调度器

    1. Go 携程调度三个角色 GMP
      G 构造中蕴含 stack 相干信息，还有与协程抢占式调度相干的字段 stackguard0，defer 和 -panic 链表。还包含以后 G 占用的线程，调度器相干数据 sched 以及 goid 等等。
      M 中蕴含的字段比拟重要的有 g0 和 currg，其中 g0 代表持有调度栈的 G 他会深度参加协程的调度, curg 是在以后线程上运行的用户 G, 这也是操作系统线程惟一关怀的两个 Goroutine. 除此之外还有在运行代码的处理器 p、暂存的处理器 nextp 和执行零碎调用之前的应用线程的处理器 oldp.
      P 的数量通过 GOMAXPROCS 设置，最多只会有 GOMAXPROCS 个沉闷的操作系统线程可能失常运行. P 是线程和 Goroutine 的中间层, 也会负责调度线程上的期待队列. 它能在 Goroutine 进行一些 I/O 操作时及时切换, 进步线程的利用率. P 自身也有 status 字段代表其状态, 比方 _Pidle 代表 P 上的 G 队列为空, _Prunning 代表正在执行用户代码, _Pgcstop 代表 P 被 GC 进行, 等等.
  • golang 自动检测死锁 deadlock 的实现
    一个用于检测死锁的工具, 实现形式就是封装了 Go 的 sync 库的锁, 而后在每次加锁前检测是否有可能死锁.
退出移动版