Dawn's Blogs

分享技术 记录成长

0%

发表于 更新于 分类于

Redis概述

介绍

Redis是一个高性能的key-value数据库，默认端口号6379

Redis有以下特点：

  • Redis支持数据持久化，可以将内存中的数据保存在磁盘中
  • Redis支持的类型更丰富，包括string(字符串)、list(链表)、set(集合)、zset(sorted set –有序集合)和hash（哈希类型）
  • Redis支持数据的备份，master-slave(主从)同步

Redis 和memcache有三点不同：

  • 支持多数据类型。
  • 支持持久化。
  • 单线程+多路IO复用（memcache为多线程）
阅读全文 »

发表于 更新于 分类于

螺旋矩阵 II

螺旋矩阵 II

解题思路

生成一个空的矩阵，随后模拟整个向内环绕的填入过程。定义上下左右边界up, down, left, right，设被填入的数字为num。当num <= n*n时循环，始终按照上、右、下、左的顺序填入数字

解题代码

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
func generateMatrix(n int) [][]int {
    // 生成一个空矩阵
    matrix := make([][]int, n)
    for i := 0; i < n; i++ {
        matrix[i] = make([]int, n)
    }
    // 定义上下左右边界
    up, down, left, right := 0, n-1, 0, n-1
    num := 1    // 待填入的数字
    // 螺旋遍历矩阵，填入数字
    for num <= n*n {
        // 填写上边界
        for i := left; i <= right; i++ {
            matrix[up][i] = num
            num++
        }
        up++
        // 填写右边界
        for i := up; i <= down; i++ {
            matrix[i][right] = num
            num++
        }
        right--
        // 填写下边界
        for i := right; i >= left; i-- {
            matrix[down][i] = num
            num++
        }
        down--
        // 填写左边界
        for i := down; i >= up; i-- {
            matrix[i][left] = num
            num++
        }
        left++
    }

    return matrix
}
阅读全文 »

发表于 更新于 分类于

范式

在关系型数据库中，关于数据表设计得基本原则/规则，就称为范式（Normal Form，NF）。目前关系型数据库有六种常见范式，按照范式级别从低到高分别是：第一范式（1NF）、第二范式（2NF）、第三范式（3NF）、巴斯-科德范式（BCNF）、第四范式（4NF）和第五范式（5NF）

数据库得范式设计越高阶，冗余度越低，同时高阶范式一定满足低阶范式得要求。一般在关系型数据库设计中，最高也就遵循到BCNF，普遍还是3NF。但是有些时候为了提高查询性能，还需要破坏范式规则，称为反规范化。

阅读全文 »

发表于 更新于 分类于

RPC

简介

RPC（Remote Procedure Call，远程过程调用）允许一台计算机通过网络从远程计算机的程序中请求服务。RPC协议构建于TCP或UDP，或者是HTTP上。允许开发者直接调用另一台服务器上的程序，而开发者无需另外的为这个调用过程编写网络通信相关代码。

RPC允许跨机器、跨语言调用计算机程序方法。

工作原理

运行时，一次客户机对服务器的 RPC 调用，其内部操作大致有如下：

  1. 调用客户端句柄：执行传送参数
  2. 调用本地系统内核发送网络消息
  3. 消息传送到远程主机
  4. 服务器句柄得到消息并取得参数
  5. 执行远程过程
  6. 执行的过程将结果返回服务器句柄
  7. 服务器句柄返回结果，调用远程系统内核
  8. 消息传回本地主机
  9. 客户句柄由内核接收消息
  10. 客户接收句柄返回的数据

img

RPC vs RESTful

RPC 可以通过 TCP、UDP 或者 HTTP 等进行传输消息，称为 RPC over TCP、RPC over HTTP。

首先比较 RPC over HTTP 和 RESTful：

  • RPC 的客户端和服务器是紧密耦合的，，客户端需要知道调用的过程的名字，过程的参数以及它们的类型、顺序等。一旦服务器更改了过程的实现， 客户端的实现很容易出问题。RESTful 的客户端和服务器是松散的关系，客户端并不关心服务器端的具体实现，比较灵活。
  • 它们操作的对象不一样。RPC 操作的是方法对象，而 RESTful 操作的是资源。
  • RESTful 执行的是对资源的增删改查（CRUD），如果实现一个其他具体操作 RPC 的实现更加具有意义。

接着比较 RPC over TCP 和 RESTful：

  • RPC over TCP 减少了 HTTP 协议带来的额外开销（如HTTP 请求头）。
  • RPC over TCP 可以通过长连接减少连接的建立所产生的花费，当然 RESTful 也可以通过 keep-alive 实现长连接，但是它最大的一个问题是它的 request-response 模型是阻塞的（HTTP 1.0 和 HTTP 1.1 是阻塞的，HTTP 2.0 不是），发送一个请求得到响应后才能发送第二个，而 RPC 没有这个限制。

Go RPC

GO语言官方提供了net/rpc包实现RPC，使用encoding/gob进行编解码，支持TCP或者HTTP数据传输方式，由于其他语言不支持gob编解码方式，所以使用net/rpc实现的RPC方法没办法实现跨语言调用。

net/rpc 介绍

net/rpc包允许PRC客户端程序通过网络或者其他IO连接，调用一个远程对象的公开方法。在PRC服务端，可将一个对象注册为可访问的服务，之后该对象的公开方法就能够以远程的方式提供访问。一个RPC服务端可以注册多个不通类型的对象，但不允许注册同一类型的多个对象。

只有满足如下标准的方法才能用于远程访问，其余方法会被忽略：

  • 方法是导出的（首字母大写）
  • 方法有两个参数，第一个参数是接收的参数，第二个参数是返回给客户端的参数
  • 方法的第二个参数是指针
  • 方法只有一个error接口类型的返回值

事实上，方法必须看起来像这样：

1
func (t *T) MethodName(argType T1, replyType *T2) error

方法的第一个参数代表调用者提供的参数；第二个参数代表返回给调用者的参数。方法的返回值，如果非nil，将被作为字符串回传，在客户端看来就和errors.New创建的一样。如果返回了错误，回复的参数将不会被发送给客户端。

阅读全文 »

发表于 更新于 分类于

移动零

移动零

解题思路

  1. 利用冒泡，元素交换的基本思想：当num[i] == 0 && nums[i+1] != 0时交换元素。若本轮没有交换元素，可以提前跳出循环

  2. 双指针法，两次遍历。创建两个指针i和j，第一次遍历的时候指针j记录有多少个非零元素。第一次遍历完后，j指针的下标就指向了最后一个非零元素下标。第二次遍历的时候，起始位置就从j开始，将剩下的这段区域内的元素全部置为0

  3. 双指针法，一次遍历。参照了快速排序的基本思想，把0作为中间点，把不等于0的放到中间点的左边，等于0的放到其右边。使用两个指针i和j，只要nums[i]!=0，就交换nums[i]和nums[j]

阅读全文 »

发表于 更新于 分类于

字符串解码

字符串解码

解题思路

利用两个栈，numStack记录需要重复的次数k，strStack记录扫描到的字符串。从左向右扫描字符串：

  • 若遇到数字：压入numStack中
  • 若遇到左括号或者字母：压入strStack中
  • 若遇到右括号：需要字符串解码
    • strStack中的字符串依次出栈组成待重复的子串subStr，直到遇到左括号为止
    • 弹出numStack栈顶元素k，使subStr重复k次并重新压入strStack中
  • 最后从底向顶扫描strStack，依次组成返回结果

解题代码

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
45
46
47
48
49
func decodeString(s string) string {
    numStack := make([]int, 0)      // 记录需要重复的次数
    strStack := make([]string, 0)   // 记录待解码的字符串
    i := 0      // 扫描字符串的下标
    for i < len(s) {
        if '0' <= s[i] && s[i] <= '9' {     // 若扫描到数字
            k := int(s[i]-'0')      // 重复次数k
            j := i+1
            for ; j < len(s) && '0' <= s[j] && s[j] <= '9'; j++ {   // 转化为int型
                k = k*10 + int(s[j]-'0')
            }
            // 重复次数入栈
            numStack = append(numStack, k)
            // 更新下标
            i = j
        } else if s[i] == ']' {     // 扫描到右括号，需要解码
            var subStr string      // 待解码的字符串
            // 依次出栈，直到遇到左括号
            cur := strStack[len(strStack)-1]
            for cur != "[" {
                subStr = cur + subStr
                strStack = strStack[:len(strStack)-1]
                cur = strStack[len(strStack)-1]
            }
            strStack = strStack[:len(strStack)-1]   // 弹出左括号
            // 弹出一个重复数字
            k := numStack[len(numStack)-1]
            numStack = numStack[:len(numStack)-1]
            // 重复k次，加入到栈中
            var encoded string
            for ; k > 0; k-- {
                encoded = encoded + subStr
            }
            strStack = append(strStack, encoded)
            i++
        } else {    // 扫描到字母、左括号时直接入栈
            strStack = append(strStack, string(s[i]))
            i++
        }
    }

    var res string      // 返回结果
    // 从底向顶扫描栈，依次加入结果
    for i := 0; i < len(strStack); i++ {
        res += strStack[i]
    }

    return res
}

手撕堆排序

手撕堆排序

解题思路

堆排序过程：

  • 首先建成大根堆：从最后一个分支节点开始，向上调整
  • 依次将大根堆的根节点与最后一个节点交换，使大根堆的长度减一，再从新的根节点开始向下调整；直到大根堆只剩一个元素

解题代码

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
45
46
func sortArray(nums []int) []int {
    len := len(nums)
    heapSort(nums, len)     // 堆排序

    return nums
}

func heapSort(nums []int, len int) {
    // 建成大根堆
    buildHeap(nums, len)
    
    for len > 1 {
        // 大根堆的根节点放到最后
        nums[0], nums[len-1] = nums[len-1], nums[0]
        // 剩余节点重新调整为大根堆
        len--
        adjestHeap(nums, 0, len)
    }
    
}

func buildHeap(nums []int, len int) {
    for i := (len/2)-1; i >= 0; i-- {   // 从最后一个分支节点开始，依次向上调整堆
        adjestHeap(nums, i, len)
    }
}

func adjestHeap(nums []int, i, len int) {   // 以nums[i]为根节点调整成大根堆
    for 2*(i+1) <= len {     // 自上而下调整
        leftChild := 2*(i+1)-1      // 左孩子下标
        rightChild := leftChild+1   // 右孩子下标
        var larger int  // 左右孩子中较大者的下标
        if rightChild < len && nums[rightChild] > nums[leftChild] {
            // 右孩子较大
            larger = rightChild
        } else {
            // 左孩子较大
            larger = leftChild
        }
        if nums[i] < nums[larger] {
            // 孩子节点更大，则交换
             nums[i], nums[larger] = nums[larger], nums[i]
        }
        i = larger
    }
}

二叉搜索树的第k大节点

二叉搜索树的第k大节点

解题思路

求出右子树的节点个数rightNodeNum：

  • 若k == rightNodeNum+1，当前根节点就是第k大的节点，返回根节点的值
  • 若k <= rightNodeNum，说明第k大的节点在右子树中，递归寻找右子树的第k大节点
  • 否则第k大的节点在左子树中，递归寻找左子树的第(k-1-rightNodeNum)大的节点

解题代码

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
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func kthLargest(root *TreeNode, k int) int {
    rightNodeNum := nodeNum(root.Right)    // 右子树节点个数
    if k == rightNodeNum+1 {
        // 当前根节点就是第k大节点
        return root.Val
    } else if k <= rightNodeNum {
        // 第k大节点在右子树中
        return kthLargest(root.Right, k)
    } else {
        // 第k大节点在左子树中
        // 在左子树中找第(k-1-rightNodeNum)大的节点
        return kthLargest(root.Left, k-1-rightNodeNum)
    }
}

func nodeNum(root *TreeNode) int {      // 求以root为根节点的树的节点总数
    if root != nil {
        left := nodeNum(root.Left)      // 左子树的节点个数
        right := nodeNum(root.Right)    // 右子树的节点个数
        
        return 1+left+right
    } else {
        return 0
    }
}

二叉树的后序遍历

二叉树的后序遍历

解题思路

  1. 递归法
  2. 非递归法

解题代码

  1. 递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func postorderTraversal(root *TreeNode) []int {
    res := []int{}
    var postorder func(root *TreeNode)
    postorder = func(root *TreeNode) {
        if root != nil {
            postorder(root.Left)
            postorder(root.Right)
            res = append(res, root.Val)
        }
    }
    postorder(root)

    return res
}
  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
28
29
30
31
32
33
34
35
36
37
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func postorderTraversal(root *TreeNode) []int {
    res := make([]int, 0)
    stack := make([]*TreeNode, 0)
    cur := root
    var pre *TreeNode

    for len(stack) > 0 || cur != nil {
        for cur != nil {
            stack = append(stack, cur)
            cur = cur.Left
        }
        if len(stack) > 0 {
            cur = stack[len(stack)-1]
            if cur.Right == nil || pre == cur.Right {
                // 若栈顶节点右子树为空，或者刚刚遍历过右子树
                // 遍历栈顶节点并弹出
                res = append(res, cur.Val)
                pre = cur
                stack = stack[:len(stack)-1]
                cur = nil
            } else {
                // 否则进入右子树
                cur = cur.Right
            }
        }
    }

    return res
}

发表于 更新于 分类于

接口

接口类型是对其它类型行为的抽象和概括；因为接口类型不会和特定的实现细节绑定在一起，通过这种抽象的方式我们可以让我们的函数更加灵活和更具有适应能力

概述

接口是抽象的数据类型，仅仅定义了行为（方法）。一个类型如果拥有一个接口需要的所有方法，那么这个类型就实现了这个接口。

发表于 更新于 分类于

方法

方法是与类型相关联的函数

方法声明

一个方法的声明如下，其中参数p，叫做方法的接收器（receiver）：

1
2
3
4
5
6
7
8
9
10
import "math"

type Point struct {
    X, Y float64
}

// 一个方法的声明
func (p Point) Distance(q Point) float64 {
    return math.Htpot(q.X-p.X, q.Y-p.Y)
}

可以给同一个包内的任意命名类型（基础数据类型需要起别名）定义方法，只要这个命名类型的底层类型不是指针或者interface

指针类型的接收器

也可以定义接收器对象为指针类型，这样可以避免拷贝、或者更新接收器对象：

1
2
3
4
5
// 接收器为指针类型
func (p *Point) ScaleBy(factor float64) {
	p.X *= factor
	p.Y *= factor
}

注意：

  • 不管方法的接收器是指针类型还是非指针类型，都是可以通过指针/非指针类型进行调用的，编译器会自动做隐式类型转换

  • nil可以作为接收器

嵌入结构体扩展类型

可以嵌入其他结构体，嵌入匿名结构体时，可以直接访问叶子属性而不需要给出完整的路径、也可以拥有匿名结构体的所有方法

1
2
3
4
5
6
7
8
9
10
11
12
type Point struct{
    X, Y float64 
}

type RGBA struct {
    R, G, B, A uint8
}

type ColoredPoint struct {
	Point				// 嵌入匿名结构体
	Color color.RGBA
}

同时，可以把ColoredPoint类型当作接收器来调用Point里的方法，即使ColoredPoint里没有声明这些方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
red := color.RGBA{255, 0, 0, 255}
blue := color.RGBA{0, 0, 255, 255}

var p = ColoredPoint{Point{1, 1}, red}
var q = ColoredPoint{Point{5, 4}, blue}

fmt.Println(p.Distance(q.Point)) // "5"
p.ScaleBy(2)
q.ScaleBy(2)
fmt.Println(p.Distance(q.Point)) // "10"

/*
p.Distance(q) // compile error: cannot use q (ColoredPoint) as Point
*/

一个ColoredPoint并不是一个Point，但他**”has a”Point**，并且它有从Point类里引入的Distance和ScaleBy方法。Distance函数的参数类型是Point，所以必须显式地选择q.Point

方法值和方法表达式

方法值

常用p.Distance()调用方法，实际上将其分成两步来执行也是可能的。p.Distance叫作选择器，选择器会返回一个方法值：一个将方法Point.Distance绑定到特定接收器变量的函数。

这个函数可以不通过指定其接收器即可被调用，因为已经在前文中指定过了，只要传入函数的参数即可

1
2
3
4
5
6
7
8
9
10
11
12
p := Point{1, 2}
q := Point{4, 6}

distanceFromP := p.Distance			// method value
fmt.Println(distanceFromP(q))		// "5"
var origin Point					// {0, 0}
fmt.Println(distanceFromP(origin))	// "2.23606797749979", sqrt(5)

scaleP := p.ScaleBy		// method value
scaleP(2)				// p becomes (2, 4)
scaleP(3)				// then (6, 12)
scaleP(10)				// then (60, 120)

方法表达式

当T是一个类型时，方法表达式可能会写作T.f或者(*T).f，会返回一个函数”值”，这种函数会将其第一个参数用作接收器：

1
2
3
4
5
6
7
8
9
10
11
p := Point{1, 2}
q := Point{4, 6}

distance := Point.Distance // method expression
fmt.Println(distance(p, q)) // "5"
fmt.Printf("%T\n", distance) // "func(Point, Point) float64"

scale := (*Point).ScaleBy
scale(&p, 2)
fmt.Println(p) // "{2 4}"
fmt.Printf("%T\n", scale) // "func(*Point, float64)"

当你根据一个变量来决定调用同一个类型的哪个函数时，方法表达式就显得很有用了。可以根据选择来调用接收器各不相同的方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
type Point struct{ X, Y float64 }

func (p Point) Add(q Point) Point { return Point{p.X + q.X, p.Y + q.Y} }
func (p Point) Sub(q Point) Point { return Point{p.X - q.X, p.Y - q.Y} }

type Path []Point

func (path Path) TranslateBy(offset Point, add bool) {
	var op func(p, q Point) Point
	if add {
		op = Point.Add
	} else {
		op = Point.Sub
	}
	for i := range path {
		// Call either path[i].Add(offset) or path[i].Sub(offset).
		path[i] = op(path[i], offset)
	}
}

封装

一个对象的变量或者方法如果对调用方是不可见的话，一般就被定义为封装。

Go语言只有一种控制可见性的手段：大写首字母的标识符会从定义它们的包中被导出，小写字母的则不会。这种基于名字的手段使得在语言中最小的封装单元是package，而不是像其它语言一样的类型，如一个struct类型的字段对同一个包的所有代码都有可见性。

封装的好处：

  • 隐藏实现细节

  • 可以对数据（某些字段）进行验证，保证安全合理

封装的步骤

  1. 将结构体、字段的首字母小写，使之不能导出
  2. 给结构体所在包提供一个工厂模式的函数，首字母大写，类似于构造函数
  3. 提供访问getter或修改setter内部变量的函数
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
package person

import "fmt"

// 定义不能导出的结构体
type person struct {
   name string
   age  int
   sal float64
}

// 定义工厂模式的函数 首字母大写 类似构造函数
func  NewPerson(name string) *person{
   return &person{
      name:name,
   }
}

// 提供一个setter 设置年龄
func (user *person) Setage(age int) {
   if age >0  && age < 150 {
      user.age = age
   }else {
      fmt.Println("年龄数值不对！")
   }
}

// 获取年龄
func (user *person) Getage() int{
   return  user.age
}

// 更改姓名
func  (user *person) Updatename(name string) string{
   user.name=name
   return  user.name
}

发表于 更新于 分类于

SQL查询优化大致上可以分为两种：

  • 物理查询优化：通过索引和表连接方式等技术进行优化
  • 逻辑查询优化：通过SQL等价变换来提升查询效率

索引创建的基本原则

联合索引优于单值索引

若WHERE过滤条件中有涉及到多个列，那么对多个列创建联合索引的查询效率高于对单个列创建的索引查询效率

最佳左前缀法则

在MySQL建立联合索引时，会遵循最佳左前缀匹配原则，在检索数据时从联合索引的最左边开始匹配。也就是说，过滤条件要使用索引必须按照索引建立时的顺序，一旦某个顺序与联合索引的顺序不匹配，后面的字段无法使用索引。

引文件具有B-Tree的最左前缀匹配特性，如果左边的值未确定，那么无法使用此索引。

阅读全文 »

发表于 更新于 分类于

搜索二维矩阵 II

搜索二维矩阵 II

解题思路

  1. 对每一行进行二分查找

  2. 从二维矩阵的右上角开始，会发现每次都是向左数字会变小，向下数字会变大，有点和二分查找树相似。所以可以把target与当前值进行比较：

    • 如果target大于当前值，向下走
    • 如果target小于当前值，向左走
    • 如果target等于当前值，返回true
阅读全文 »