收集一些常见算法

发表于 分类于 Waline： 本文字数： 812 阅读时长 ≈ 1 分钟

翻转字符串

以字符串中间字符为中心，遍历交换前后字符来达到翻转的目的

因为中英文字符所占用byte的长度不一致，一个中文字符在utf-8编码集中占用3个字节，导致len()会出现问题，故使用如下方法：

1
2
3
4
5
6
7
8

str := "hello世界"
// 方法一
strArr := []rune(str)
fmt.Println(len(strArr))
// 方法二
fmt.Println(utf8.RuneCountInString(str)) // 调用 unicode/utf8 标准库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

package main

import "fmt"

func ReverseString(str string) string {
	strArr := []rune(str)
	for i := 0; i < len(strArr)/2; i++ {
		strArr[len(strArr)-1-i], strArr[i] = strArr[i], strArr[len(strArr)-1-i]
	}
	return string(strArr)
}

func main() {
	str := "hello世界"
	fmt.Println(ReverseString(str))
}

堆排序和快速排序的原理

堆排序

原理阐述： 1. 建堆 2. 堆调整 3. 堆排序

我们一般提到堆排序里的堆指的是二叉堆（binary heap），是一种完全二叉树，二叉堆有两种：最大堆和最小堆，特点是父节点的值大于（小于）两个小节点的值。完全二叉树有一个性质是，除了最底层，每一层都是满的。

快速排序

原理阐述：分而治之

实现步骤：

先从数列中取出一个数作为基准数。分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。再对左右区间重复第二步，直到各区间只有一个数（各个区间都为有序）。