Contents

算法 - (数组、链表)

数组、链表是编程语言中最常见的数据结构,也是最基础的数据结构。以下会以几道 LeetCode 巩固自己的基础

结构对比

数组和链表各有各的优势,比如数组的随机插入和删除都是O(n)的,可谓是很低效了。但是数组的查找是是O(1),直接指定下标即可找到对应的元素。而链表必须遍历,也就是想要查找你一个元素的时间复杂度是 O(n)。所以数组和链表各有各的优势,互相补充。

数据结构    操作  时间复杂度
数组       prepend  O(1)    
           append     O(1) 
         lookup     O(1)
         insert     O(n)
         delete     O(n)
         –     
链表       prepend    O(1)   
           append     O(1) 
         lookup     O(n)
         insert     O(1)
         delete     O(1)

实现

数组

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
a := []int{1, 1, 2, 2, 2, 3, 4, 5, 5, 5, 6}

var b []int
b = append(c, 11)
b = append(b, a...)


// make( []Type, size, cap )
// 其中 Type 是指切片的元素类型,
// size 指的是为这个类型分配多少个元素,cap 为预分配的元素数量,
// 这个值设定后不影响 size,只是能提前分配空间,降低多次分配空间造成的性能问题。
c := make([]int, 2, 10)  

链表

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 定义单链表
type ListNode struct {     
	Val 	int
	Next 	*ListNode
}

func (ln *ListNode) add(v int) {
	if ln == nil {
		ln = &ListNode{Val: v,Next: nil}
	}
	for ln.Next != nil {
		ln = ln.Next
	}
	ln.Next = &ListNode{Val: v,Next: nil}
}

func (ln *ListNode) traverse() {
	for ln != nil {
		fmt.Printf("%d ",ln.Val)
		ln = ln.Next
	}
}

Leetcode

数组

No.1 两数之和

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
func twoSum(nums []int, target int) []int {
	tmp := make(map[int]int, len(nums)/2)
	for i := 0;i < len(nums);i++ {
		if index, ok := tmp[target-nums[i]]; ok {
			return []int{index,i}
		}
		tmp[nums[i]] = i
	}
	return []int{}
}

No.3 无重复字符的最长子串

 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
func lengthOfLongestSubstring(s string) int {
	if len(s) == 0 {
		return 0
	}

	checkFunc := func(sub string) bool {
		m := make(map[byte]struct{})
		for i := 0 ; i < len(sub); i++ {
			if _, ok := m[sub[i]]; ok {
				return false
			} else {
				m[sub[i]] = struct{}{}
			}
		}
		return true
	}

	maxLength := 1
	for i := 0; i < len(s); i++ {
		for j := i; j < len(s); j ++ {
			subStr := s[i:j+1]
			if checkFunc(subStr) {
				if len(subStr) > maxLength {
					maxLength = len(subStr)
				}
			}
		}
	}
	return maxLength
}

看了一下官方题解,原来是要搞个滑动窗口。

  1. 首先,不断移动右指针,当出现某个字符不为0时,证明子串里有重复了。
  2. 再移动左指针,看看是否还有重复。
  3. 直到计算出最大子串的值
 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
func lengthOfLongestSubstring(s string) int {
	right := 0 // 相当于字符串的最左边
	storeMap := make(map[byte]int)
	max := 0

	for left := 0; left < len(s); left ++ {
		if left != 0 {
			// 移动了左指针一次
			delete(storeMap, s[left - 1])
		}

		// 如果当前右指针不为0就退出循环
		for right  < len(s) && storeMap[s[right ]] == 0 {
			storeMap[s[right]] ++
			// 移动右指针
			right ++
		}

		if max < right - left {
			max = right - left
		}
	}

	return max
}

No.5 最长回文子串

回文有两种形式, “aba” 和 “aabb” 都是回文的模式。我们对长串的每一个字段都进行一次中心扩展。

 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
func longestPalindrome(s string) string {
	if s == "" {
		return ""
	}
	start, end := 0, 0
	for i := 0; i < len(s); i++ {
		// aba 模式
        left1, right1 := expandAroundCenter(s, i, i)
        // aabb 模式
		left2, right2 := expandAroundCenter(s, i, i + 1)
		if right1 - left1 > end - start {
			start, end = left1, right1
		}
		if right2 - left2 > end - start {
			start, end = left2, right2
		}
	}
	return s[start:end+1]
}

func expandAroundCenter(s string, left, right int) (int, int) {
	for ; left >= 0 && right < len(s) && s[left] == s[right]; left, right = left-1 , right+1 { }
    // 回到for循环最后一个满足条件的左右界限上
	return left + 1, right - 1
}

No.11 盛最多水的容器

  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
func maxArea(height []int) int {
	maxV := 0
	left, right := 0, len(height)-1
	
	for left < right {
		if height[left] > height[right] {
			maxV = max((right-left) * height[right], maxV)
			// 左边更高,右边左移
			right -- 
		} else {
			maxV = max((right-left) * height[left], maxV)
			// 右边更高,左边右移动
			left ++ 
		}
	}
	
	return maxV
}

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

No.15 三数之和

  • 链接:https://leetcode.cn/problems/3sum/
  • 思路:先将数组排序,再2层循环。如[-1,0,1,2,-1,-4 ] 先排序,排序之后 [-4, -1, -1, 0, 1, 2] 数组,再进行一次双重循环,第一次取 -4 ,再对 -4 之后的数组进行一次循环,-4 + 数组头元素 + 数组尾元素 > 0 就证明,数组尾元素过大, < 0 就证明数组头元素太小。逐渐的收拢第二个数组。
 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
func threeSum(nums []int) [][]int {
	sort.Ints(nums)

	var resMap map[[3]int]struct{}
	resMap = make(map[[3]int]struct{})

	for i := 0 ; i < len(nums) - 2; i ++ {
		a := nums[i]
		tmp := nums[i+1:]
		ltmp := len(tmp)
		for j := 0; j < ltmp -1; j++ {
			if a + tmp[j] + tmp[ltmp-1] > 0 {  // tmp[ltmp-1] 过大
 				ltmp--
 				j--
 				continue
			} else if a + tmp[j] + tmp[ltmp-1] < 0 { // tmp[j] 过小
				continue
			} else {
				resMap[[3]int{a, tmp[j], tmp[ltmp-1]}] = struct {}{}
			}
		}
	}
	var res [][]int
	for k,_ := range resMap {
		res = append(res, []int{k[0],k[1],k[2]})
	}

	return res
}

No.26 删除排序数组中的重复项

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func removeDuplicates(nums []int) int {
	j := 0
	for i := 0; i < len(nums) - 1; i ++ {
		if nums[i] != nums[i+1] {
			// 先j++的目的是为了防止数组全是重复项,所以从第二个数字开始改
			j++
			nums[j] = nums[i+1]
		}
	}
	return j+1
}
  • 思路2: 旋转数组法 旋转数组应该是我比较喜欢的一种方式,比较简单,那就是数组翻转2次,可以将首位数转到末尾曲,重复项判断刚好使用这种方式,对于移动数组类的题是比较通吃的一个方法问题就是时间复杂度比较大

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
func reversal(nums []int) {
	length := len(nums)
	for i := 0; length > 1 && i < length/2; i ++ {
		nums[i],nums[length-1-i] = nums[length-1-i],nums[i]
	}
}

func removeDuplicates(nums []int) int {
	length := len(nums)

	for i := 0; i < length; i ++ {
		if i + 1 < length && nums[i] == nums[i+1] {
			reversal(nums[i+1:length])
			reversal(nums[i+1:length-1])
			length = length - 1
			i = i - 1
		}
	}
	return length
}

No.29 顺时针打印矩阵

jianzhi_29_fig1

 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
func spiralOrder(matrix [][]int) []int {
	if len(matrix) == 0 || len(matrix[0]) == 0 {
		return []int{}
	}

	var (
		rows, columns = len(matrix), len(matrix[0])
		order = make([]int, rows * columns)
		index = 0
		left, right, top, bottom = 0, columns -1 , 0 , rows -1
	)

	for left <= right && top <= bottom {
		// 打印最上层(包含top行最后一个)
		for col := left; col <= right; col ++ {
			order[index] = matrix[top][col]
			index++
		}
		// 打印最右边(包含最右列最后一个)
		for row := top + 1; row <= bottom; row ++ {
			order[index] = matrix[row][right]
			index++
		}
		//
		if left < right && top < bottom {
			// 打印最下边(不包含bottom行最后一个和第一个)
			for col := right - 1; col > left; col -- {
				order[index] = matrix[bottom][col]
				index++
			}
			// 打印最左边(不包含left列最后一个)
			for row := bottom; row > top; row -- {
				order[index] = matrix[row][left]
				index++
			}
		}
	}
	left ++
	right --
	top ++
	bottom --

	return order
}

No.209 长度最小的子数组

 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
func minSubArrayLen(target int, nums []int) int {
	ri := 0  // 右指针
	minLength := math.MaxInt  

	if len(nums) == 0 {
		return 0
	}

	curSize := 0

	// 移动左指针
	for i := 0 ; i < len(nums); i ++ {
		if i != 0 { 
			curSize -= nums[i-1]
		}
		
		// 移动右指针。当前Size >= target就退出
		for ri < len(nums) && nums[ri] + curSize < target {
			curSize += nums[ri]
			ri ++
		}
        // 是我们想要的退出时机,而不是ri遍历完了
		if ri < len(nums) && curSize + nums[ri] >= target {
			if ri + 1 - i < minLength {
				minLength = ri + 1 -i
			}
		}
	}
	if minLength == math.MaxInt {
		return 0
	}

	return minLength
}

No.459 重复的子字符串

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
func repeatedSubstringPattern(s string) bool {
	length := len(s)
	for i := 1; i * 2 <= length; i++ {  // i为子串长度
		if length % i == 0 {    // 总长度 % 子串长度 必须为0
			var flag bool = true
			for j := i ; j < length ; j ++ {  // 循环一遍,不能为false
				if s[j] != s[j-i] {  // 子串在父串中可循环
					flag = false
					break
				}
			}
			if flag { return flag }
		}
	}
	return false
}


674. 最长连续递增序列

 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 findLengthOfLCIS(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	prev := nums[0]
	maxLength := 0

	for i := 0; i < len(nums); i++ {
		curMax := 1
		for j := i + 1; j < len(nums); j ++ {
			if nums[j] > prev {
				curMax ++
				prev = nums[j]
			} else {
				i = j -1 
				break
			}
		}
		if curMax > maxLength {
			maxLength = curMax
		}
	}
	return maxLength
}

链表


No.21 合并两个链表

 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
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	tmp := &ListNode{}

	prev := tmp
	for l1 != nil && l2 != nil {
		if l1.Val < l2.Val{
			prev.Next = l1
			prev = prev.Next

			l1 = l1.Next
		}else {
			prev.Next = l2
			prev = prev.Next

			l2 = l2.Next
		}
	}

	if l2 != nil {
		prev.Next = l2
	}

	if l1 != nil {
		prev.Next = l1
	}

	return tmp.Next
}

No.22 链表的倒数第k个节点

 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
// 非常low的写法
func getKthFromEnd(head *ListNode, k int) *ListNode {
	var rest []*ListNode
	for node := head; node != nil; node = node.Next {
		rest = append(rest, node)
	}
	if len(rest) >= k {
		return rest[len(rest) - k]
	}
	return nil
}

// 快慢指针
func getKthFromEnd(head *ListNode, k int) *ListNode {
	fast, slow := head, head 
	for fast != nil && k > 0 {
		fast = fast.Next
		k--
	}
	for fast != nil {
		fast = fast.Next
		slow = slow.Next
	}
	return slow 
}

No.25 K个一组翻转链表

 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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
func reverseKGroup(head *ListNode, k int) *ListNode {
	if head == nil {
		return nil
	}

	var ok bool = true
	var sub *ListNode
	var root *ListNode = &ListNode{}
	var tmp *ListNode = root

	for ok {
		sub, ok = helper(head, k)
		tmp.Next = sub
		head = sub
		if ok {
			tmpK := k
			for tmpK > 0 {
				tmp = tmp.Next
				head = head.Next
				tmpK --
			}
		}
	}

	return root.Next
}

func helper(head *ListNode, k int) (*ListNode, bool) {
	if head == nil {
		return nil, false
	}
	root := head
	length := 0
	for head != nil {
		head = head.Next
		length++
	}

	if k > length {
		return root, false
	}

	head = root
	var prev *ListNode = nil
	cur := prev

	for head != nil && k > 0 {
		next := head.Next

		head.Next = prev
		cur = head
		prev = cur

		head = next
		k--
	}
	next := head
	ret := cur

	for cur.Next != nil {
		cur = cur.Next
	}
	cur.Next = next

	return ret, true
}


No.83 删除排序链表重复项

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
func deleteDuplicates(head *ListNode) *ListNode {
	if head == nil {
		return head
	}

	cur := &ListNode{} 
	tmp := cur   // 记录链表头
	for head != nil {
		for head.Next != nil && head.Val == head.Next.Val {
			 head = head.Next
		}
		cur.Next = head
		cur = cur.Next
		head = head.Next
	}
	return tmp.Next
}

No.92 翻转局部链表

 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
50
51
52
53
54
55
func reverseBetween(head *ListNode, left int, right int) *ListNode {
    if head == nil {
		return nil
	}
	length := right - left
	tmp := &ListNode{}
	tmp.Next = head
	cur := tmp

    // 将指针移动到翻转的前半部分
	for head != nil && left - 1 > 0 {
		next := head.Next

		cur.Next = head
		cur = cur.Next

		head = next
		left --
	}
    
	next := head
	cur.Next = reverseList(next, length+1)

	return tmp.Next
}

// 生成翻转和翻转的后半部分 
func reverseList(head *ListNode, length int) *ListNode {
if head == nil || length <= 0 {
		return head
	}

	var prev *ListNode = nil
	var cur *ListNode = prev

	for head != nil && length > 0 {
		next := head.Next

		head.Next = prev
		cur = head
		prev = cur

		length --
		head = next
	}
	next := head

	tmp := cur
	for tmp.Next != nil {
		tmp = tmp.Next
	}
	tmp.Next = next

	return cur
}

No.141 环形链表

  • 链接: https://leetcode-cn.com/problems/linked-list-cycle/
  • 思路1:这道题思路非常简单,就是快慢指针,慢指针每次前进一步,快指针每次前进两步。如果存在环快指针一定会追上慢指针,问题就是边界条件太多,需要仔细判断。
  • 思路2:hash表存已有的数据做对比,这个最简单,不演示啦~
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
func hasCycle(head *ListNode) bool {
    if head == nil {
		return false
	}
	slow := head
	fast := head.Next
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if slow == fast {
			return true
		}
	}

	return false
}

No.148 排序链表

  • 链接:https://leetcode.cn/problems/sort-list/
  • 思路:这道题采用归并排序的方法,将链表拆成足够小的部分,然后排序,就相当于是有序链表的合并,而拆到足够细时,因为链表就一个值,所以当然是有序的
 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
50
51
52
53
54
55
56
57
58
59
func sortList(head *ListNode) *ListNode {
	return sort(head, nil)
}

func sort(head *ListNode, tail *ListNode) *ListNode {
	if head == nil {
		return nil
	}

    // 拆到足够细了,就是链表的一个节点
	if head.Next == tail {
		head.Next = nil
		return head
	}

	fast := head
	slow := head

	for fast.Next != tail {
		fast = fast.Next
		slow = slow.Next
		if fast.Next != tail {
			fast = fast.Next
		}
	}
	return merge(sort(head, slow), sort(slow, tail))
}

// 有序链表的合并
func merge(p, q *ListNode) *ListNode {
	if p == nil {
		return q
	}
	if q == nil {
		return p
	}

	tmp := &ListNode{}
	cur := tmp
	for p != nil && q != nil {
		if p.Val > q.Val {
			cur.Next = &ListNode{Val: q.Val, Next: nil}
            q = q.Next
		} else {
			cur.Next = &ListNode{Val: p.Val, Next: nil}
			p = p.Next
		}
		cur = cur.Next
	}

	if p != nil {
		cur.Next = p
	} else {
		cur.Next = q
	}

	return tmp.Next
}


No.160 相交链表

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func getIntersectionNode(headA, headB *ListNode) *ListNode {
	tmp := make(map[*ListNode]struct{})
	for headA != nil {
		tmp[headA] = struct{}{}
		headA = headA.Next
	}
	for headB != nil {
		if _, ok := tmp[headB]; ok {
			return headB
		}
		headB = headB.Next
	}
	return nil 
}

No.203 移除链表元素

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
func removeElements(head *ListNode, val int) *ListNode {
	if head == nil {
		return nil 
	}
	
	tmp := &ListNode{}
	prev := tmp
	
	for head != nil {
		for head != nil && head.Val == val {
			head = head.Next
		}
		prev.Next = head
		prev = prev.Next
		if head != nil {
			head = head.Next
		}
	}
	
	return tmp.Next
}

No.206 反转链表

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
func reverseList(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}

	var prev *ListNode = nil
	cur := prev

	for head != nil {
		next := head.Next  // 存下一个

		head.Next = prev // haed 的Next指向 prev
		cur = head       // cur 就是 head
		prev = cur		 // cur 成为 prev

		head = next   // head 前进
	}

	return cur
}

No.234 回文链表

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func isPalindrome(head *ListNode) bool {
var vals []int
	for ; head != nil; head = head.Next {
		vals = append(vals, head.Val)
	}
	n := len(vals)
	for i, v := range vals[:n/2] {
		if v != vals[n-1-i] {
			return false
		}
	}
	return true
}

实现一个 LRU 缓存

  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
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
package lru

import (
	"container/list"
	"errors"
)

const (
	MemoryOverFlow				int = 0
	MemorySizeError				int = 1
	NotFoundObject				int = 11
)


var lruErrorName = map[int]string{
	MemoryOverFlow:      "MemoryOverFlow",
	MemorySizeError: 	 "MemorySizeError",
	NotFoundObject: 	 "NotFoundObject",
}


// 记录存储数据的大小
type Value interface {
	Len() int64
}

// 存储的对象
type entry struct {
	key 	string
	value 	Value
}

type Cache struct {
	maxBytes int64        // 最大使用内存
	nBytes 	 int64        // 当前已使用内存
	ll *list.List         // 链表存储淘汰关系
	cache  map[string]*list.Element   //节点放到字典中,加速查找
	OnEvicted  func(key string, value Value)   //某条记录被删除时候的回调函数
}

func CreateLRUCache(maxByte int64,evicted func(string,Value)) *Cache {
	return &Cache{
		maxBytes:  maxByte,
		nBytes:    0,
		ll:        new(list.List),
		cache:     make(map[string]*list.Element),
		OnEvicted: evicted,
	}
}


func (c *Cache) Get(key string) (value Value,err error) {
	if ele, ok := c.cache[key]; ok {
		c.ll.MoveToFront(ele)
		return ele.Value.(*entry).value, nil
	}else {
		return nil, errors.New(lruErrorName[NotFoundObject])
	}
}

func (c *Cache) Add(key string, value Value) error {
	// 判断是否可以加入(太大会把所有缓存冲掉)
	if c.isOutOfMaxMemory(value.Len()) {
		return errors.New(lruErrorName[MemoryOverFlow])   // 内存不足以添加该缓存
	}

	// 判断缓存中已有该键, 更新
	if v, ok := c.cache[key]; ok {
		oldValue := v.Value.(*entry)
		// 可以加入,将该键移动到队头
		c.ll.MoveToFront(v)
		c.cache[oldValue.key] = &list.Element{Value: &entry{key,value}}
		c.nBytes = c.nBytes - oldValue.value.Len() + value.Len()
		return nil
	}
	// 没有该键,第一次添加
	ele := c.ll.PushFront(&entry{key, value})
	c.cache[key] = ele
	c.nBytes = c.nBytes + value.Len()

	// 若内存不够,需要循环删除掉最老的
	for c.maxBytes != 0 && c.maxBytes < c.nBytes {
		if err := c.RemoveOldest(); err != nil {
			return err
		}
	}

	return nil
}

func (c *Cache) RemoveOldest() error {
	oldest := c.ll.Back()
	if oldest != nil {
		oldestEntry := oldest.Value.(*entry)
		c.ll.Remove(oldest) // 删除链表节点
		c.nBytes = c.nBytes - oldestEntry.value.Len() // 删除字节长度
		delete(c.cache, oldestEntry.key)  // 删除字典
		if c.nBytes < 0 {
			return errors.New(lruErrorName[MemorySizeError])
		}
		if c.OnEvicted != nil {
			c.OnEvicted(oldestEntry.key, oldestEntry.value)
		}
	}
	return nil
}

func (c *Cache) Len() int64 {
	return int64(c.ll.Len())
}

func (c *Cache) isOutOfMaxMemory(size int64) bool {
	return size > c.maxBytes

测试

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
type GeeByte struct {
	Value []byte
}

func (g GeeByte) Len() int64 {
	return int64(len(g.Value))
}


func TestLruCache(t *testing.T) {
	lruObject := lru.CreateLRUCache(20, func(key string, value lru.Value) {
		fmt.Printf("%s 被删除了, 释放了 %d 字节的空间\n", key, value.Len())
	})

	_ = lruObject.Add("key1", GeeByte{[]byte("Hello, Golang")})
	_ = lruObject.Add("key2", GeeByte{[]byte("Hello, ByteDance")})

	if value, err := lruObject.Get("key2"); err != nil {
		log.Fatalln(err)
	}else {
		fmt.Printf("%s",value)
	}
}