ARTS #79

Algorithm

646. 最长数对链

func findLongestChain(pairs [][]int) int {
    sort.Slice(pairs, func(i, j int) bool {
        if pairs[i][0] < pairs[j][0] {
            return true
        } else if pairs[i][0] == pairs[j][0] {
            return pairs[i][1] >= pairs[j][1]
        } else {
            return false
        }
    })
    length := len(pairs)
    dp := make([]int, length)
    dp[0] = 1
    result := 1
    for i := 1; i < length; i++ {
        count := 1
        for j := i - 1; j >= 0; j-- {
            if pairs[i][0] > pairs[j][1] {
                count = dp[j] + 1
                break
            }
        }
        dp[i] = count
        if count > result {
            result = count
        }
    }
    return result
}

Review

NA

TIP

这周工作过程需要在本地环境运行不同go版本进行编译问题定位，所以了解了下如何安装不同go版本官方的 Go 多版本管理：使用和原理：

$ go get golang.org/dl/go<version>      // 其中 <version> 替换为你希望安装的 Go 版本
$ go<version> download          // 和上面一样，<version> 是具体的版本

Share

这周了解了下无锁并发编程的底层原理：

• 一般我们使用的mutex属于加锁并发编程，是高级语言标准库调用操作系统锁机制（关中断、自旋锁、信号量）来实现互斥锁（mutex）的底层原理是什么？ 操作系统具体是怎么实现的？？，加锁操作性能比较差。
• 如果想要获得更好的并发性能，可以尝试通过并发原理 — CPU原子性指令（一）操作进行无锁并发编程。底层原理就是通过总线加锁、缓存行加锁、原子性指令等方式实现。