今天的每日一题是跳表，如果按一般的方法用 Scala 重新实现一遍就有点无聊，给自己找了点乐子——用 Stream 取代掉所有的 while 循环。

纯属娱乐，不过通过这样写，倒是略微感觉到了惰性和函数式编程的强相关性。以及普适性的结论：像 Haskell 语言里面没有 while 循环，就也可以通过它的 iterate 函数和 scanl 函数按照类似逻辑来执行循环逻辑？

把最后写出来的代码贴出来，感兴趣的话可以参考。感觉函数式编程还是很多东西要多学多练啊……（顺便提一句，前段时间发现洛谷和 Codeforce 上居然支持 Haskell 刷题，力扣目前不支持。有空可以去玩玩）

1 题目

不使用任何库函数，设计一个 跳表 。

跳表 是在 O(log(n)) 时间内完成增加、删除、搜索操作的数据结构。跳表相比于树堆与红黑树，其功能与性能相当，并且跳表的代码长度相较下更短，其设计思想与链表相似。

跳表中有很多层，每一层是一个短的链表。在第一层的作用下，增加、删除和搜索操作的时间复杂度不超过 O(n)。跳表的每一个操作的平均时间复杂度是 O(log(n))，空间复杂度是 O(n)。

在本题中，你的设计应该要包含这些函数：

• bool search(int target) : 返回target是否存在于跳表中。

• void add(int num): 插入一个元素到跳表。

• bool erase(int num): 在跳表中删除一个值，如果 num 不存在，直接返回false. 如果存在多个 num ，删除其中任意一个即可。

注意，跳表中可能存在多个相同的值，你的代码需要处理这种情况。

示例 1:

输入
["Skiplist", "add", "add", "add", "search", "add", "search", "erase", "erase", "search"]
[[], [1], [2], [3], [0], [4], [1], [0], [1], [1]]
输出
[null, null, null, null, false, null, true, false, true, false]

解释
Skiplist skiplist = new Skiplist();
skiplist.add(1);
skiplist.add(2);
skiplist.add(3);
skiplist.search(0);   // 返回 false
skiplist.add(4);
skiplist.search(1);   // 返回 true
skiplist.erase(0);    // 返回 false，0 不在跳表中
skiplist.erase(1);    // 返回 true
skiplist.search(1);   // 返回 false，1 已被擦除


提示:

• 0 <= num, target <= 2 * 10^4

• 调用search, add,  erase操作次数不大于 5 * 10^4

来源：力扣（LeetCode）

链接：https://leetcode.cn/problems/design-skiplist

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2 题解

用普通的类似 Java 的写法感觉有点无聊，对着题解或者 CurrentSkipListMap 源码（需要自己去掉一下同步相关逻辑）的思路抄就完事了。干脆练习了一下 Scala 的 Stream 怎么写这个数据结构。

跳表层数使用节点 1/5 概率向上生长的设计，简化实现。其中概率可以通过修改 avgJump 变量来控制。当删除节点时，不会减小层数，防止抖动。

自己之前一直用的 Scala 2.11，排查问题过程中，发现 2.13 推荐使用 LazyList 代替 Stream。两者差别是，LazyList 全部都是惰性的，但是 Stream 的 head 不是惰性的。