redis使用单线程模型,为什么效率也很高

1.redis是基于内存的,内存的读写速度非常快;

2.redis是单线程的,省去了很多上下文切换线程的时间;

3.redis使用多路复用技术,可以处理并发的连接。非阻塞IO 内部实现采用epoll,采用了epoll+自己实现的简单的事件框架。epoll中的读、写、关闭、连接都转化成了事件,然后利用epoll的多路复用特性,绝不在io上浪费一点时间。

最大连续1的个数 III

给定一个由若干 0 和 1 组成的数组 A,我们最多可以将 K 个值从 0 变成 1 。

返回仅包含 1 的最长(连续)子数组的长度。

示例 1:

输入:A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出:6
解释:
[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1,最长的子数组长度为 6。
示例 2:

输入:A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出:10
解释:
[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1,最长的子数组长度为 10。

题解:这道题目求的是最多可以把 K 个 0 变成 1,求仅包含 1 的最长子数组的长度,我们可以把它进行一次转换,找出一个最长的子数组,该子数组最多允许有K个0,这样子就好理解了,而且这道题一看就是使用滑动窗口来做。

func longestOnes(A []int, K int) (ans int) {
    var left, lsum, rsum int
    for right, v := range A {
        rsum += 1 - v
        for lsum < rsum - K {
            lsum += 1 - A[left]
            left++
        }
        ans = max(ans, right-left+1)
    }
    return 
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

K 连续位的最小翻转次数

在仅包含 0 和 1 的数组 A 中,一次 K 位翻转包括选择一个长度为 K 的(连续)子数组,同时将子数组中的每个 0 更改为 1,而每个 1 更改为 0。

返回所需的 K 位翻转的最小次数,以便数组没有值为 0 的元素。如果不可能,返回 -1。

示例 1:

输入:A = [0,1,0], K = 1
输出:2
解释:先翻转 A[0],然后翻转 A[2]。
示例 2:

输入:A = [1,1,0], K = 2
输出:-1
解释:无论我们怎样翻转大小为 2 的子数组,我们都不能使数组变为 [1,1,1]。
示例 3:

输入:A = [0,0,0,1,0,1,1,0], K = 3
输出:3
解释:
翻转 A[0],A[1],A[2]: A变成 [1,1,1,1,0,1,1,0]
翻转 A[4],A[5],A[6]: A变成 [1,1,1,1,1,0,0,0]
翻转 A[5],A[6],A[7]: A变成 [1,1,1,1,1,1,1,1]

题解:这道题目理解起来还是简单的,而且一看就是用滑动窗口来做,但是并不好写,根据官方的解释,用差分数组也可以去做,创建一个len(A)+1的数组,如果需要翻转就记录翻转次数,记录就是差分遍历的首位(i)加,末位(i+k)减。最后再利用差分求累计翻转次数;
如果需要翻转,但剩余元素长度已经不足K个,那么就是无法完成全置1的目标,返回-1即可。

func minKBitFlips(A []int, K int) (ans int) {
     n := len(A)
     diff := make([]int, n + 1)
     revCnt := 0
     for k, v := range A {
         revCnt += diff[k]
         if (revCnt + v) % 2 == 0 {
             if k + K > n {
                 return -1
             }
             ans++                                                                             
             revCnt++
             diff[k+K]--
         }
     }
     return
}

RabbitMQ Go语言客户端1 初始化

1. 准备环境

首先需要我们安装Erlang和RabbitMQ的Window版本,配置环境

RabbitMQ的下载地址https://www.rabbitmq.com/install-windows.html

Erlang的下载地址https://www.erlang.org/downloads

接下来配置环境变量,常规操作,新建系统变量-键入变量名ERLANG_HOME,键入变量值:erlang安装路径,然后添加系统path路径中,添加 : %ERLANG_HOME%\bin

RabbitMQ不需要添加,我们直接打开打安装目录下的sbin目录,cmd,输入

rabbitmq-plugins enable rabbitmq_management

启动成功,我们就可以通过http://localhost:15672来访问web端的管理界面

2.Golang

介绍一下

RabbitMQ是一个消息代理:它接受并转发消息。你可以把它想象成一个邮局:当你把你想要邮寄的邮件放进一个邮箱时,你可以确定邮差先生或女士最终会把邮件送到你的收件人那里。在这个比喻中,RabbitMQ是一个邮箱、一个邮局和一个邮递员。

RabbitMQ和邮局的主要区别在于它不处理纸张,而是接受、存储和转发二进制数据块——消息。

RabbitMQ和一般的消息传递都使用一些术语。

  • 生产仅意味着发送。发送消息的程序是生产者:
img
  • 队列是位于RabbitMQ内部的邮箱的名称。尽管消息通过RabbitMQ和你的应用程序流动,但它们只能存储在队列中。队列只受主机内存和磁盘限制的限制,实际上它是一个大的消息缓冲区。许多生产者可以向一个队列发送消息,而许多消费者可以尝试从一个队列接收数据。以下是我们表示队列的方式:
img
  • 消费与接收具有相似的含义。消费者是一个主要等待接收消息的程序:
img

请注意,生产者,消费者和代理(broker)不必位于同一主机上。实际上,在大多数应用程序中它们不是。一个应用程序既可以是生产者,也可以是消费者。

3.Golang操作

Go RabbitMQ客户端库

RabbitMQ讲多种协议。我们使用amqp0-9-1,这是一个开放的、通用的消息传递协议,我们需要先安装一下

go get github.com/streadway/amqp
  1. 发送
(P) -> [|||]

我们将消息发布者(发送者)称为 send.go,将消息消费者(接收者)称为receive.go。发布者将连接到RabbitMQ,发送一条消息,然后退出。

send.go中,我们需要首先导入库:

package main

import (
  "log"

  "github.com/streadway/amqp"
)

我们还需要一个辅助函数来检查每个amqp调用的返回值:

func failOnError(err error, msg string) {
  if err != nil {
    log.Fatalf("%s: %s", msg, err)
  }
}

然后连接到RabbitMQ服务器

// 1. 尝试连接RabbitMQ,建立连接
// 该连接抽象了套接字连接,并为我们处理协议版本协商和认证等。
conn, err := amqp.Dial("amqp://guest:guest@localhost:5672/")
failOnError(err, "Failed to connect to RabbitMQ")
defer conn.Close()

连接抽象了socket连接,并为我们处理协议版本协商和认证等。接下来,我们创建一个通道,这是大多数用于完成任务的API所在的位置:

// 2. 接下来,我们创建一个通道,大多数API都是用过该通道操作的。
ch, err := conn.Channel()
failOnError(err, "Failed to open a channel")
defer ch.Close()

要发送,我们必须声明要发送到的队列。然后我们可以将消息发布到队列:

// 3. 声明消息要发送到的队列
q, err := ch.QueueDeclare(
  "hello", // name
  false,   // durable
  false,   // delete when unused
  false,   // exclusive
  false,   // no-wait
  nil,     // arguments
)
failOnError(err, "Failed to declare a queue")

body := "Hello World!"
// 4.将消息发布到声明的队列
err = ch.Publish(
  "",     // exchange
  q.Name, // routing key
  false,  // mandatory
  false,  // immediate
  amqp.Publishing {
    ContentType: "text/plain",
    Body:        []byte(body),
  })
failOnError(err, "Failed to publish a message")

声明队列是幂等的——仅当队列不存在时才创建。消息内容是一个字节数组,因此你可以在此处编码任何内容。

2.接收

上面是我们的发布者。我们的消费者监听来自RabbitMQ的消息,因此与发布单个消息的发布者不同,我们将使消费者保持运行状态以监听消息并打印出来。

[|||] -> (C)

该代码(在receive.go中)具有与send相同的导入和帮助功能:

package main

import (
  "log"

  "github.com/streadway/amqp"
)

func failOnError(err error, msg string) {
  if err != nil {
    log.Fatalf("%s: %s", msg, err)
  }
}

设置与发布者相同;我们打开一个连接和一个通道,并声明要消耗的队列。请注意,这与send发布到的队列匹配。

// 建立连接
conn, err := amqp.Dial("amqp://guest:guest@localhost:5672/")
failOnError(err, "Failed to connect to RabbitMQ")
defer conn.Close()

// 获取channel
ch, err := conn.Channel()
failOnError(err, "Failed to open a channel")
defer ch.Close()

// 声明队列
q, err := ch.QueueDeclare(
  "hello", // name
  false,   // durable
  false,   // delete when unused
  false,   // exclusive
  false,   // no-wait
  nil,     // arguments
)
failOnError(err, "Failed to declare a queue")

请注意,我们也在这里声明队列。因为我们可能在发布者之前启动使用者,所以我们希望在尝试使用队列中的消息之前确保队列存在。

我们将告诉服务器将队列中的消息传递给我们。由于它将异步地向我们发送消息,因此我们将在goroutine中从通道(由amqp::Consume返回)中读取消息。

// 获取接收消息的Delivery通道
msgs, err := ch.Consume(
  q.Name, // queue
  "",     // consumer
  true,   // auto-ack
  false,  // exclusive
  false,  // no-local
  false,  // no-wait
  nil,    // args
)
failOnError(err, "Failed to register a consumer")

forever := make(chan bool)

go func() {
  for d := range msgs {
    log.Printf("Received a message: %s", d.Body)
  }
}()

log.Printf(" [*] Waiting for messages. To exit press CTRL+C")
<-forever

现在我们可以运行两个脚本。在一个终端窗口,运行发布者:

go run send.go

然后,运行使用者:

go run receive.go

消费者将打印通过RabbitMQ从发布者那里得到的消息。使用者将持续运行,等待消息(使用Ctrl-C停止它),因此请尝试从另一个终端运行发布者。

我们先可以在web端看见读取和接收的过程。

快速排序

快排排序的思想就是取一个基准数,比它小的放在左边,大的放在右边的这样一个思想,然后递归取值,直到子数组的长度小于2

func quickSort(arr []int)  {
	 arrLen := len(arr)
	 if arrLen <= 1 {
		 return
	 }

	 randNum := getRandNum(arrLen - 1)
	 arr[randNum], arr[0] = arr[0], arr[randNum]
	 mid := arr[0]

	 head, tail := 0, arrLen-1

	 for i := 1; i <= tail; {		 
		if arr[i] > mid {
			arr[i], arr[tail] = arr[tail], arr[i]
			tail--
		}else {
			arr[i], arr[head] = arr[head], arr[i]
			head++
			i++
		}
	 }
	 quickSort(arr[:head])
	 quickSort(arr[head+1:])
 }

 func getRandNum(totalNum int) int {
	rand.Seed(time.Now().Unix())// 设置随机种子
    return rand.Intn(totalNum)
 }

当然还有双轴快排,这里的思路就是在右两个指针,比较左右指针和基准数,小的放在左边

func QSortTwoWay(arr []int)  {
	arrLen := len(arr)
    if arrLen <= 1{
        return
    }

    randNum := getRandNum(arrLen -1)
    arr[randNum], arr[0] = arr[0],arr[randNum]
    mid := arr[0]//取出用于比较的元素

	head, tail := 0, arrLen - 1
	for {
        for head <= tail && arr[head] < mid{
            head ++
        }

        for tail > head && arr[tail] > mid{
            tail --
        }

        if head > tail{
            break
        }

        swap(arr, head, tail)
        head++
        tail--
    }

    QSortTwoWay(arr[:head])
    QSortTwoWay(arr[head+1:])

 }

归并排序

归并排序的方法就是两两切割,切割成两个数组,然后递归分块,直到不可再分割,然后两两排序,最后得到一个已经排好序的数组。

问世间情是何物,直教生死相许。
/*
 * @Author: yuzhouan
 * @Date: 2021-02-15 10:52:45
 * @LastEditTime: 2021-02-15 16:58:05
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: \Code\mergeSort.go
 */

package main

import "fmt"

func merge(arr []int) []int {
	if len(arr) < 2 {
		return arr
	}
	i := len(arr) / 2
	left := merge(arr[0:i])
	right := merge(arr[i:])
	result := mergeSort(left, right)
	return result
}

func mergeSort(left, right []int) []int {
	result := make([]int, 0)
	m, n := 0, 0
	l, r := len(left), len(right)
	for m < l && n < r {
		if left[m] > right[n] {
			result = append(result, right[n])
			n++
			continue
		}
		result = append(result, left[m])
		m++
	}
	if n < r {
		result = append(result, right[n:]...)
	}
	if m < l {
		result = append(result, left[m:]...)
	}
	return result
}

func main()  {
	arr := []int{1,4,6,2,5,7,6,9}
	result := merge(arr)
	fmt.Print(result)
}

GO strings包的用法

包含判断

  • 前后缀判断
func main() {
    //前后缀包含
    var str string = "This is a fat cat"
    var str1 string = "Hello Boss!"
    var str2 string = "Lucy is name My"
    fmt.Printf("T/F? Does the string \"%s\" have prefix %s?\n", str, "is") //str的前缀是否包含"is"?
    fmt.Printf("%t\n", strings.HasPrefix(str, "is"))                       //使用HasPrefix方法判断前缀
    fmt.Printf("T/F Does the string \"%s\" have prefix %s?\n", str1, "He")
    fmt.Printf("%t\n", strings.HasPrefix(str1, "He"))
    fmt.Printf("T/F Does the string \"%s\" have prefix %s?\n", str2, "My") //str2的后缀是否包含"y"
    fmt.Printf("%t\n,", strings.HasSuffix(str2, "My"))                     //使用HasSuffix方法判断后缀
}
  • 子字符串包含关系

除了可以检查前后缀,还可以使用Contains方法判断一个字符串的中间是否包含指定子字符串。

func main() {

    //使用ContainsAny方法查询字符串是否包含多个字符,
    fmt.Println(strings.ContainsAny("team", "e"))     //true
    fmt.Println(strings.ContainsAny("chain", ""))     //false
    fmt.Println(strings.ContainsAny("name", "n & m")) //true

    //使用Contains方法查找某个字符串是否存在这个字符串中,若存在,返回true
    fmt.Println(strings.Contains("team", "t & a")) //false
    fmt.Println(strings.Contains("chain", ""))     //true
    fmt.Println(strings.Contains("name", "n & m")) //false
}

与strings.Contains(str, chars)不同的是,strings.ContainsAny(str, chars)能够匹配更广泛的内容,它可以匹配Unicode字符串。

统计

  • 出现频率

在strings包中,可以借助strings.Count(str, manyO)统计字符串出现的频率。

func main() {
   
    str := "Golang is cool, right?"
    str1 := "科学建设钓鱼城特色的完满教育!"
    var manyG string = "o"
    
    //使用strings.Count()统计的字符串出现频率
    fmt.Printf("%d\n", strings.Count(str, manyG))
    fmt.Printf("%d\n", strings.Count(str, "oo"))
    fmt.Printf("%d\n", strings.Count(str1, "完满教育"))
}
/* 
3
1
1
*/

大小写转换

使用ToLower将字符串中的Unicode字符全部转换为相应的小写字符
使用ToUpper将字符串中的Unicode字符全部转换为相应的大写字符

func main() {

    str := "Hello World!\n"
    fmt.Printf("%s", str)
    fmt.Printf(strings.ToLower(str)) //使用ToLower将字符串全部转换成小写
    fmt.Printf(strings.ToUpper(str)) //使用ToUpper将字符串全部转换成大写
}
/*
Hello World!
hello world!
HELLO WORLD!
*/

修剪

使用strings.Trim()函数对字符串去掉一些不必要的内容,这一过程被称为修剪。

func main() {

    str := "完满 Hello Go 完满"
    str1 := "          请使用TrimSpace()修剪空白字符       "
    fmt.Println(str)
    fmt.Printf("%q\n", strings.Trim(str, "完满")) //修剪前缀和后缀
    fmt.Printf("%q\n", strings.Trim(str, "完满 "))

    fmt.Printf("%q\n", strings.TrimLeft(str, "完满 "))  //修剪左边前缀的字符
    fmt.Printf("%q\n", strings.TrimRight(str, " 完满")) //修剪右边后缀的字符
    fmt.Printf("%q\n", strings.TrimSpace(str1))       //修剪前缀和后缀的空白字符
}
/* 完满 Hello Go 完满
 " Hello Go "
 "Hello Go"
 "Hello Go 完满"
 "完满 Hello Go"
 "请使用TrimSpace()修剪空白字符"
*/

分割

使用分割函数strings.Split(),函数返回的是一个切片(slice)。切片的形式是用 [ ] 括起来,在后续的复合数据类型中将会进一步学习切片的使用。

func main() {
    str := "This is Golang Project"
    fmt.Println(str)
    fmt.Printf("%q\n", strings.Split(str, "Project")) //分割指定字符
    fmt.Printf("%q\n", strings.Split(str, " "))       //分割空白字符
}
/*
This is Golang Project
["This is Golang " ""]
["This" "is" "Golang" "Project"]
*/

插入字符

strings.Fields函数用于将字符串转换成slice(切片),strings.Join则将类型为string的切片使用分隔符组成拼接组成一个字符串。

func main() {
    str := "What's your name 完满主任"
    strFli := strings.Fields(str) //将原字符串转换成切片类型
    fmt.Println(str)
    fmt.Println(strFli)

    for _, val := range strFli { //range关键字的用法,需补充....
        fmt.Printf("%s", val)
    }
    fmt.Println()
    str2 := strings.Join(strFli, ";") //用分号拼接字符串
    fmt.Printf("%s\n", str2)
}
/*
What's your name 完满主任
[What's your name 完满主任]
What'syourname完满主任
What's;your;name;完满主任
*/

最长湍流子数组

当 A 的子数组 A[i], A[i+1], …, A[j] 满足下列条件时,我们称其为湍流子数组:

若 i <= k < j,当 k 为奇数时, A[k] > A[k+1],且当 k 为偶数时,A[k] < A[k+1]; 或 若 i <= k < j,当 k 为偶数时,A[k] > A[k+1] ,且当 k 为奇数时, A[k] < A[k+1]。
也就是说,如果比较符号在子数组中的每个相邻元素对之间翻转,则该子数组是湍流子数组。

返回 A 的最大湍流子数组的长度。

示例 1:

输入:[9,4,2,10,7,8,8,1,9]
输出:5
解释:(A[1] > A[2] < A[3] > A[4] < A[5])
示例 2:

输入:[4,8,12,16]
输出:2
示例 3:

输入:[100]
输出:1

题解:

最开始还真没有啥想法,以为是一个最大滑动窗口的问题,但是没有什么想法去做,后面发现一种简单的办法,交换变量,通过一大一小,不断的递增变量,就可以得到结果了。

func maxTurbulenceSize(arr []int) int {
    ans := 1
    up := 1
    down := 1
    for i:=1;i<len(arr);i++{
        if arr[i] > arr[i-1]{
            up = down + 1
            down = 1 
        }else if arr[i]<arr[i-1]{
            down = up + 1
            up = 1
        }else {
            down = 1
            up = 1
        }
        ans = max(ans,max(up,down))
    }
    return ans
}

func max(a, b int) int {
    if a>b {
        return a
    }
    return b
}

LRU / LFU

LRU是Least Recently Used的缩写,即最近最少使用,是一种常用的页面置换算法,选择最近最久未使用的页面予以淘汰。

根据 LRU 的策略,每次都淘汰最近最久未使用的页面,所以先淘汰 A 页面。再插入 C 的时候,发现缓存中有 C 页面,这个时候需要把 C 页面放到首位,因为它被使用了。以此类推,插入 G 页面,G 页面是新页面,不在缓存中,所以淘汰掉 B 页面。插入 H 页面,H 页面是新页面,不在缓存中,所以淘汰掉 D 页面。插入 E 的时候,发现缓存中有 E 页面,这个时候需要把 E 页面放到首位。插入 I 页面,I 页面是新页面,不在缓存中,所以淘汰掉 F 页面。

可以发现,「LRU 更新和插入新页面都发生在链表首,删除页面都发生在链表尾」

LRU 要求查询尽量高效,O(1) 内查询。那肯定选用 map 查询。修改,删除也要尽量 O(1) 完成。搜寻常见的数据结构,链表,栈,队列,树,图。树和图排除,栈和队列无法任意查询中间的元素,也排除。所以选用链表来实现。但是如果选用单链表,删除这个结点,需要 O(n) 遍历一遍找到前驱结点。所以选用双向链表,在删除的时候也能 O(1) 完成。

由于 Go 的 container 包中的 list 底层实现是双向链表,所以可以直接复用这个数据结构。定义 LRUCache 的数据结构如下:

import "container/list"

type LRUCache struct {
    Cap  int
    Keys map[int]*list.Element
    List *list.List
}

type pair struct {
    K, V int
}

func Constructor(capacity int) LRUCache {
    return LRUCache{
        Cap: capacity,
        Keys: make(map[int]*list.Element),
        List: list.New(),
    }
}

在 container/list 中,这个双向链表的每个结点的类型是 Element。Element 中存了 4 个值,前驱和后继结点,双向链表的头结点,value 值。这里的 value 是 interface 类型。笔者在这个 value 里面存了 pair 这个结构体。这就解释了 list 里面存的是什么数据。

为什么要存 pair 呢?单单指存 v 不行么,为什么还要存一份 key ?原因是在 LRUCache 执行删除操作的时候,需要维护 2 个数据结构,一个是 map,一个是双向链表。在双向链表中删除淘汰出去的 value,在 map 中删除淘汰出去 value 对应的 key。如果在双向链表的 value 中不存储 key,那么再删除 map 中的 key 的时候有点麻烦。如果硬要实现,需要先获取到双向链表这个结点 Element 的地址。然后遍历 map,在 map 中找到存有这个 Element 元素地址对应的 key,再删除。这样做时间复杂度是 O(n),做不到 O(1)。所以双向链表中的 Value 需要存储这个 pair。

LRUCache 的 Get 操作很简单,在 map 中直接读取双向链表的结点。如果 map 中存在,将它移动到双向链表的表头,并返回它的 value 值,如果 map 中不存在,返回 -1。

func (c *LRUCache) Get(key int) int {
 if el, ok := c.Keys[key]; ok {
  c.List.MoveToFront(el)
  return el.Value.(pair).V
 }
 return -1
}

LRUCache 的 Put 操作也不难。先查询 map 中是否存在 key,如果存在,更新它的 value,并且把该结点移到双向链表的表头。如果 map 中不存在,新建这个结点加入到双向链表和 map 中。最后别忘记还需要维护双向链表的 cap,如果超过 cap,需要淘汰最后一个结点,双向链表中删除这个结点,map 中删掉这个结点对应的 key。

func (c *LRUCache) Put(key int, value int) {
 if el, ok := c.Keys[key]; ok {
  el.Value = pair{K: key, V: value}
  c.List.MoveToFront(el)
 } else {
  el := c.List.PushFront(pair{K: key, V: value})
  c.Keys[key] = el
 }
 if c.List.Len() > c.Cap {
  el := c.List.Back()
  c.List.Remove(el)
  delete(c.Keys, el.Value.(pair).K)
 }
}

LFU 是 Least Frequently Used 的缩写,即最不经常最少使用,也是一种常用的页面置换算法,选择访问计数器最小的页面予以淘汰。如下图,缓存中每个页面带一个访问计数器。

根据 LFU 的策略,每访问一次都要更新访问计数器。当插入 B 的时候,发现缓存中有 B,所以增加访问计数器的计数,并把 B 移动到访问计数器从大到小排序的地方。再插入 D,同理先更新计数器,再移动到它排序以后的位置。当插入 F 的时候,缓存中不存在 F,所以淘汰计数器最小的页面的页面,所以淘汰 A 页面。此时 F 排在最下面,计数为 1。

这里有一个比 LRU 特别的地方。如果淘汰的页面访问次数有多个相同的访问次数,选择最靠尾部的。如上图中,A、B、C 三者的访问次数相同,都是 1 次。要插入 F,F 不在缓存中,此时要淘汰 A 页面。F 是新插入的页面,访问次数为 1,排在 C 的前面。也就是说相同的访问次数,按照新旧顺序排列,淘汰掉最旧的页面。这一点是和 LRU 最大的不同的地方。

可以发现,「LFU 更新和插入新页面可以发生在链表中任意位置,删除页面都发生在表尾」

LFU 同样要求查询尽量高效,O(1) 内查询。依旧选用 map 查询。修改和删除也需要 O(1) 完成,依旧选用双向链表,继续复用 container 包中的 list 数据结构。LFU 需要记录访问次数,所以每个结点除了存储 key,value,需要再多存储 frequency 访问次数。

还有 1 个问题需要考虑,一个是如何按频次排序?相同频次,按照先后顺序排序。如果你开始考虑排序算法的话,思考方向就偏离最佳答案了。排序至少 O(nlogn)。重新回看 LFU 的工作原理,会发现它只关心最小频次。其他频次之间的顺序并不关心。所以不需要排序。用一个 min 变量保存最小频次,淘汰时读取这个最小值能找到要删除的结点。相同频次按照先后顺序排列,这个需求还是用双向链表实现,双向链表插入的顺序体现了结点的先后顺序。相同频次对应一个双向链表,可能有多个相同频次,所以可能有多个双向链表。用一个 map 维护访问频次和双向链表的对应关系。删除最小频次时,通过 min 找到最小频次,然后再这个 map 中找到这个频次对应的双向链表,在双向链表中找到最旧的那个结点删除。这就解决了 LFU 删除操作。

LFU 的更新操作和 LRU 类似,也需要用一个 map 保存 key 和双向链表结点的映射关系。这个双向链表结点中存储的是 key-value-frequency 三个元素的元组。这样通过结点中的 key 和 frequency 可以反过来删除 map 中的 key。

定义 LFUCache 的数据结构如下:

import "container/list"

type LFUCache struct {
 nodes    map[int]*list.Element
 lists    map[int]*list.List
 capacity int
 min      int
}

type node struct {
 key       int
 value     int
 frequency int
}

func Constructor(capacity int) LFUCache {
 return LFUCache{nodes: make(map[int]*list.Element),
  lists:    make(map[int]*list.List),
  capacity: capacity,
  min:      0,
 }
}

LFUCache 的 Get 操作涉及更新 frequency 值和 2 个 map。在 nodes map 中通过 key 获取到结点信息。在 lists 删除结点当前 frequency 结点。删完以后 frequency ++。新的 frequency 如果在 lists 中存在,添加到双向链表表首,如果不存在,需要新建一个双向链表并把当前结点加到表首。再更新双向链表结点作为 value 的 map。最后更新 min 值,判断老的 frequency 对应的双向链表中是否已经为空,如果空了,min++。

func (this *LFUCache) Get(key int) int {
 value, ok := this.nodes[key]
 if !ok {
  return -1
 }
 currentNode := value.Value.(*node)
 this.lists[currentNode.frequency].Remove(value)
 currentNode.frequency++
 if _, ok := this.lists[currentNode.frequency]; !ok {
  this.lists[currentNode.frequency] = list.New()
 }
 newList := this.lists[currentNode.frequency]
 newNode := newList.PushFront(currentNode)
 this.nodes[key] = newNode
 if currentNode.frequency-1 == this.min && this.lists[currentNode.frequency-1].Len() == 0 {
  this.min++
 }
 return currentNode.value
}

LFU 的 Put 操作逻辑稍微多一点。先在 nodes map 中查询 key 是否存在,如果存在,获取这个结点,更新它的 value 值,然后手动调用一次 Get 操作,因为下面的更新逻辑和 Get 操作一致。如果 map 中不存在,接下来进行插入或者删除操作。判断 capacity 是否装满,如果装满,执行删除操作。在 min 对应的双向链表中删除表尾的结点,对应的也要删除 nodes map 中的键值。

由于新插入的页面访问次数一定为 1,所以 min 此时置为 1。新建结点,插入到 2 个 map 中。


func (this *LFUCache) Put(key int, value int) {
 if this.capacity == 0 {
  return
 }
 // 如果存在,更新访问次数
 if currentValue, ok := this.nodes[key]; ok {
  currentNode := currentValue.Value.(*node)
  currentNode.value = value
  this.Get(key)
  return
 }
 // 如果不存在且缓存满了,需要删除
 if this.capacity == len(this.nodes) {
  currentList := this.lists[this.min]
  backNode := currentList.Back()
  delete(this.nodes, backNode.Value.(*node).key)
  currentList.Remove(backNode)
 }
 // 新建结点,插入到 2 个 map 中
 this.min = 1
 currentNode := &node{
  key:       key,
  value:     value,
  frequency: 1,
 }
 if _, ok := this.lists[1]; !ok {
  this.lists[1] = list.New()
 }
 newList := this.lists[1]
 newNode := newList.PushFront(currentNode)
 this.nodes[key] = newNode
}

02-04 面试问题

1.channel什么时候会引发panic?

(1)通道一旦关闭,再对他进行发送操作,就会引发panic

(2)如果试图关闭一个已经关闭了的通道,也会引发panic

2.var a []int和a := []int{}是否有区别?

有区别, var a []int 是nil 切片,a := []int{}是空切片,它们的区别就是空切片是有一个特殊的内存地址,所有类型的「空切片」都共享这一个内存地址。

但是它们在使用的时候是没有区别的

3.函数返回局部变量的指针是否安全?

是的,在Go中这是绝对安全的。

支持栈的Go编译器将会对每个局部变量进行逃逸分析。 对于官方标准编译器来说,如果一个值可以在编译时刻被断定它在运行时刻仅会在一个协程中被使用,则此值将被开辟在(此协程的)栈上;否则此值将被开辟在堆上