0%

题目描述

原题链接: 146. LRU缓存机制

运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put

  • 获取数据 get(key)
    • 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1。
  • 写入数据 put(key, value)
    • 如果密钥不存在,则写入其数据值。当缓存容量达到上限时,它应该在写入新数据之前删除最近最少使用的数据值,从而为新的数据值留出空间。
阅读全文 »

ziplist(压缩列表) 和 listNode(双端链表) 共同组成了列表的底层结构 quicklist,同时也是 哈希、有序集合 在数据量较小时的底层实现, 可以看做是一个特殊的数组, 数组中的每一项的长度不固定

ziplist在内存中是一整块的连续内存, 所有节点在内存中是紧挨着的,因此不需要和双端链表一样保存前进指针和后退指针。

阅读全文 »

跳表(skiplist)是一种基于有序链表的用于方便快速查找/插入/删除的数据结构, 查询效率(平均O(logN), 最差O(N)) 堪比红黑树, 然而实现与维护却要比红黑树要简单的多。 跳表的每个节点都维护了多个指向其他节点的指针,所以在查找、插入、删除操作时可以跳过一些节点,快速找到操作需要的节点。

阅读全文 »

字典是一种用于保存键值对(key-value pair)的抽象数据结构, 在字典中, 一个键(key)可以可一个值关联(或者说将键映射为值), 这些关联的键和值就成为键值对。

字典中的每个键都是独一无二的, 程序可以在字典中做到根据键查找与之关联的值,或者通过键更新/删除值等

Redis用到字典的地方主要有:

  • 实现数据库键空间(key space),维护 key 和 value 映射关系的数据结构
  • 用作 Hash 类型键的底层实现之一(另一种是ziplist)
  • 使用dict和skiplist来共同维护一个sorted_set
阅读全文 »

Redis没有直接使用C语言传统的字符串表示, 而是自己撸了一种名为简单动态字符串(Simple Dynamic String, SDS)的抽象类型作为 Redis 的默认字符串表示。

阅读全文 »

原题链接: Leetcode 10. 正则表达式匹配

题目描述

给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素

所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。

说明:

s 可能为空,且只包含从 a-z 的小写字母。
p 可能为空,且只包含从 a-z 的小写字母,以及字符 .*

阅读全文 »

AcWing 902. 最短编辑距离

题目描述

给定两个字符串A和B,现在要将A经过若干操作变为B,可进行的操作有:
删除–将字符串A中的某个字符删除。
插入–在字符串A的某个位置插入某个字符。
替换–将字符串A中的某个字符替换为另一个字符。
现在请你求出,将A变为B至少需要进行多少次操作。

阅读全文 »