题目描述 一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。 示例 1： 输入：n = 2 输出：2 示例 2： 输入：n = 7 输出：21 示例 3： 输入：n = 0 输出：1 提示： 0 <= n <= 100 解题思路 这道题是一道很经典的动态规划的题。 基本思路就是用动态数组中的元素dp[i]表示跳到i级台阶共有多少种跳法。那么我们可以很容易…

字典也被称为映射(map)，经常作为一种数据结构内置在很多高级编程语言里面。但是Redis所使用的C语言并没有内置这种数据结构，因此Redis构建了自己的字典实现。 字典在Redis中的应用相当广泛，比如Redis的数据库就是使用字典来作为底层实现的，对数据库的增删改查也是构建在对字典的操作之上的。字典还是哈希键的底层实现之一。当一个哈希键包含的键值对比较多，又或者键值对中的元素都是比较长的字符串时，Redis就会使用字典作为哈希键的底层实现。 字典的实现 Redis 的字典使用哈希表作为底层实现， 一个哈希表里面…

整数集合（Intset）是集合键的底层实现之一： 当一个集合只包含整数值元素， 并且这个集合的元素数量不多时， Redis 就会使用整数集合作为集合键的底层实现。 整数集合的实现 整数集合（intset）是 Redis 用于保存整数值的集合抽象数据结构， 它可以保存类型为 int16_t 、 int32_t 或者 int64_t 的整数值， 并且保证集合中不会出现重复元素。 每个 intset.h/intset 结构表示一个整数集合： typedef struct intset { // 编码方式 uint32_t…

压缩列表（ziplist）是列表键和哈希键的底层实现之一。 当一个列表键只包含少量列表项， 并且每个列表项要么就是小整数值， 要么就是长度比较短的字符串， 那么 Redis 就会使用压缩列表来做列表键的底层实现。 另外， 当一个哈希键只包含少量键值对， 并且每个键值对的键和值要么就是小整数值， 要么就是长度比较短的字符串， 那么 Redis 就会使用压缩列表来做哈希键的底层实现。 压缩列表的实现 压缩列表是 Redis 为了节约内存而开发的， 由一系列特殊编码的连续内存块组成的顺序型（sequential）数据结构…

跳跃表是基于链表实现的有序列表，将查询的时间复杂度优化到了$O(logn)$。 Redis使用跳跃表作为有序集合键的底层实现之一。如果一个有序集合包含的元素数量比较多，又或者有序集合中元素的成员是比较长的字符串时，Redis就会使用跳跃表来作为有序集合键的底层实现。 实际上，Redis只在两个地方用到了跳跃表，一个是实现有序集合键，另一个是在集群节点中用作内部数据结构。 跳跃表的实现 Redis 的跳跃表由 redis.h/zskiplistNode 和 redis.h/zskiplist 两个结构定义， 其中 z…

InnoDB存储引擎有多个内存块，可以认为这些内存块组成了一个大的内存池，负责如下工作： 维护所有进程/线程需要访问的多个内部数据结构 缓存磁盘上的数据，方便快速读取，同时在对磁盘文件的数据修改之前在这里缓存 重做日志(redo log)缓冲 而后台线程的主要作用是负责刷新内存池中的数据，保证缓冲池中的内存缓存的是最新的数据。此外将已经修改的数据文件刷新到磁盘文件。同时还要保证在数据库发生异常的情况下InnoDB能恢复到正常运行状态。 InnoDB的简单的体系结构图如下所示： 后台线程 InnoDB存储引擎是多线程…

构成MySQL数据库和InnoDB存储引擎表的各种类型的文件可以分为以下类型： 参数文件：告诉MySQL实例启动的时候在哪里可以找到数据库文件，并且指定某些初始化参数，这些参数定义了某种内存结构的大小等设置； 日志文件：用来记录MySQL实例对某种条件做出响应时写入的文件，如错误日志，二进制日志文件，慢查询日志文件，查询日志文件等； socket文件：当用UNIX域套接字方式进行连接时需要的文件； pid文件：MySQL实例的进程ID文件； MySQL表结构文件：用来存放MySQL表结构定义文件； 存储引擎文件：因…

开发多用户，数据库驱动的应用时，最大的一个难点是：一方面要最大程度的利用数据库的并发访问，另一方面还要确保每个用户能以一致的方式读取和修改数据，为此就有了锁机制。同时这也是数据库系统区别于文件系统的一个关键特性。锁机制用于管理对共享资源的并发访问，InnoDB存储引擎会在行级别上对表数据上锁。 myisam引擎不支持行锁，只支持表锁，并发情况下的读没有问题，但是并发插入时的性能就要差一些了。 InnoDB存储引擎的实现和Oracle数据库非常类似，提供一致性的非锁定读、行级锁支持。行级锁没有相关额外的开销，并可以同…

题目描述 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。 示例 1： 输入：target = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。 示例 2： 输入：target = 4, nums = [1,4,4] 输出：1 示例 3： …

题目描述 给定一个经过编码的字符串，返回它解码后的字符串。 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。 示例 1： 输入：s = "3[a]2[bc]" 输出："aaabcbc…