winymu / arts Goto Github PK

算法，主要是以下几种：
基础技巧：分治、二分、贪心
排序算法：快速排序、归并排序、计数排序
搜索算法：回溯、递归、深度优先遍历，广度优先遍历，二叉搜索树等
图论：最短路径、最小生成树
动态规划：背包问题、最长子序列

数据结构，主要有如下几种：
数组与链表：单 / 双向链表
栈与队列
哈希表
堆：最大堆 ／ 最小堆
树与图：最近公共祖先、并查集
字符串：前缀树（字典树） ／ 后缀树

在公司内部引入Go语言的三个步骤:

• https://superhighway.dev/piloting-go

1. 深入地理解Go
2. 鼓励同事去玩Go，并解决他们遇到的问题
3. 做一些case: 用case说服产品主管、技术leader使用Go开发真的可以提高效率

Go语言中的生成器、wait group和闭包

• https://www.acim.net/generators-waitgroups-closures-golang
  使用function编程，针对统一形式的可变option参数，是很好的应用

KMP算法核心：

1. 在不匹配时，尽可能低减少"匹配index"的回退；
2. 需要利用“前缀”、“后缀”最长匹配，生成部分匹配Next数组，算法关键是求解Next数组
3. 移动位数 = 已匹配的字符数 - 对应的部分匹配值

"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例，
－　"A"的前缀和后缀都为空集，共有元素的长度为0；
－　"AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；
－　"ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；
－　"ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；
－　"ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A"，长度为1；
－　"ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为2；
－　"ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。

func TestKmpNext(t *testing.T) {
	str := `agctagcagctagctg`
	// str := `aaaaaaaa`
	L := len(str)
	next := make([]int, L)
	for i := 1; i < L; i++ {
		// 首先检查当前元素i的 next[i] 的值
		// 如果为0表示前面的字符串中就没有“前缀” == “后缀”
		if next[i-1] == 0 {
			// 从头开始，检查与第一个字符是否相等，相等则有一个匹配
			if str[i] == str[0] {
				next[i] = 1
			}
		} else { // 前面的字符串中就出现了“前缀” == “后缀”， 则next[i-1] ！=0
			if str[i] == str[next[i-1]] {
				next[i] = next[i-1] + 1
			} else if str[i] == str[0] {
				next[i] = 1
			}
		}
	}
	fmt.Println("next:", next)
}

innodb引擎自增主键非连续的原因：

1. 唯一键冲突
2. 申请到主键后回滚
3. insert...select 语句批量申请（后一次申请的是前一次的2倍）的主键id，会有浪费

Mysql的Join过程及优化

重温OAuth2.0
http://www.ruanyifeng.com/blog/2019/04/oauth-grant-types.html

1. 授权码。安全性最高，微信支付使用
2. 隐藏式。没有code授权机制，直接返回token，URL锚点形式
3. 密码式。毫无安全性
4. 凭证式。命令行使用，通过appid和appSecret申请token，授权范围为第三方应用，不能像授权码方式可以授权个人