算法

前缀树

前缀树又称字典树 Trie的应用自动补全,例如：在百度搜索的输入框中,输入一个单词的前半部分,能够自动补全出可能的单词结果。拼写检查，例如：在word中输入一个拼写错误的单词, 能够自动检测出来。 IP路由表，在IP路由表中进行路由匹配时, 要按照最长匹配前缀的原则进行匹配。 T9预测文本，在大多手机输入法中, 都会用9格的那种输入法. 这个输入法能够根据用户在9格上的输入,自动匹配出可能的单词。填单词游戏，相信大多数人都玩过那种在横竖的格子里填单词的游戏。

Thursday, August 12, 2021 阅读

排序算法

归并排序思想整体是递归（当然可以用非递归实现），使左边有序，使右边有序，合并左边右边使整体有序具体实现核心代码 func merge(arr []interface{}, l, mid, r int, compare Compare) { help := make([]interface{}, r-l+1) i := 0 p1 := l p2 := mid + 1 for p1 <= mid && p2 <= r { if compare(arr[p1], arr[p2]) { help[i] = arr[p1] p1++ } else { help[i] = arr[p2] p2++ } i++ } //要么p1越界了，要么p2越界了 for p1 <= mid { help[i] = arr[p1] i++ p1++ } for p2 <= r { help[i] = arr[p2] i++ p2++ } for j, _ := range help { arr[l+j] = help[j] } } 递归核心代码

Saturday, August 7, 2021 阅读