zhe.ink1、LZＷ算法的基本概念
LZW有三个重要对象：数据流(CharStream)、编码流(String Table)和编译表(String Table)。
(1)编码时，数据流是输入对象 (数据序列)，编码流就是输出对象(经过压缩运算的编码数据)；
(2)解码时，编码流是输入对象，数据流是输出对象；而编译表是在编码和解码时都需要借助的对象。
2、LZW压缩的基本原理
提取原始文本文件数据中的不同字符，基于这些字符创建一个编译表，然后用编译表中的字符的索引来替代原始数据中的相应字符，减少原始数据大小。注意：此处的编译表是根据原始数据动态创建的，解码时需要从已编码的数据中还原出原来的编译表。
3、LZW算法流程
步骤一：开始时词典包含所有可能的根，当前前缀字符串P和 当前字符 均为空；
步骤二：读入新的字符C，与P合并形成字符串P+C；
步骤三：判断P+C是否在字典中
如果"是"：
P = P + C；
返回步骤二；
如果"否"：
输出P的映射；
P = P+C ；
把前缀字符串P添加到字典，建立映射;
令P = C //(现在的P仅包含一个字符C);
步骤四： 判断码字流中是否还有码字要译
如果"是"：
返回步骤二；
如果"否"：
把代表当前前缀P的码字输出到码字流;
结束。
实现代码：
package main
import "fmt"
func compressLZW(testStr string) []int {
code := 256
dictionary := make(map[string]int)
for i := 0; i < 256; i++ {
dictionary[string(i)] = i
}
currChar := ""
result := make([]int, 0)
for _, c := range []byte(testStr) {
phrase := currChar + string(c)
if _, isTrue := dictionary[phrase]; isTrue {
currChar = phrase
} else {
result = append(result, dictionary[currChar])
dictionary[phrase] = code
code++
currChar = string(c)
}
}
if currChar != "" {
result = append(result, dictionary[currChar])
}
return result
}
func decompressLZW(compressed []int) string {
code := 256
dictionary := make(map[int]string)
for i := 0; i < 256; i++ {
dictionary[i] = string(i)
}
currChar := string(compressed[0])
result := currChar
for _, element := range compressed[1:] {
var word string
if x, ok := dictionary[element]; ok {
word = x
} else if element == code {
word = currChar + currChar[:1]
} else {
panic(fmt.Sprintf("Bad compressed element: %d", element))
}
result += word
dictionary[code] = currChar + word[:1]
code++
currChar = word
}
return result
}
func main() {
fmt.Print("Enter any string :")
var testStr string
fmt.Scanln(&testStr)
compressed := compressLZW(testStr)
fmt.Println("\nAfter Compression :", compressed)
uncompression := decompressLZW(compressed)
fmt.Println("\nAfter Uncompression :", uncompression)
}
输出：
Enter any string :Australia
After Compression : [65 117 115 116 114 97 108 105 97]
After Uncompression : Australia
C:\golang\example>go run test.go
Enter any string :Germany
After Compression : [71 101 114 109 97 110 121]
After Uncompression : Germany
排列是将有序列表S的元素重新排列为与S本身一一对应的对应关系。长度为n的字符串有n！排列。让我们以"ABCD"为例，编写一个程序来生成Golang中所有可能的字符串排列和组合。
实现代码：
package main
import (
"fmt"
)
func join(ins []rune, c rune) (res []string) {
for i := 0; i <= len(ins); i++ {
res = append(res, string(ins[:i])+string(c)+string(ins[i:]))
}
return res
}
func permutations(testStr string) []string {
var n func(testStr []rune, p []string) []string
n = func(testStr []rune, p []string) []string {
if len(testStr) == 0 {
return p
} else {
result := []string{}
for _, e := range p {
result = append(result, join([]rune(e), testStr[0])...)
}
return n(testStr[1:], result)
}
}
output := []rune(testStr)
return n(output[1:], []string{string(output[0])})
}
func main() {
d := permutations("ABCD")
fmt.Println(d)
}
输出：
[DCBA CDBA CBDA CBAD DBCA BDCA BCDA BCAD DBAC BDAC BADC BACD DCAB CDAB CADB CABD DACB ADCB ACDB ACBD DABC ADBC ABDC ABCD]
AVL树是高度平衡的二叉搜索树。AVL树检查左侧和右侧子树的高度，并确保差异不超过1，这种差异称为平衡因子。
实现代码：
package main
import (
"encoding/json"
"fmt"
)
type Key interface {
Less(Key) bool
Eq(Key) bool
}
type Node struct {
Data Key
Balance int
Link [2]*Node
}
func opp(dir int) int {
return 1 - dir
}
// single rotation
func single(root *Node, dir int) *Node {
save := root.Link[opp(dir)]
root.Link[opp(dir)] = save.Link[dir]
save.Link[dir] = root
return save
}
// double rotation
func double(root *Node, dir int) *Node {
save := root.Link[opp(dir)].Link[dir]
root.Link[opp(dir)].Link[dir] = save.Link[opp(dir)]
save.Link[opp(dir)] = root.Link[opp(dir)]
root.Link[opp(dir)] = save
save = root.Link[opp(dir)]
root.Link[opp(dir)] = save.Link[dir]
save.Link[dir] = root
return save
}
// adjust valance factors after double rotation
func adjustBalance(root *Node, dir, bal int) {
n := root.Link[dir]
nn := n.Link[opp(dir)]
switch nn.Balance {
case 0:
root.Balance = 0
n.Balance = 0
case bal:
root.Balance = -bal
n.Balance = 0
default:
root.Balance = 0
n.Balance = bal
}
nn.Balance = 0
}
func insertBalance(root *Node, dir int) *Node {
n := root.Link[dir]
bal := 2*dir - 1
if n.Balance == bal {
root.Balance = 0
n.Balance = 0
return single(root, opp(dir))
}
adjustBalance(root, dir, bal)
return double(root, opp(dir))
}
func insertR(root *Node, data Key) (*Node, bool) {
if root == nil {
return &Node{Data: data}, false
}
dir := 0
if root.Data.Less(data) {
dir = 1
}
var done bool
root.Link[dir], done = insertR(root.Link[dir], data)
if done {
return root, true
}
root.Balance += 2*dir - 1
switch root.Balance {
case 0:
return root, true
case 1, -1:
return root, false
}
return insertBalance(root, dir), true
}
// Insert a node into the AVL tree.
func Insert(tree **Node, data Key) {
*tree, _ = insertR(*tree, data)
}
// Remove a single item from an AVL tree.
func Remove(tree **Node, data Key) {
*tree, _ = removeR(*tree, data)
}
func removeBalance(root *Node, dir int) (*Node, bool) {
n := root.Link[opp(dir)]
bal := 2*dir - 1
switch n.Balance {
case -bal:
root.Balance = 0
n.Balance = 0
return single(root, dir), false
case bal:
adjustBalance(root, opp(dir), -bal)
return double(root, dir), false
}
root.Balance = -bal
n.Balance = bal
return single(root, dir), true
}
func removeR(root *Node, data Key) (*Node, bool) {
if root == nil {
return nil, false
}
if root.Data.Eq(data) {
switch {
case root.Link[0] == nil:
return root.Link[1], false
case root.Link[1] == nil:
return root.Link[0], false
}
heir := root.Link[0]
for heir.Link[1] != nil {
heir = heir.Link[1]
}
root.Data = heir.Data
data = heir.Data
}
dir := 0
if root.Data.Less(data) {
dir = 1
}
var done bool
root.Link[dir], done = removeR(root.Link[dir], data)
if done {
return root, true
}
root.Balance += 1 - 2*dir
switch root.Balance {
case 1, -1:
return root, true
case 0:
return root, false
}
return removeBalance(root, dir)
}
type intKey int
func (k intKey) Less(k2 Key) bool { return k < k2.(intKey) }
func (k intKey) Eq(k2 Key) bool { return k == k2.(intKey) }
func main() {
var tree *Node
fmt.Println("Empty Tree:")
avl,_ := json.MarshalIndent(tree, "", " ")
fmt.Println(string(avl))
fmt.Println("\nInsert Tree:")
Insert(&tree, intKey(4))
Insert(&tree, intKey(2))
Insert(&tree, intKey(7))
Insert(&tree, intKey(6))
Insert(&tree, intKey(6))
Insert(&tree, intKey(9))
avl,_ = json.MarshalIndent(tree, "", " ")
fmt.Println(string(avl))
fmt.Println("\nRemove Tree:")
Remove(&tree, intKey(4))
Remove(&tree, intKey(6))
avl,_ = json.MarshalIndent(tree, "", " ")
fmt.Println(string(avl))
}
输出：
Empty Tree:
null
Insert Tree:
{
"Data": 6,
"Balance": 0,
"Link": [
{
"Data": 4,
"Balance": 0,
"Link": [
{
"Data": 2,
"Balance": 0,
"Link": [
null,
null
]
},
{
"Data": 6,
"Balance": 0,
"Link": [
null,
null
]
}
]
},
{
"Data": 7,
"Balance": 1,
"Link": [
null,
{
"Data": 9,
"Balance": 0,
"Link": [
null,
null
]
}
]
}
]
}
Remove Tree:
{
"Data": 6,
"Balance": 1,
"Link": [
{
"Data": 2,
"Balance": 0,
"Link": [
null,
null
]
},
{
"Data": 7,
"Balance": 1,
"Link": [
null,
{
"Data": 9,
"Balance": 0,
"Link": [
null,
null
]
}
]
}
]
}
绘制2D矩阵，以螺旋格式打印给定矩阵的所有元素。给定一个数字n，使用O(1) 空间顺时针方向打印n x n螺旋矩阵(从1到n x n的数字)。
实现代码：
package main
import (
"fmt"
)
func spiral(n int) []int {
left, top, right, bottom := 0, 0, n-1, n-1
sz := n * n
s := make([]int, sz)
i := 0
for left < right {
// work right, along top
for c := left; c <= right; c++ {
s[top*n+c] = i
i++
}
top++
// work down right side
for r := top; r <= bottom; r++ {
s[r*n+right] = i
i++
}
right--
if top == bottom {
break
}
// work left, along bottom
for c := right; c >= left; c-- {
s[bottom*n+c] = i
i++
}
bottom--
// work up left side
for r := bottom; r >= top; r-- {
s[r*n+left] = i
i++
}
left++
}
// center (last) element
s[top*n+left] = i
return s
}
func main() {
num := 5
len := 2
for i, draw := range spiral(num) {
fmt.Printf("%*d ", len, draw)
if i%num == num-1 {
fmt.Println("")
}
}
}
输出：
0 1 2 3 4
15 16 17 18 5
14 23 24 19 6
13 22 21 20 7
12 11 10 9 8 绘制2D矩阵，按数字折线顺序打印给定矩阵的所有元素。该数字必须从0开始，然后以折线格式增加，并且必须绘制一个正方形。
实现代码：
package main
import (
"fmt"
)
func zigzag(n int) []int {
zz := make([]int, n*n)
i := 0
n2 := n * 2
for p := 1; p <= n2; p++ {
x := p - n
if x < 0 {
x = 0
}
y := p - 1
if y > n-1 {
y = n - 1
}
j := n2 - p
if j > p {
j = p
}
for k := 0; k < j; k++ {
if p&1 == 0 {
zz[(x+k)*n+y-k] = i
} else {
zz[(y-k)*n+x+k] = i
}
i++
}
}
return zz
}
func main() {
num := 5
len := 2
for i, draw := range zigzag(num) {
fmt.Printf("%*d ", len, draw)
if i%num == num-1 {
fmt.Println("")
}
}
}
输出：
0 1 5 6 14
2 4 7 13 15
3 8 12 16 21
9 11 17 20 22
10 18 19 23 24
迷宫可以通过从具有壁位点的细胞的预定排列开始产生。这种预定的排列可以被认为是连接图，其边缘表示可能的壁位点，节点表示单元。然后，迷宫生成算法的目的可以被认为是制作一个子图，在该子图中，在两个特定节点之间找到路线是具有挑战性的。
实现代码：
package main
import (
"bytes"
"fmt"
"math/rand"
"time"
)
type Maze struct {
c,h,v []byte
cell,hor,ver [][]byte
}
func DrawMaze(rows, cols int) *Maze {
c := make([]byte, rows*cols)
h := bytes.Repeat([]byte{'-'}, rows*cols)
v := bytes.Repeat([]byte{'|'}, rows*cols)
cell := make([][]byte, rows)
hor := make([][]byte, rows)
ver := make([][]byte, rows)
for i := range hor {
cell[i] = c[i*cols : (i+1)*cols]
hor[i] = h[i*cols : (i+1)*cols]
ver[i] = v[i*cols : (i+1)*cols]
}
return &Maze{c, h, v, cell, hor, ver}
}
func (m *Maze) String() string {
hWall := []byte("+---")
hOpen := []byte("+ ")
vWall := []byte("| ")
vOpen := []byte(" ")
rightCorner := []byte("+\n")
rightWall := []byte("|\n")
var b []byte
// for all rows
for r, hw := range m.hor {
// draw h walls
for _, h := range hw {
if h == '-' || r == 0 {
b = append(b, hWall...)
} else {
b = append(b, hOpen...)
}
}
b = append(b, rightCorner...)
// draw v walls
for c, vw := range m.ver[r] {
if vw == '|' || c == 0 {
b = append(b, vWall...)
} else {
b = append(b, vOpen...)
}
// draw cell contents
if m.cell[r][c] != 0 {
b[len(b)-2] = m.cell[r][c]
}
}
b = append(b, rightWall...)
}
// draw bottom edge of maze
for _ = range m.hor[0] {
b = append(b, hWall...)
}
b = append(b, rightCorner...)
return string(b)
}
func (m *Maze) generator() {
// Allocate the maze with recursive method
m.recursion(rand.Intn(len(m.cell)), rand.Intn(len(m.cell[0])))
}
const (
up = iota
down
right
left
)
func (m *Maze) recursion(row, col int) {
rand.Seed(time.Now().UnixNano())
m.cell[row][col] = ' '
for _, wall := range rand.Perm(4) {
switch wall {
// Whether cells up is out or not
case up:
if row > 0 && m.cell[row-1][col] == 0 {
m.hor[row][col] = 0
m.recursion(row-1, col)
}
// Whether cells down is out or not
case down:
if row < len(m.cell)-1 && m.cell[row+1][col] == 0 {
m.hor[row+1][col] = 0
m.recursion(row+1, col)
}
// Whether cells left is out or not
case left:
if col > 0 && m.cell[row][col-1] == 0 {
m.ver[row][col] = 0
m.recursion(row, col-1)
}
// Whether cells to the right is out or not
case right:
if col < len(m.cell[0])-1 && m.cell[row][col+1] == 0 {
m.ver[row][col+1] = 0
m.recursion(row, col+1)
}
}
}
}
func main() {
d := DrawMaze(5,7)
d.generator()
fmt.Print(d)
}
输出：
+---+---+---+---+---+---+---+
| | | |
+ + + + + + + +
| | | | | | | |
+ + +---+ + + + +
| | | | | | |
+ +---+ + + + + +
| | | | | | | |
+ + + + + + + +
| | | | |
+---+---+---+---+---+---+---+
用Golang编写一个程序来绘制一个2 X 3 X 6尺寸的长方体。长方体可以以图形方式表示，也可以以ASCII艺术形式表示，具体取决于语言功能。为了满足长方体的标准，必须有三个面是可见的。
package main
import "fmt"
func cuboidDraw(drawX, drawY, drawZ int) {
fmt.Printf("Cuboid %d %d %d:\n", drawX, drawY, drawZ)
cubeLine(drawY+1, drawX, 0, "+-")
for i := 1; i <= drawY; i++ {
cubeLine(drawY-i+1, drawX, i-1, "/ |")
}
cubeLine(0, drawX, drawY, "+-|")
for i := 4*drawZ - drawY - 2; i > 0; i-- {
cubeLine(0, drawX, drawY, "| |")
}
cubeLine(0, drawX, drawY, "| +")
for i := 1; i <= drawY; i++ {
cubeLine(0, drawX, drawY-i, "| /")
}
cubeLine(0, drawX, 0, "+-\n")
}
func cubeLine(n, drawX, drawY int, cubeDraw string) {
fmt.Printf("%*s", n+1, cubeDraw[:1])
for d := 9*drawX - 1; d > 0; d-- {
fmt.Print(cubeDraw[1:2])
}
fmt.Print(cubeDraw[:1])
fmt.Printf("%*s\n", drawY+1, cubeDraw[2:])
}
func main() {
fmt.Println("Enter 3 dimensions of Cuboid : ")
var l,b,h int
fmt.Scanln(&l)
fmt.Scanln(&b)
fmt.Scanln(&h)
cuboidDraw(l,b,h)
}
输出：
Cuboid 2 3 6:
+-----------------+
/ /|
/ / |
/ / |
+-----------------+ |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | +
| | /
| | /
| |/
+-----------------+
赫夫曼编码是可变字长编码(VLC)的一种。 Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字，有时称之为最佳编码，一般就称Huffman编码。下面引证一个定理，该定理保证了按字符出现概率分配码长，可使平均码长最短。
实现代码：
package main
import (
"container/heap"
"fmt"
)
type HuffmanTree interface {
Freq() int
}
type HuffmanLeaf struct {
freq int
value rune
}
type HuffmanNode struct {
freq int
left, right HuffmanTree
}
func (self HuffmanLeaf) Freq() int {
return self.freq
}
func (self HuffmanNode) Freq() int {
return self.freq
}
type treeHeap []HuffmanTree
func (th treeHeap) Len() int { return len(th) }
func (th treeHeap) Less(i, j int) bool {
return th[i].Freq() < th[j].Freq()
}
func (th *treeHeap) Push(ele interface{}) {
*th = append(*th, ele.(HuffmanTree))
}
func (th *treeHeap) Pop() (popped interface{}) {
popped = (*th)[len(*th)-1]
*th = (*th)[:len(*th)-1]
return
}
func (th treeHeap) Swap(i, j int) { th[i], th[j] = th[j], th[i] }
// The main function that builds a Huffman Tree and print codes by traversing
// the built Huffman Tree
func buildTree(symFreqs map[rune]int) HuffmanTree {
var trees treeHeap
for c, f := range symFreqs {
trees = append(trees, HuffmanLeaf{f, c})
}
heap.Init(&trees)
for trees.Len() > 1 {
// two trees with least frequency
a := heap.Pop(&trees).(HuffmanTree)
b := heap.Pop(&trees).(HuffmanTree)
// put into new node and re-insert into queue
heap.Push(&trees, HuffmanNode{a.Freq() + b.Freq(), a, b})
}
return heap.Pop(&trees).(HuffmanTree)
}
// Prints huffman codes from the root of Huffman Tree. It uses byte[] to
// store codes
func printCodes(tree HuffmanTree, prefix []byte) {
switch i := tree.(type) {
case HuffmanLeaf:
// If this is a leaf node, then it contains one of the input
// characters, print the character and its code from byte[]
fmt.Printf("%c\t%d\t%s\n", i.value, i.freq, string(prefix))
case HuffmanNode:
// Assign 0 to left edge and recur
prefix = append(prefix, '0')
printCodes(i.left, prefix)
prefix = prefix[:len(prefix)-1]
// Assign 1 to right edge and recur
prefix = append(prefix, '1')
printCodes(i.right, prefix)
prefix = prefix[:len(prefix)-1]
}
}
// Driver program to test above functions
func main() {
test := "abcdefghijklmnopqrstuvwxyz"
symFreqs := make(map[rune]int)
// read each symbol and record the frequencies
for _, c := range test {
symFreqs[c]++
}
// example tree
exampleTree := buildTree(symFreqs)
// print out results
fmt.Println("SYMBOL\tWEIGHT\tHUFFMAN CODE")
printCodes(exampleTree, []byte{})
}
输出：
SYMBOL WEIGHT HUFFMAN CODE
m 1 0000
d 1 0001
r 1 0010
t 1 0011
a 1 0100
p 1 0101
s 1 01100
y 1 01101
u 1 01110
w 1 01111
v 1 10000
o 1 10001
f 1 10010
z 1 10011
n 1 10100
i 1 10101
l 1 10110
c 1 10111
g 1 11000
h 1 11001
e 1 11010
k 1 11011
x 1 11100
j 1 11101
q 1 11110
b 1 11111
汉诺塔(Tower of Hanoi)，又称河内塔，是一个源于印度古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
实现代码：
package main
import "fmt"
type solver interface {
play(int)
}
// towers is example of type satisfying solver interface
type towers struct {
// an empty struct
}
// play is sole method required to implement solver type
func (t *towers) play(n int) {
t.moveN(n, 1, 2, 3)
}
// recursive algorithm
func (t *towers) moveN(n, from, to, via int) {
if n > 0 {
t.moveN(n-1, from, via, to)
t.moveM(from, to)
t.moveN(n-1, via, to, from)
}
}
func (t *towers) moveM(from, to int) {
fmt.Println("Move disk from rod", from, "to rod", to)
}
func main() {
var t solver
t = new(towers) // type towers must satisfy solver interface
t.play(4)
}
输出：
Move disk from rod 1 to rod 3
Move disk from rod 1 to rod 2
Move disk from rod 3 to rod 2
Move disk from rod 1 to rod 3
Move disk from rod 2 to rod 1
Move disk from rod 2 to rod 3
Move disk from rod 1 to rod 3
Move disk from rod 1 to rod 2
Move disk from rod 3 to rod 2
Move disk from rod 3 to rod 1
Move disk from rod 2 to rod 1
Move disk from rod 3 to rod 2
Move disk from rod 1 to rod 3
Move disk from rod 1 to rod 2
Move disk from rod 3 to rod 2
Floyd-Warshall算法(英语：Floyd-Warshall algorithm)，中文亦称弗洛伊德算法，是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权(但不可存在负权回路)的最短路径问题，同时也被用于计算有向图的传递闭包。Floyd-Warshall算法的时间复杂度为O(N3)，空间复杂度为O(N2)，因时间复杂度比较高，不适合计算大量数据。
示例代码：
package main
import (
"fmt"
"math"
)
type graph struct {
to int
wt float64
}
func floydWarshall(g [][]graph) [][]float64 {
dist := make([][]float64, len(g))
for i := range dist {
di := make([]float64, len(g))
for j := range di {
di[j] = math.Inf(1)
}
di[i] = 0
dist[i] = di
}
for u, graphs := range g {
for _, v := range graphs {
dist[u][v.to] = v.wt
}
}
for k, dk := range dist {
for _, di := range dist {
for j, dij := range di {
if d := di[k] + dk[j]; dij > d {
di[j] = d
}
}
}
}
return dist
}
func main() {
gra := [][]graph{
1: {{2, 3}, {3, 8},{5, -4}},
2: {{4, 1}, {5, 7}},
3: {{2, 4}},
4: {{1, 2}, {3, -5}},
5: {{4, 6}},
}
dist := floydWarshall(gra)
//dist[][] will be the output matrix that will finally
//have the shortest distances between every pair of vertices
for _, d := range dist {
fmt.Printf("%4g\n", d)
}
}
输出：
[ 0 +Inf +Inf +Inf +Inf +Inf]
[+Inf 0 1 -3 2 -4]
[+Inf 3 0 -4 1 -1]
[+Inf 7 4 0 5 3]
[+Inf 2 -1 -5 0 -2]
[+Inf 8 5 1 6 0]
KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n) 。
(1)精确匹配
如果在目标T中至少一处存在模式P，则称匹配成功，否则即使目标与模式只有一个字符不同也不能称为匹配成功，即匹配失败。给定一个字符或符号组成的字符串目标对象T和一个字符串模式P，模式匹配的目的是在目标T中搜索与模式P完全相同的子串,返回T和P匹配的第一个字符串的首字母位置。
(2)近似匹配
如果模式P与目标T(或其子串)存在某种程度的相似,则认为匹配成功。常用的衡量字符串相似度的方法是根据一个串转换成另一个串所需的基本操作数目来确定。基本操作由字符串的插入、删除和替换来组成。
示例代码：
package main
import (
"fmt"
)
const (
PatternSize int = 100
)
func SearchNext(haystack string, needle string) int {
retSlice := KMP(haystack, needle)
if len(retSlice) > 0 {
return retSlice[len(retSlice)-1]
}
return -1
}
func SearchString(haystack string, needle string) int {
retSlice := KMP(haystack, needle)
if len(retSlice) > 0 {
return retSlice[0]
}
return -1
}
func KMP(haystack string, needle string) []int {
next := preKMP(needle)
i := 0
j := 0
m := len(needle)
n := len(haystack)
x := []byte(needle)
y := []byte(haystack)
var ret []int
//got zero target or want, just return empty result
if m == 0 || n == 0 {
return ret
}
//want string bigger than target string
if n < m {
return ret
}
for j < n {
for i > -1 && x[i] != y[j] {
i = next[i]
}
i++
j++
//fmt.Println(i, j)
if i >= m {
ret = append(ret, j-i)
//fmt.Println("find:", j, i)
i = next[i]
}
}
return ret
}
func preMP(x string) [PatternSize]int {
var i, j int
length := len(x) - 1
var mpNext [PatternSize]int
i = 0
j = -1
mpNext[0] = -1
for i < length {
for j > -1 && x[i] != x[j] {
j = mpNext[j]
}
i++
j++
mpNext[i] = j
}
return mpNext
}
func preKMP(x string) [PatternSize]int {
var i, j int
length := len(x) - 1
var kmpNext [PatternSize]int
i = 0
j = -1
kmpNext[0] = -1
for i < length {
for j > -1 && x[i] != x[j] {
j = kmpNext[j]
}
i++
j++
if x[i] == x[j] {
kmpNext[i] = kmpNext[j]
} else {
kmpNext[i] = j
}
}
return kmpNext
}
func main() {
fmt.Println("Search First Position String:\n")
fmt.Println(SearchString("cocacola", "co"))
fmt.Println(SearchString("Australia", "lia"))
fmt.Println(SearchString("cocacola", "cx"))
fmt.Println(SearchString("AABAACAADAABAABA", "AABA"))
fmt.Println("\nSearch Last Position String:\n")
fmt.Println(SearchNext("cocacola", "co"))
fmt.Println(SearchNext("Australia", "lia"))
fmt.Println(SearchNext("cocacola", "cx"))
fmt.Println(SearchNext("AABAACAADAABAABAAABAACAADAABAABA", "AABA"))
}
输出：
Search First Position String:
0
6
-1
0
Search Last Position String:
4
6
-1
25
编辑距离是针对二个字符串(例如英文字)的差异程度的量化量测，量测方式是看至少需要多少次的处理才能将一个字符串变成另一个字符串。编辑距离可以用在自然语言处理中，例如拼写检查可以根据一个拼错的字和其他正确的字的编辑距离，判断哪一个(或哪几个)是比较可能的字。DNA也可以视为用A、C、G和T组成的字符串，因此编辑距离也用在生物信息学中，判断二个DNA的类似程度。Unix下的diff及patch即是利用编辑距离来进行文本编辑对比的例子。
示例代码：
package main
import "fmt"
func levenshtein(str1, str2 []rune) int {
s1len := len(str1)
s2len := len(str2)
column := make([]int, len(str1)+1)
for y := 1; y <= s1len; y++ {
column[y] = y
}
for x := 1; x <= s2len; x++ {
column[0] = x
lastkey := x - 1
for y := 1; y <= s1len; y++ {
oldkey := column[y]
var incr int
if str1[y-1] != str2[x-1] {
incr = 1
}
column[y] = minimum(column[y]+1, column[y-1]+1, lastkey+incr)
lastkey = oldkey
}
}
return column[s1len]
}
func minimum(a, b, c int) int {
if a < b {
if a < c {
return a
}
} else {
if b < c {
return b
}
}
return c
}
func main(){
var str1 = []rune("Asheville")
var str2 = []rune("Arizona")
fmt.Println("Distance between Asheville and Arizona:",levenshtein(str1,str2))
str1 = []rune("Python")
str2 = []rune("Peithen")
fmt.Println("Distance between Python and Peithen:",levenshtein(str1,str2))
str1 = []rune("Orange")
str2 = []rune("Apple")
fmt.Println("Distance between Orange and Apple:",levenshtein(str1,str2))
}
输出：
Distance between Asheville and Arizona: 8
Distance between Python and Peithen: 3
Distance between Orange and Apple: 5
Longest Common Sub-sequence
最长公共子序列(LCS)是一个在一个序列集合中(通常为两个序列)用来查找所有序列中最长子序列的问题。一个数列 ，如果分别是两个或多个已知数列的子序列，且是所有符合此条件序列中最长的，则称为已知序列的最长公共子序列。
最长公共子序列问题是一个经典的计算机科学问题，也是数据比较程序，比如Diff工具，和生物信息学应用的基础。它也被广泛地应用在版本控制，比如Git用来调和文件之间的改变。
示例代码：
package main
import "fmt"
func max(a, b int) int {
if a > b {
return a
}
return b
}
func lcs(X string, Y string, m int, n int) int {
if m == 0 || n == 0 {
return 0
}
if X[m-1] == Y[n-1] {
return 1 + lcs(X, Y, m-1, n-1)
}
return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n))
}
func main() {
X := "AGGTAB"
Y := "GXTXAYB"
m := len(X)
n := len(Y)
fmt.Println("Length of LCS is", lcs(X, Y, m, n))
}
输出：
Length of LCS is 4该算法由Blum、Floyd、Pratt、Rivest、Tarjan在1973年提出，最坏时间复杂度为O(n)，最差的空间复杂度为O(logn)。
在计算机科学中，中位数的中位数是一种近似(中位数)选择算法，通常用于为精确选择算法(主要是快速选择)提供良好的枢轴，该算法选择第k个最小元素。
算法步骤
(1)：将n个元素划分为 ⌊n/5⌋ 个组，每组5个元素，若有剩余，舍去；
(2)：使用排序方法找到 ⌊n/5⌋ 个组中每一组的中位数；
(3)：对于(2)中找到的所有中位数，递归(1)(2)查找中位数的中位数，作为Partition划分过程的主元
(4)：进行Partition划分，即一次快排
(5)：判断主元的位置与k的大小，有选择的对左边或右边递归。
算法应用
BFPRT算法的一个经典应用就是TOP-K问题，即在一组数据中寻找第K大或第K小的元素。
这类问题可以分为对数据完全排序，部分排序和不排序。
完全排序情况下可以使用快速排序等排序方法能达到O(nlogn)的时间复杂度。
部分排序可以使用冒泡排序，选择排序等方法也能达到O(kn)的时间复杂度。
不排序的情况可以使用堆排序的方法，时间复杂度为O(nlogk)。
而BFPRT算法解决这类问题能达到O(n)的时间复杂度！！
这是Go程序的源代码，用于查找第K个最小元素的中位数。
package main
import (
"fmt"
"sort"
)
func medianOfMedians(sliceList []int, k, r int) int {
num := len(sliceList)
if num < 10 {
sort.Ints(sliceList)
return sliceList[k-1]
}
med := (num + r - 1) / r
medians := make([]int, med)
for i := 0; i < med; i++ {
v := (i * r) + r
var arr []int
if v >= num {
arr = make([]int, len(sliceList[(i*r):]))
copy(arr, sliceList[(i*r):])
} else {
arr = make([]int, r)
copy(arr, sliceList[(i*r):v])
}
sort.Ints(arr)
medians[i] = arr[len(arr)/2]
}
pivot := medianOfMedians(medians, (len(medians)+1)/2, r)
var leftSide, rightSide []int
for i := range sliceList {
if sliceList[i] < pivot {
leftSide = append(leftSide, sliceList[i])
} else if sliceList[i] > pivot {
rightSide = append(rightSide, sliceList[i])
}
}
switch {
case k == (len(leftSide) + 1):
return pivot
case k <= len(leftSide):
return medianOfMedians(leftSide, k, r)
default:
return medianOfMedians(rightSide, k-len(leftSide)-1, r)
}
}
func main() {
intSlice := []int{5, 9, 77, 62, 71, 11, 22, 46, 36, 18, 19, 33, 75, 17, 39, 41, 73, 50, 217, 79, 120}
sort.Ints(intSlice)
for _, j := range []int{5, 10, 15, 20} {
i := medianOfMedians(intSlice, j, 5)
fmt.Println(j, "smallest element = ", i)
v := intSlice[j-1]
fmt.Println("arr[", j-1, "] = ", v)
if i != v {
fmt.Println("Oops! Algorithm is wrong")
}
}
}
输出：
5 smallest element = 18
arr[ 4 ] = 18
10 smallest element = 39
arr[ 9 ] = 39
15 smallest element = 71
arr[ 14 ] = 71
20 smallest element = 120
arr[ 19 ] = 120堆栈是一个有序列表，其中所有插入和删除都在一端(称为顶部)进行。队列是一个有序列表，其中所有插入都发生在一端(后部)，而所有删除都发生在另一端(前部)。堆栈有时称为后进先出 (LIFO) 列表，队列称为先进先出 (FIFO) 列表。
package main
import (
"fmt"
)
type Node struct {
Value int
}
func (n *Node) String() string {
return fmt.Sprint(n.Value)
}
// 创建stack
func NewStack() *Stack {
return &Stack{}
}
// Stack结构type Stack struct {
nodes []*Node
count int
}
// 压入stack
func (s *Stack) Push(n *Node) {
s.nodes = append(s.nodes[:s.count], n)
s.count++
}
// 弹出stack
func (s *Stack) Pop() *Node {
if s.count == 0 {
return nil
}
s.count--
return s.nodes[s.count]
}
// 创建queue
func NewQueue(size int) *Queue {
return &Queue{
nodes: make([]*Node, size),
size: size,
}
}
// Queue结构type Queue struct {
nodes []*Node
size int
head int
tail int
count int
}
// queue的压入func (q *Queue) Push(n *Node) {
if q.head == q.tail && q.count > 0 {
nodes := make([]*Node, len(q.nodes)+q.size)
copy(nodes, q.nodes[q.head:])
copy(nodes[len(q.nodes)-q.head:], q.nodes[:q.head])
q.head = 0
q.tail = len(q.nodes)
q.nodes = nodes
}
q.nodes[q.tail] = n
q.tail = (q.tail + 1) % len(q.nodes)
q.count++
}
// queue的弹出func (q *Queue) Pop() *Node {
if q.count == 0 {
return nil
}
node := q.nodes[q.head]
q.head = (q.head + 1) % len(q.nodes)
q.count--
return node
}
func main() {
s := NewStack()
s.Push(&Node{3})
s.Push(&Node{5})
s.Push(&Node{7})
s.Push(&Node{9})
fmt.Println(s.Pop(), s.Pop(), s.Pop(), s.Pop())
q := NewQueue(1)
q.Push(&Node{2})
q.Push(&Node{4})
q.Push(&Node{6})
q.Push(&Node{8})
fmt.Println(q.Pop(), q.Pop(), q.Pop(), q.Pop())
}单向链表是由一系列节点组成的数据结构，其中每个节点都包含一个值和一个指向序列中下一个节点的引用。在单向链表中，每个节点只有对下一个节点的引用，没有对前一个节点的引用。在未排序的链表中，节点的顺序无关紧要，可以在列表中的任何位置插入或删除它们。
要访问链表中的特定节点，我们从头节点(链表中的第一个节点)开始，然后按照链接操作，直到到达所需的节点。如果某个节点对其下一个节点的引用为null，则将其视为链表中的最后一个节点。
单向无序链表是一种有用的数据结构，用于实现许多算法，例如搜索、排序和图遍历算法。但是，它们在按索引访问元素方面不如数组或其他数据结构高效，因为我们必须从头开始遍历链表才能找到特定元素。
示例代码：
package main
import (
"fmt"
)
type Node struct {
data int
next *Node
}
type List struct {
head *Node
}
func (l *List) add(value int) {
newNode := &Node{data: value}
if l.head == nil {
l.head = newNode
return
}
curr := l.head
for curr.next != nil {
curr = curr.next
}
curr.next = newNode
}
func (l *List) remove(value int) {
if l.head == nil {
return
}
if l.head.data == value {
l.head = l.head.next
return
}
curr := l.head
for curr.next != nil && curr.next.data != value {
curr = curr.next
}
if curr.next != nil {
curr.next = curr.next.next
}
}
func main() {
list := &List{}
list.add(1)
list.add(2)
list.add(3)
list.add(4)
fmt.Println("Initial List: ")
printList(list)
list.remove(2)
fmt.Println("List after removing 2: ")
printList(list)
list.remove(4)
fmt.Println("List after removing 4: ")
printList(list)
}
func printList(l *List) {
curr := l.head
for curr != nil {
fmt.Printf("%d ", curr.data)
curr = curr.next
}
fmt.Println()
}
首先，我们定义了两个结构：Node和List。Node结构表示链表中的单个节点，其中包含数据和指向下一个节点的指针。List结构包含指向头节点的指针。
接下来，我们定义add函数，该函数接受一个值并将其添加到列表末尾。如果列表为空，则新节点将成为头节点。否则，我们遍历列表以查找最后一个节点，然后将新节点追加到该节点。
然后，我们定义remove函数，该函数接受一个值并从列表中删除它的第一个出现。如果列表为空，或者未找到值，则该函数不执行任何操作。如果在头节点上找到该值，我们只需更新头指针。否则，我们遍历列表以查找要删除的节点之前的节点，然后更新其下一个指针以跳过要删除的节点。
最后，在main函数中，我们创建一个新列表并向其添加一些节点。然后，我们打印初始列表，删除几个节点，然后再次打印列表以查看更改。
Rabin-Karp算法(也可以叫Karp-Rabin算法)，由Richard M. Karp和Michael O. Rabin在1987年发表，它也是用来解决多模式串匹配问题的。它的实现方式有点与众不同，首先是计算两个字符串的哈希值，然后通过比较这两个哈希值的大小来判断是否出现匹配。
哈希算法可以有很多种不同的形式，它可能包含ASCII码字符以便对数字进行转化，但也可能是别的形式。我们唯一需要的就是将一个字符串(模式串)转化成为能够快速进行比较的哈希值。以"hello world"为例，假设它的哈希值hash('hello world')=12345。那么如果hash('he')=1，那么我们就可以说模式串"he"包含在文本"hello world"中。由此，我们可以每次从文本中取出长度为m(m为模式串的长度)的子串，然后将该子串进行哈希，并将其哈希值与模式串的哈希值进行比较。
示例代码：
package main
import (
"fmt"
)
const base = 16777619
func Search(txt string, patterns []string) []string {
in := indices(txt, patterns)
matches := make([]string, len(in))
i := 0
for j, p := range patterns {
if _, ok := in[j]; ok {
matches[i] = p
i++
}
}
return matches
}
func indices(txt string, patterns []string) map[int]int {
n, m := len(txt), minLen(patterns)
matches := make(map[int]int)
if n < m || len(patterns) == 0 {
return matches
}
var mult uint32 = 1 // mult = base^(m-1)
for i := 0; i < m-1; i++ {
mult = (mult * base)
}
hp := hashPatterns(patterns, m)
h := hash(txt[:m])
for i := 0; i < n-m+1 && len(hp) > 0; i++ {
if i > 0 {
h = h - mult*uint32(txt[i-1])
h = h*base + uint32(txt[i+m-1])
}
if mps, ok := hp[h]; ok {
for _, pi := range mps {
pat := patterns[pi]
e := i + len(pat)
if _, ok := matches[pi]; !ok && e <= n && pat == txt[i:e] {
matches[pi] = i
}
}
}
}
return matches
}
func hash(s string) uint32 {
var h uint32
for i := 0; i < len(s); i++ {
h = (h*base + uint32(s[i]))
}
return h
}
func hashPatterns(patterns []string, l int) map[uint32][]int {
m := make(map[uint32][]int)
for i, t := range patterns {
h := hash(t[:l])
if _, ok := m[h]; ok {
m[h] = append(m[h], i)
} else {
m[h] = []int{i}
}
}
return m
}
func minLen(patterns []string) int {
if len(patterns) == 0 {
return 0
}
m := len(patterns[0])
for i := range patterns {
if m > len(patterns[i]) {
m = len(patterns[i])
}
}
return m
}
func main() {
txt := "Australia is a country and continent surrounded by the Indian and Pacific oceans."
patterns := []string{"and", "the", "surround", "Pacific", "Germany"}
matches := Search(txt, patterns)
fmt.Println(matches)
}
输出：
[and the surround Pacific]
二叉树是由节点组成的数据结构，其中每个节点最多有两个子节点(也称为"左"和"右"子节点)。二叉树中的节点由边连接，边表示节点之间的链接。树中最顶层的节点称为根节点，除根节点外的每个节点都连接到唯一的父节点。
二叉树通常用于表示分层数据结构，例如家谱、组织结构图和文件系统目录。它们还被用作许多算法的底层数据结构，例如二进制搜索、排序和图形遍历算法。
二叉树有几个重要的属性，包括：
l级别的最大节点数为2(h+1)-1。
二叉树的高度是从根节点到叶节点(没有子节点的节点)的最长路径上的边数。空树的高度定义为 -1。
如果每个节点的左右子树的高度最多相差1，则称二叉树是平衡的。平衡二叉树的高度为O(log n)，其中n是树中的节点数。
二叉树可以通过多种方式遍历，包括按顺序(左子树、根节点、右子树)、前序(根节点、左子树、右子树)和后序(左子树、右子树、根节点)遍历。
二叉树有许多变体，包括二叉搜索树 (BST)、AVL树和红黑树，它们具有不同的规则来对树中的节点进行排序和平衡。
示例代码：它实现了一个二叉搜索树 (BST) 并以图形格式打印树的节点。
package main
import (
"fmt"
"os"
"io"
)
type BinaryNode struct {
left *BinaryNode
right *BinaryNode
data int64
}
type BinaryTree struct {
root *BinaryNode
}
func (t *BinaryTree) insert(data int64) *BinaryTree {
if t.root == nil {
t.root = &BinaryNode{data: data, left: nil, right: nil}
} else {
t.root.insert(data)
}
return t
}
func (n *BinaryNode) insert(data int64) {
if n == nil {
return
} else if data <= n.data {
if n.left == nil {
n.left = &BinaryNode{data: data, left: nil, right: nil}
} else {
n.left.insert(data)
}
} else {
if n.right == nil {
n.right = &BinaryNode{data: data, left: nil, right: nil}
} else {
n.right.insert(data)
}
}
}
func print(w io.Writer, node *BinaryNode, ns int, ch rune) {
if node == nil {
return
}
for i := 0; i < ns; i++ {
fmt.Fprint(w, " ")
}
fmt.Fprintf(w, "%c:%v\n", ch, node.data)
print(w, node.left, ns+2, 'L')
print(w, node.right, ns+2, 'R')
}
func main() {
tree := &BinaryTree{}
tree.insert(100).
insert(-20).
insert(-50).
insert(-15).
insert(-60).
insert(50).
insert(60).
insert(55).
insert(85).
insert(15).
insert(5).
insert(-10)
print(os.Stdout, tree.root, 0, 'M')
}
输出：
M:100
L:-20
L:-50
L:-60
R:-15
R:50
L:15
L:5
L:-10
R:60
L:55
R:85
我们可以先找到最大的数的位置i,然后煎饼翻转k= i+1,让最大的数放到最前面。
接着我们煎饼翻转len，让最大的数放到最后面,然后len --。
接着我们再找到arr[0~-2]中最大的数，执行操作1~2即可，一直执行到i=2为止。
对于煎饼翻转的过程：如果我们的翻转数为k，我们先定一个最小下标a=0, 执行swap(arr[a],arr[k-1]),进行数据交换，然后执行a ++,b --即可。直到a>=b为止，视为完成了煎饼翻转的过程。
示例代码：
package main
import "fmt"
func main() {
list := data{28, 11, 59, -26, 503, 158, 997, 193, -23, 44}
fmt.Println("\n--- Unsorted --- \n\n", list)
list.pancakesort()
fmt.Println("\n--- Sorted ---\n\n", list, "\n")
}
type data []int32
func (dataList data) pancakesort() {
for uns := len(dataList) - 1; uns > 0; uns-- {
// find largest in unsorted range
lx, lg := 0, dataList[0]
for i := 1; i <= uns; i++ {
if dataList[i] > lg {
lx, lg = i, dataList[i]
}
}
// move to final position in two flips
dataList.flip(lx)
dataList.flip(uns)
}
}
func (dataList data) flip(r int) {
for l := 0; l < r; l, r = l+1, r-1 {
dataList[l], dataList[r] = dataList[r], dataList[l]
}
}
输出：
--- Unsorted ---
[28 11 59 -26 503 158 997 193 -23 44]
--- Sorted ---
[-26 -23 11 28 44 59 158 193 503 997]
基数排序(radix sort)属于"分配式排序"(distribution sort)，又称"桶子法"(bucket sort)或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些"桶"中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。
时间效率：设待排序列为n个记录，d个关键码，关键码的取值范围为radix，则进行链式基数排序的时间复杂度为O(d(n+radix))，其中，一趟分配时间复杂度为O(n)，一趟收集时间复杂度为O(radix)，共进行d趟分配和收集。 空间效率：需要2*radix个指向队列的辅助空间，以及用于静态链表的n个指针。
示例代码：
package main
import (
"bytes"
"encoding/binary"
"fmt"
)
const digit = 4
const maxbit = -1 << 31
func main() {
var data = []int32{421, 15, -175, 90, -2, 214, -52, -166}
fmt.Println("\n--- Unsorted --- \n\n", data)
radixsort(data)
fmt.Println("\n--- Sorted ---\n\n", data, "\n")
}
func radixsort(data []int32) {
buf := bytes.NewBuffer(nil)
ds := make([][]byte, len(data))
for i, e := range data {
binary.Write(buf, binary.LittleEndian, e^maxbit)
b := make([]byte, digit)
buf.Read(b)
ds[i] = b
}
countingSort := make([][][]byte, 256)
for i := 0; i < digit; i++ {
for _, b := range ds {
countingSort[b[i]] = append(countingSort[b[i]], b)
}
j := 0
for k, bs := range countingSort {
copy(ds[j:], bs)
j += len(bs)
countingSort[k] = bs[:0]
}
}
var w int32
for i, b := range ds {
buf.Write(b)
binary.Read(buf, binary.LittleEndian, &w)
data[i] = w^maxbit
}
}
输出：
--- Unsorted ---
[421 15 -175 90 -2 214 -52 -166]
--- Sorted ---
[-175 -166 -52 -2 15 90 214 421]
苏公网安备
32050902101537号