补充题目 | 彩潭有鲤的札记

type

status

date

slug

summary

前缀和

和至少为 K 的最短子数组

题目：给一个整数数组nums和一个整数k ，找出nums中和至少为k的最短非空子数组 ，并返回该子数组的长度。如果不存在这样的子数组 ，返回-1 。

示例：

为了方便计算子数组的和，使用前缀和来计算。nums[i]到nums[j]的和就可以表示为prefix[j + 1] - prefix[i]。

那么，问题就转化为了针对某个prefix[i]，找到最近的prefix[k]使其差大于等于k。

可以用遍历一遍前缀和，在遍历时，查找之前的遍历过的前缀和中，是否有满足两者差大于等于k的，如果有就记录子数组的长度，最终取最小值。

和为 K 的子数组

题目：给一个整数数组nums和一个整数k ，请统计并返回该数组中和为k的连续子数组的个数

示例：

定义为里所有数的和，则可以由递推而来，即：那么这个子数组和为这个条件可以转化为：

简单移项可得符合条件的下标需要满足

考虑以结尾的和为的连续子数组个数时只要统计有多少个前缀和为的即可

建立哈希表，以和为键，出现次数为对应的值，记录出现的次数，从左往右边更新边计算答案，那么以结尾的答案即可在时间内得到。最后的答案即为所有下标结尾的和为的子数组个数之和。

设计数据结构

LRU 缓存

题目：

设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。实现 LRUCache 类：

LRUCache(int capacity)以正整数作为容量 capacity 初始化 LRU 缓存

int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 1 。

void put(int key, int value)如果关键字 key 已经存在，则变更其数据值value；如果不存在，则向缓存中插入该组key-value。如果插入操作导致关键字数量超过capacity，则应该逐出最久未使用的关键字。

函数get和put必须以O(1)的平均时间复杂度运行。

Cache的容量有限，因此当Cache的容量用完后，而又有新的内容需要添加进来时，就需要挑选并舍弃原有的部分内容，从而腾出空间来放新内容。LRU Cache 的替换原则就是将最近最少使用的内容替换掉。其实，LRU译成最久未使用会更形象，因为该算法每次替换掉的就是一段时间内最久没有使用过的内容。

LRU 缓存机制可以通过哈希表辅以双向链表实现，用一个哈希表和一个双向链表维护所有在缓存中的键值对。双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。

这样以来，首先使用哈希表进行定位，找出缓存项在双向链表中的位置，随后将其移动到双向链表的头部，即可在的时间内完成get或者put操作：

对于get操作，首先判断key是否存在：

如果key不存在，则返回−1
如果key存在，则key对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置，并将其移动到双向链表的头部，最后返回该节点的值。

对于put操作，首先判断key是否存在：

如果key不存在，使用key和value创建一个新的节点，在双向链表的头部添加该节点，并将key和该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量，如果超出容量，则删除双向链表的尾部节点，并删除哈希表中对应的项
如果key存在，则与get操作类似，先通过哈希表定位，再将对应的节点的值更新为value，并将该节点移到双向链表的头部

LRU 缓存

题目：

请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。实现 LFUCache 类：

LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象

int get(int key) - 如果键 key 存在于缓存中，则获取键的值，否则返回 1 。

void put(int key, int value) - 如果键 key 已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量 capacity 时，则应该在插入新项之前，移除最不经常使用的项。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最近最久未使用 的键。

为了确定最不常使用的键，可以为缓存中的每个键维护一个 使用计数器 。使用计数最小的键是最久未使用的键。

当一个键首次插入到缓存中时，它的使用计数器被设置为 1 (由于 put 操作)。对缓存中的键执行 get 或 put 操作，使用计数器的值将会递增。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

使用到「平衡二叉树」。在 C++ 语言中，可以直接使用std::set类作为平衡二叉树

首先定义缓存的数据结构：

其中 cnt 表示缓存使用的频率，time 表示缓存的使用时间，key 和 value 表示缓存的键值。

用哈希表key_table以键key为索引存储缓存，建立一个平衡二叉树S来保持缓存根据(cnt，time)双关键字由于。在C++中，可以使用STL提供的std::set 类，set背后的实现是红黑树：

对于get(key)操作，只要查看一下哈希表key_table是否有key这个键即可，有的话需要同时更新哈希表和集合中该缓存的使用频率以及使用时间，否则返回 -1。

对于put(key, value)操作，首先需要查看key_table中是否已有对应的键值。如果有的话操作基本等同于get(key)，不同的是需要更新缓存的value 值。如果没有的话相当于是新插入一个缓存，这时候需要先查看是否达到缓存容量capacity，如果达到了的话，需要删除最近最少使用的缓存，即平衡二叉树中最左边的结点，同时删除key_table中对应的索引，最后向key_table和S插入新的缓存信息即可。

数学

整数反转

题目：给一个32位的有符号整数x ，返回将x中的数字部分反转后的结果。如果反转后整数超过 32 位的有符号整数的范围，就返回0

假设环境不允许存储 64 位整数（有符号或无符号）。

示例：

回文数

题目：给一个整数x，如果x是一个回文整数，返回true ；否则，返回false 。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

例如，121 是回文，而 123 不是。

示例：

Excel表列名称

题目：给你一个整数columnNumber ，返回它在 Excel 表中相对应的列名称

示例：

用 Rand7() 实现 Rand10()

题目：给定方法 rand7 可生成 [1,7] 范围内的均匀随机整数，试写一个方法 rand10 生成 [1,10] 范围内的均匀随机整数。只能调用 rand7() 且不能调用其他方法。请不要使用系统的 Math.random() 方法。每个测试用例将有一个内部参数 n，即你实现的函数 rand10() 在测试时将被调用的次数。请注意，这不是传递给 rand10() 的参数。

示例：

定理：若rand_n()能等概率生成1到n的随机整数，则有(rand_n() - 1) * n + rand_n()能等概率生成1到n * n的随机整数。

解释： rand7()能等概率生成1~7，rand7() - 1能等概率生成0~6，(rand7() - 1) * 7能等概率生成{0, 7, 14, 21, 28, 35, 42}，(rand7() - 1) * 7 + rand7()能等概率生成1~49。