File system-based deduplication File system-based deduplication is a simple method to reduce duplicate data at the file level, and usually is just a compare operation within the file system or a file system-based algorithm that eliminates duplicates. An example of this method is comparing the name, size, type and date-modified information of two files with… Continue reading file deduplication
Category: algorithm
kmp匹配字符串
kmp算法常用于优化字符串匹配，例如下面的问题： 有一个字符串a = “BBC ABCDAB ABCDABCDABDE”，我想知道，里面是否包含另一个字符串b = “ABCDABD” 一般的做法是循环比较。 func contain(a string, b string) bool { for i := 0; i < len(a); i++ { k := i for j := 0; j < len(b); { if b[j] == a[k] { if j == len(b)-1 { return true } j++ k++ } else {… Continue reading kmp匹配字符串
堆排序
关键：k[i]>=k[2i]&&k[i]>=k[2*i+1] 父节点大于子节点这是大根堆。 堆可以被看成是一棵树，结点在堆中的高度可以被定义为从本结点到叶子结点的最长简单下降路径上边的数目；定义堆的高度为树根的高度。我们将看到，堆结构上的一些基本操作的运行时间至多是与树的高度成正比，为O（lgn） 利用堆排序，分两步： 1构建堆 2获取堆顶 package main import ( “fmt” ) func main() { arr := []int{0, 1, 2, 3, 4, 5, 6, 7} for length := len(arr); length > 0; length– { buildBigHeap(arr, length) fmt.Print(arr) change(&arr[0], &arr[length-1]) fmt.Print(“***”) fmt.Print(arr) fmt.Println(“———–“) } } /** 建立大顶堆 */ func buildBigHeap(arr []int, len int) { //for parent… Continue reading 堆排序