今天的每日一題是跳表，如果按一般的方法用 Scala 重新實(shí)現(xiàn)一遍就有點(diǎn)無(wú)聊，給自己找了點(diǎn)樂(lè)子——用 Stream 取代掉所有的 while 循環(huán)。

純屬娛樂(lè)，不過(guò)通過(guò)這樣寫，倒是略微感覺(jué)到了惰性和函數(shù)式編程的強(qiáng)相關(guān)性。以及普適性的結(jié)論：像 Haskell 語(yǔ)言里面沒(méi)有 while 循環(huán)，就也可以通過(guò)它的 iterate 函數(shù)和 scanl 函數(shù)按照類似邏輯來(lái)執(zhí)行循環(huán)邏輯？

把最后寫出來(lái)的代碼貼出來(lái)，感興趣的話可以參考。感覺(jué)函數(shù)式編程還是很多東西要多學(xué)多練啊……（順便提一句，前段時(shí)間發(fā)現(xiàn)洛谷和 Codeforce 上居然支持 Haskell 刷題，力扣目前不支持。有空可以去玩玩）

1 題目

不使用任何庫(kù)函數(shù)，設(shè)計(jì)一個(gè) 跳表 。

跳表 是在 O(log(n)) 時(shí)間內(nèi)完成增加、刪除、搜索操作的數(shù)據(jù)結(jié)構(gòu)。跳表相比于樹堆與紅黑樹，其功能與性能相當(dāng)，并且跳表的代碼長(zhǎng)度相較下更短，其設(shè)計(jì)思想與鏈表相似。

跳表中有很多層，每一層是一個(gè)短的鏈表。在第一層的作用下，增加、刪除和搜索操作的時(shí)間復(fù)雜度不超過(guò) O(n)。跳表的每一個(gè)操作的平均時(shí)間復(fù)雜度是 O(log(n))，空間復(fù)雜度是 O(n)。

在本題中，你的設(shè)計(jì)應(yīng)該要包含這些函數(shù)：

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

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

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

注意，跳表中可能存在多個(gè)相同的值，你的代碼需要處理這種情況。

示例 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

• 調(diào)用search, add, ?erase操作次數(shù)不大于 5 * 10^4

來(lái)源：力扣（LeetCode）

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

著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2 題解

用普通的類似 Java 的寫法感覺(jué)有點(diǎn)無(wú)聊，對(duì)著題解或者 CurrentSkipListMap 源碼（需要自己去掉一下同步相關(guān)邏輯）的思路抄就完事了。干脆練習(xí)了一下 Scala 的 Stream 怎么寫這個(gè)數(shù)據(jù)結(jié)構(gòu)。

跳表層數(shù)使用節(jié)點(diǎn) 1/5 概率向上生長(zhǎng)的設(shè)計(jì)，簡(jiǎn)化實(shí)現(xiàn)。其中概率可以通過(guò)修改 avgJump 變量來(lái)控制。當(dāng)刪除節(jié)點(diǎn)時(shí)，不會(huì)減小層數(shù)，防止抖動(dòng)。

自己之前一直用的 Scala 2.11，排查問(wèn)題過(guò)程中，發(fā)現(xiàn) 2.13 推薦使用 LazyList 代替 Stream。兩者差別是，LazyList 全部都是惰性的，但是 Stream 的 head 不是惰性的。