Dawn's Blogs

分享技术 记录成长

0%

发表于 更新于 分类于

函数

错误处理

对于那些将运行失败看作是预期结果的函数，它们会返回一个额外的返回值，通常是最后一个，来传递错误信息。

如果导致失败的原因只有一个，额外的返回值可以是一个布尔值，通常被命名为ok

1
2
3
4
5
value, ok := cache.Lookup(key)

if !ok {
	// ...cache[key] does not exist…
}

通常，导致失败的原因不止一种，尤其是对I/O操作而言，用户需要了解更多的错误信息。因此，额外的返回值不再是简单的布尔类型，而是error类型

在Go中，函数运行失败时会返回错误信息，这些错误信息被认为是一种预期的值而非异常（exception），这使得Go有别于那些将函数运行失败看作是异常的语言。

在Go中，错误处理有一套独特的编码风格。检查某个子函数是否失败后，我们通常将处理失败的逻辑代码放在处理成功的代码之前。如果某个错误会导致函数返回，那么成功时的逻辑代码不应放在else语句块中，而应直接放在函数体中。Go中大部分函数的代码结构几乎相同，首先是一系列的初始检查，防止错误发生，之后是函数的实际逻辑

错误处理策略

当一次函数调用返回错误时，调用者有应该选择何时的方式处理错误。根据情况不同，有5种不同的处理策略。

  1. 传播错误，这是最常用的方式。函数中某个子程序的失败，会变成该函数的失败。可以用fmt.Errorf函数重新构造错误信息返回
1
2
3
4
5
resp, err := http.Get(url)
if err != nil{
    // 执行失败，直接返回
	return nil, err
}
  1. 如果错误的发生是偶然性的，或由不可预知的问题导致的。一个明智的选择是重新尝试失败的操作。在重试时，我们需要限制重试的时间间隔或重试的次数，防止无限制的重试。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// WaitForServer attempts to contact the server of a URL.
// It tries for one minute using exponential back-off.
// It reports an error if all attempts fail.
func WaitForServer(url string) error {
	const timeout = 1 * time.Minute
	deadline := time.Now().Add(timeout)
    
	for tries := 0; time.Now().Before(deadline); tries++ {
		_, err := http.Head(url)
		if err == nil {
			return nil // success
		}
		log.Printf("server not responding (%s);retrying…", err)
		time.Sleep(time.Second << uint(tries)) // exponential back-off
	}
    
	return fmt.Errorf("server %s failed to respond after %s", url, timeout)
}
  1. 如果错误发生后，程序无法继续运行，可以输出错误信息并结束程序。需要注意的是，这种策略只应在main中执行。对库函数而言，应仅向上传播错误，除非该错误意味着程序内部包含不一致性，即遇到了bug，才能在库函数中结束程序。
1
2
3
4
5
6
7
// (In function main.)
if err := WaitForServer(url); err != nil {
	fmt.Fprintf(os.Stderr, "Site is down: %v\n", err)
	os.Exit(1)
    // 以上两条等价于
    // log.Fatalf("Site is down: %v\n", err)
}
  1. 我们只需要输出错误信息就足够了，不需要中断程序的运行。我们可以通过log包提供函数或者标准错误流输出错误信息
1
2
3
4
if err := Ping(); err != nil {
	log.Printf("ping failed: %v; networking disabled",err)
    // fmt.Fprintf(os.Stderr, "ping failed: %v; networking disabled\n", err)
}
  1. 直接忽略错误

文件结尾错误

io包保证任何由文件结束引起的读取失败都返回同一个错误——io.EOF，该错误在io包中定义：

1
var EOF = errors.New("EOF")

调用者只需通过简单的比较，就可以检测出这个错误。下面的例子展示了如何从标准输入中读取字符，以及判断文件结束。

1
2
3
4
5
6
7
8
9
10
11
12
in := bufio.NewReader(os.Stdin)
for {
	r, _, err := in.ReadRune()
	if err == io.EOF {
		break // finished reading
	}
	if err != nil {
		return fmt.Errorf("read failed:%v", err)
	}
	// ...use r…
}

因为文件结束这种错误不需要更多的描述，所以io.EOF有固定的错误信息——“EOF”。对于其他错误，我们可能需要在错误信息中描述错误的类型和数量，这使得我们不能像io.EOF一样采用固定的错误信息

函数值

在GO语言中，函数像其他值一样，拥有类型、可以被赋值给其他变量。

函数值属于引用类型

函数类型的零值是nil，函数值是可以和nil进行比较的。但是函数值之间是不可比较的（也就是说，函数值不能作为map的key）

1
2
3
4
var f func(int) int
if f != nil {
	f(3)
}

函数值作为函数的参数可以定义函数的行为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func f(pre, post func()) {
    if pre != nil {
        // 在执行f之前调用pre()
        pre()
    }
    /*
    	中间的函数体
    	.....
    */
    if post != nil {
        // 在执行f之后调用post
        post()
    }
}

匿名函数

拥有函数名的函数只能在包级语法块中被声明，通过函数字面量（function literal），我们可绕过这一限制，在任何表达式中表示一个函数值。函数字面量的语法和函数声明相似，区别在于func关键字后没有函数名。函数值字面量是一种表达式，它的值被成为匿名函数

更为重要的是，通过这种方式定义的函数可以访问完整的词法环境（lexical environment），这意味着在函数中定义的内部函数可以引用该函数的变量：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// squares返回一个匿名函数。
// 该匿名函数每次被调用时都会返回下一个数的平方。
func squares() func() int {
	var x int
	return func() int {
		x++
		return x * x
	}
}

func main() {
	f := squares()
	fmt.Println(f()) // "1"
	fmt.Println(f()) // "4"
	fmt.Println(f()) // "9"
	fmt.Println(f()) // "16"
}

squares的例子证明，函数值不仅仅是一串代码，还记录了状态。在squares中定义的匿名内部函数可以访问和更新squares中的局部变量，这意味着匿名函数和squares中，存在变量引用。这就是函数值属于引用类型和函数值不可比较的原因。

同时，这个例子说明了，变量的生命周期不由它的作用域决定：squares返回后，变量x仍然隐式的存在于f中。

当匿名函数需要被递归调用时，我们必须首先声明一个变量，再将匿名函数赋值给这个变量：

1
2
3
4
5
6
7
8
var preorder func(root *TreeNode)
preorder = func(root *TreeNode) {	// 二叉树的前序遍历
    if root != nil {
        visit(root)
        preorder(root.Left)
        preorder(root.Right)
    }
}

可变参数

在声明可变参数函数时，需要在参数列表的最后一个参数类型之前加上省略符号“…”，这表示该函数会接收任意数量的该类型参数：

1
2
3
4
5
6
7
8
9
10
11
func sum(vals...int) int {
	total := 0
	for _, val := range vals {
		total += val
	}
	return total
}

fmt.Println(sum()) 				// "0"
fmt.Println(sum(3))				// "3"
fmt.Println(sum(1, 2, 3, 4))	// "10"

调用者隐式的创建一个数组，并将原始参数复制到数组中，再把数组的一个切片作为参数传给被调函数。如果原始参数已经是切片类型，只需在最后一个参数后加上省略符

1
2
values := []int{1, 2, 3, 4}
fmt.Println(sum(values...)) // "10"

虽然在可变参数函数内部，...int 型参数的行为看起来很像切片类型，但实际上，可变参数函数和以切片作为参数的函数是不同的

1
2
3
4
func f(...int) {}
func g([]int) {}
fmt.Printf("%T\n", f)	// "func(...int)"
fmt.Printf("%T\n", g)	// "func([]int)"

defer语句

当defer语句被执行时，跟在defer后面的函数会被延迟执行。直到包含该defer语句的函数执行完毕时，defer后的函数才会被执行，不论包含defer语句的函数是通过return正常结束，还是由于panic导致的异常结束。你可以在一个函数中执行多条defer语句，它们的执行顺序与声明顺序相反。

释放资源

defer语句经常被用于处理成对的操作，如打开、关闭、连接、断开连接、加锁、释放锁。通过defer机制，不论函数逻辑多复杂，都能保证在任何执行路径下，资源被释放。释放资源的defer应该直接跟在请求资源的语句后。如文件操作：

1
2
3
4
5
6
7
8
func ReadFile(filename string) ([]byte, error) {
	f, err := os.Open(filename)
    defer f.Close()
	if err != nil {
		return nil, err
	}
	return ReadAll(f)
}

记录何时进入、退出函数

调试复杂程序时，defer机制也常被用于记录何时进入和退出函数。下面的例子中，bigSlowOperation函数开始时会执行trace函数，当bigSlowOperation退出前会执行trace返回的函数。只需要一条语句，就可以控制住函数的入口和出口：

1
2
3
4
5
6
7
8
9
10
11
12
13
func bigSlowOperation() {
	defer trace("bigSlowOperation")() // don't forget the extra parentheses
	// ...lots of work…
	time.Sleep(10 * time.Second) // simulate slow operation by sleeping
}

func trace(msg string) func() {
	start := time.Now()
	log.Printf("enter %s", msg)
	return func() {
		log.Printf("exit %s (%s)", msg,time.Since(start))
	}
}

观察、修改返回值

defer语句中的函数会在return语句更新返回值变量后再执行，又因为在函数中定义的匿名函数可以访问该函数包括返回值变量在内的所有变量，所以，对匿名函数采用defer机制，可以使其观察函数的返回值：

1
2
3
4
5
6
7
8
func double(x int) (result int) {
	defer func() { fmt.Printf("double(%d) = %d\n", x,result) }()
	return x + x
}

_ = double(4)
// Output:
// "double(4) = 8"

被延迟执行的匿名函数甚至可以修改函数返回给调用者的返回值：

1
2
3
4
5
func triple(x int) (result int) {
	defer func() { result += x }()
	return double(x)
}
fmt.Println(triple(4)) // "12"

异常处理

panic异常

当panic异常发生时，程序会中断运行，并立即执行在该goroutine中被延迟的函数（defer 机制）。随后，程序崩溃并输出日志信息。日志信息包括panic value和函数调用的堆栈跟踪信息。

panic异常和其他语言异常的不同：

虽然Go的panic机制类似于其他语言的异常，但panic的适用场景有一些不同。由于panic会引起程序的崩溃，因此panic一般用于严重错误，如程序内部的逻辑不一致。

对于大部分漏洞，我们应该使用Go提供的错误机制，而不是panic，尽量避免程序的崩溃。在健壮的程序中，任何可以预料到的错误，如不正确的输入、错误的配置或是失败的I/O操作都应该被优雅的处理，最好的处理方式，就是使用Go的错误机制，即返回一个额外的返回值，通常是最后一个，来传递错误信息

recover捕获异常

通常来说，不应该对panic异常做任何处理，但有时，也许我们可以从异常中恢复，至少我们可以在程序崩溃前，做一些操作。举个例子，当web服务器遇到不可预料的严重问题时，在崩溃前应该将所有的连接关闭；如果不做任何处理，会使得客户端一直处于等待状态。

如果在deferred函数中调用了内置函数recover，并且定义该defer语句的函数发生了panic异常，recover会使程序从panic中恢复，并返回panic value。导致panic异常的函数不会继续运行，但能正常返回。在未发生panic时调用recover，recover会返回nil。

1
2
3
4
5
6
7
8
func Parse(input string) (s *Syntax, err error) {
	defer func() {
		if p := recover(); p != nil {
			err = fmt.Errorf("internal error: %v", p)
		}
	}()
	// ...parser...
}

应该有选择性的recover。换句话说，只恢复应该被恢复的panic异常。为了标识某个panic是否应该被恢复，我们可以将panic value设置成特殊类型。在recover时对panic value进行检查，如果发现panic value是特殊类型，就将这个panic作为error处理，如果不是，则按照正常的panic进行处理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func f() (res string, err error) {
    type someKindError struct{}
    defer func(){
        switch p := recover(); p {
            case nil:	//	no panic
            case someKindError{}:	// expected panic
            	err = fmt.Errorf("Take place someKindError.....")
            default:
            	panic(p)	// unexpected panic
        }
    }()
    // 其他工作
    // ....
    if 某种类型的异常发生了{
        panic(someKindError{})
    }
}

发表于 更新于 分类于

Map

GO语言中，map是一个无序的key/value对的集合，其中所有的key都是不同的，然后通过给定的key可以在常数时间复杂度内检索、更新或删除对应的value

一个map就是一个哈希表的引用，所以map作为函数的参数时，是引用传递的。map类型可以写为map[K]V，其中K和V分别对应key和value。map中所有的key都有相同的类型，所有的value也有着相同的类型，但是key和value之间可以是不同的数据类型。其中K对应的key必须是支持==比较运算符的数据类型，所以map可以通过测试key是否相等来判断是否已经存在。

内置的delete函数可以删除元素（元素不在map中也没关系）：

1
delete(hashMap, "dawn")	// 从map中移除key为dawn的元素

但是map中的元素并不是一个变量，因此我们不能对map的元素进行取址操作。禁止对map元素取址的原因是map可能随着元素数量的增长而重新分配更大的内存空间，从而可能导致之前的地址无效：

1
p := &hashMap["dawn"]	// error

和slice一样，map之间也不能进行相等比较；唯一的例外是和nil进行比较。

遍历顺序随机

map遍历的顺序是随机的，每一次遍历的顺序都不相同。这是故意的，每次都使用随机的遍历顺序可以强制要求程序不会依赖具体的哈希函数实现。如果要按顺序遍历key/value对，我们必须显式地对key进行排序

1
2
3
4
5
6
7
8
9
10
11
var names []string

for name := range ages {
    names = append(names, name)
}
// 显式的对key排序
sort.Strings(names)
// 依据顺序的key对map顺序遍历
for _, name := range names {
    fmt.Printf("%s\t%d\n", name, ages[name])
}

判断元素是否存在

通过key作为索引下标来访问map将产生一个value。如果key在map中是存在的，那么将得到与key对应的value；如果key不存在，那么将得到value对应类型的零值。如果需要区分已存在的零值和不存在的零值，可以进行以下操作，第二个布尔值ok用于报告元素是否真的存在：

1
2
3
if age, ok := ages["dawn"]; !ok {
    // ...
}

绕过key必须是可比较的限制

有时候需要map的key是slice类型，但是map的key必须是可比较的，可以通过两步来绕过此限制：

  • 定义一个函数k，将slice转为string类型，作为map的key来使用
  • 创建一个key为string的map，在每次对map操作时先用k辅助函数将slice转化为string类型
1
2
3
4
5
6
7
func k(list []string) string {	// 将slice转为string
    return fmt.Sprintf("%q", list)
}

var hashMap = make(map[string]int)
keySlice := []string{/* ... */}
hashMap[k(keySlice)]++	// 对map操作时先将slice转为string

使用同样的技术可以处理任何不可比较的key类型，而不仅仅是slice类型。这种技术对于想使用自定义key比较函数的时候也很有用，例如在比较字符串的时候忽略大小写。同时，辅助函数k(x)也不一定是字符串类型，它可以返回任何可比较的类型，例如整数、数组或结构体等。

结构体

结构体是一种聚合数据类型，结构体类型的零值是每个成员都是零值。

同时结构体在作为函数参数时默认是值传递的，也就是说函数中使用的是结构体的拷贝

结构体的比较

如果结构体的全部成员都是可以比较的，那么结构体也是可以比较的，那样的话两个结构体将可以使用==或!=运算符进行比较。在相等比较时，将比较两个结构体的每个成员

所以，可比较的结构体可以作为map的key类型

1
2
3
4
5
6
type address struct {
    hostname string
    port int
}

counts := make(map[address]int)		// address结构体作为key

结构体嵌入和匿名成员

一个结构体可以嵌入另一个结构体中，使得结构体的类型变得清晰了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 坐标点
type Point struct {
	X, Y int
}
// 圆
type Circle struct {
	Center Point	// 圆心
	Radius int		// 半径
}
// 轮子
type Wheel struct {
	Circle Circle
	Spokes int		// 径向辐条的数量
}

但是这会使得访问每个成员变得繁琐：

1
2
3
4
5
var w Wheel
w.Circle.Center.X = 1
w.Circle.Center.Y = 1
w.Circle.Radius = 2
w.Spokes = 10

所以可以使用匿名成员：

1
2
3
4
5
6
7
8
type Circle struct {
	Point		// 匿名结构体
	Radius int
}
type Wheel struct {
	Circle		// 匿名结构体
	Spokes int
}

得意于匿名嵌入的特性，我们可以直接访问叶子属性而不需要给出完整的路径：

1
2
3
4
5
var w Wheel
w.X = 1
w.Y = 1
w.Radius = 2
w.Spokes = 10d

简短的点运算符语法可以用于选择匿名成员嵌套的成员，也可以用于访问它们的方法。实际上，外层的结构体不仅仅是获得了匿名成员类型的所有成员，而且也获得了该类型导出的全部的方法

发表于 更新于 分类于

数组

特点

  • 数组长度固定，所以在声明阶段必须显示的声明数组长度
1
2
3
4
5
6
// 声明一个长度为10的int数组var 
a [10]int
// 数组的长度是根据初始化值的个数来计算
b := [...]int{1, 2, 3}
// 定义了一个含有100个元素的数组r，最后一个元素被初始化为-1，其它元素都是用0初始化
c := [...]int{99: -1}

  • 数组的长度必须是常量表达式，因为数组的长度需要在编译阶段确定

  • 同类型数组之间可以相互比较。如果一个数组的元素类型是可以相互比较的，那么数组类型也是可以相互比较的，这时候我们可以直接通过==比较运算符来比较两个数组，只有当两个数组的所有元素都是相等的时候数组才是相等的

1
2
3
4
5
6
a := [2]int{1, 2}
b := [...]int{1, 2}
c := [2]int{1, 3}
fmt.Println(a == b, a == c, b == c) // "true false false"
d := [3]int{1, 2}
fmt.Println(a == d) // compile error: cannot compare [2]int == [3]int
阅读全文 »

发表于 更新于 分类于

字符串

GO语言中的字符串是由UTF-8编码的，所以GO语言字符串是变宽字符序列，每一个字符都用1到4个字节表示。

字符串不可变

字符串的值是不可变的，意味着：

  • 如果两个字符串共享相同的底层数据的话也是安全的，这使得复制任何长度的字符串代价是低廉的。

  • 同样，一个字符串s和对应的子字符串切片s[7:]的操作也可以安全地共享相同的内存，因此字符串切片操作代价也是低廉的。

在这两种情况下都没有必要分配新的内存。

字符串切片共享内存

注意：Go语言的range循环在处理字符串的时候，会自动隐式解码UTF8字符串

bytes.Buffer

bytes.Buffer是一个实现了读写方法的可变大小的字节缓冲。

使用bytes.Buffer进行字符串的累加比起+=要高效的多，尤其是在面对大数量的字符串时

1
2
3
4
var b bytes.Buffer // A Buffer needs no initialization.
b.Write([]byte("Hello "))
fmt.Fprintf(&b, "world!")
b.WriteTo(os.Stdout)

发表于 更新于 分类于

垃圾回收GC

Mutator 即用户线程，Collector 为 GC 线程。

Serial GC：只有一个 Collector

Parallel GC：支持多个 Collector 同时回收

Concurrent GC：Mutator 和 Collector 可用同时执行

1655261106302

经典垃圾回收策略

追踪垃圾回收

  • 被回收的条件：不可达的对象

  • 过程：

    • 标记根对象 (GC roots): 静态变量、全局变量、常量、线程栈等标记为存活

    • 标记：从根对象出发，找到所有可达对象

    • 清理：回收所有不可达对象占据的内存空间。清理策略如下：

      • Copying GC: 将存活对象从一块内存空间复制到另外一块内存空间，原先的空间可以直接进行对象分配

      img

      • Mark-sweep GC: 将死亡对象所在内存块标记为可分配，使用 free list 管理可分配的空间。缺点在于：会产生内存碎片。

      img

      • Mark-compact GC: 将存活对象复制到同一块内存区域（原地）的开头。缺点在于：压缩计算的成本（需要计算位置，同时需要改变引用对象的指针）、实现复杂。

      img

阅读全文 »

发表于 更新于 分类于

二叉树的完全性检验

二叉树的完全性检验

解题思路

对一个完全二叉树进行层序遍历时，其特点就是：若遍历到一个节点左/右子树为空，那么这个节点的所有右边的节点和下层节点的左右子树都为空。可以根据这个特性来进行二叉树的完全性检验

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isCompleteTree(root *TreeNode) bool {
    q := []*TreeNode{root}  // 队列
    var flag bool   // 标记是否已经碰到过左/右子树为空的节点

    // 开始层序遍历
    for i := 0; len(q) > 0; i++ {
        p := []*TreeNode{}  // p记录下一层节点
        for j := 0; j < len(q); j++ {
            cur := q[j] // 当前遍历节点

            if cur.Left != nil && !flag{
                // 左子树入队
                p = append(p, cur.Left)
            } else if cur.Left != nil && flag{
                // 已经遇到了左/右子树为空的节点，且当前节点的左子树非空，不是完全二叉树
                return false
            } else {
                flag = true
            }

            if cur.Right != nil && !flag{
                // 右子树入队
                p = append(p, cur.Right)
            } else if cur.Right != nil && flag{
                // 已经遇到了左/右子树为空的节点，且当前节点的右子树非空，不是完全二叉树
                return false
            } else {
                flag = true
            }
        }
        q = p   // 访问下一层节点
    }

    // 遍历完成，说明是完全二叉树
    return true
}

最长连续序列

最长连续序列

解题思路

  1. 用哈希表记录数组中的元素。对于数组中的元素x，首先查看数组中是否有x-1，若有则跳过x；若没有x-1，则进行枚举x+1, x+2, ...，同时记录连续序列的长度，从而得到最长连续序列的长度

解题代码

  1. 哈希表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func longestConsecutive(nums []int) int {
    hashMap := map[int]bool{}  // 哈希表记录已有数字
    for _, v := range nums {    // 初始化哈希表
        hashMap[v] = true
    }
    var MaxLength int  // 数字连续的最长序列的长度

    for _, v := range nums {
        if !hashMap[v-1] {     // 没有等于v-1的元素，无需跳过
            curLength := 1  // 当前数字连续的序列长度
            i := 1
            for hashMap[v+i] {
                curLength++
                i++
            }
            if curLength > MaxLength {
                // 更新最大长度
                MaxLength = curLength
            }
        }
    }

    return MaxLength
}

寻找旋转排序数组中的最小值

寻找旋转排序数组中的最小值

解题思路

因为整个升序数组在旋转后，可以分为两部分，并且这两部分都是升序排列的，同时第一部分的所有元素比第二部分的所有元素大。基于二分查找，通过判断mid指向第一部分还是第二部分来更新low和high指针：

  • 若nums[mid] > nums[high]，则mid指向第一部分，最小元素在mid左侧，low更新为mid+1
  • 否则mid指向第二部分，最小元素为mid或者在mid右侧，high更新为mid

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func findMin(nums []int) int {
    low, high := 0, len(nums)-1
    var mid int

    for low < high {
        mid = (low+high)/2
        if nums[mid] > nums[high] {
            // 最小元素在mid左侧
            low = mid + 1
        } else {
            // 最小元素为mid或者在mid右侧
            high = mid
        }
    }

    return nums[low]
}

寻找峰值

寻找峰值

解题思路

  1. 因为nums[-1] = nums[n] = -∞，索引找到数组中的最大值即可，这个最大值就是峰值

  2. 爬坡的思想，随机一个下标i，沿着上升的方向走，一定可以到峰值

    • 若nums[i] < nums[i+1]，则向右侧走一定可以到达峰值
    • 否则，向左侧走一定可以到达峰值

  3. 基于二分查找，查找时比较nums[mid]与nums[mid+1]的值：

    • 如果nums[mid] < nums[mid+1]，则右侧存在峰值，low = mid+1
    • 否则，左侧存在峰值，high = mid

解题代码

  1. 找到最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
func findPeakElement(nums []int) int {
    max := nums[0]   // 最大值初始化为nums[0]
    maxIndex := 0   // 最大值元素的下标

    for i := 1; i < len(nums); i++ {    // 寻找最大值，最大值必为峰值
        if nums[i] > max {
            max = nums[i]
            maxIndex = i
        }
    }

    return maxIndex
}
  1. 爬坡
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func findPeakElement(nums []int) int {
    n := len(nums)  // 数组长度
    i := rand.Intn(n)   // 随机下标i
    right := (i+1 < n) && (nums[i+1] > nums[i])  // 向右走的标记，true为向右走，false为向左走

    for {
        if right {  // 向右走
            if i+1 < n && nums[i+1] > nums[i] {
                i++     // 继续向右
            } else {
                // 到达峰值
                break
            } 
        }

        if !right {    // 向左走
            if i-1 >= 0 && nums[i-1] >nums[i] {
                i--     // 继续向左
            } else {
                // 到达峰值
                break
            }   
        }
    }

    return i
}
  1. 二分查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func findPeakElement(nums []int) int {
    low, high := 0, len(nums)-1

    for low < high {
        mid := (low+high)/2
        
        if nums[mid] < nums[mid+1] {    // 右侧存在峰值
            low = mid + 1
        } else {    // 左侧存在峰值
            high = mid
        }
    }

    return low
}

发表于 更新于 分类于

索引的使用

查看索引

1
SHOW INDEX FROM 表名;

创建索引

创建表的时候添加索引

  1. 隐式的方式添加索引：在声明有主键约束、唯一性约束、外键约束的字段上，会自动的添加索引
1
2
3
4
5
6
7
8
9
10
11
12
CREATE TABLE dept(
    dept_id INT PRIMARY KEY AUTO_INCREMENT,	# 主键约束，自动添加索引
    dept_name VARCHAR(20)
);

CREATE TABLE emp(
    emp_id INT PRIMARY KEY AUTO_INCREMENT,	# 主键约束
    emp_name VARCHAR(20) UNIQUE,	# 唯一性约束，自动添加索引
    dept_id INT,
    # 外键约束，自动添加是索引
    CONSTRAINT emp_dept_id_fk FOREIGN KEY(dept_id) REFERENCES dept(dept_id)
);
阅读全文 »

发表于 更新于 分类于

页概述

InnoDB将数据划分为若干个页，InnoDB中数据页的默认大小为16KB。数据库管理存储空间的基本单位是页，数据库IO操作的最小单位是页。

页之间不在物理上相邻，通过双向链表相关联。数据页中的每条记录通过单向链表按照顺序连接

页的上层结构

数据库中，还存在着区（Extent）、段（Segment）和表空间（Tablespace）的概念。它们的关系如下：

结构关系

区（Extent）：比页大一级的存储结构，在InnoDB中，一个区会分配64个连续的页。一个区的大小是64*16KB=1MB

段（Segment）：由一个或者多个区组成，区在文件系统中是一个连续的空间，在段中区之间不要求相邻。段是数据库中的分配单位，不同类型的数据库对象以不同的段形式存在。在创建数据表、索引的时候会创建相应的段

表空间（Tablespace）：是一个逻辑容器，一个表空间中有一个或者多个段。数据库由一个或者多个表空间组成，表空间从管理上可以划分为系统表空间、用户表空间、撤销表空间、临时表空间等。

页的内部结构

页的内部结构可以分为7个部分，分别是文件头、页头、最大最小记录、用户记录、空闲空间、页目录、文件尾：

页结构示意图

阅读全文 »