记录一次很慌的核酸检测经历

## 前言

收到电话通知了，没有事情，检测是阴性，烧也退下去了。

## 起因

20号早晨莫名其妙发烧了，本来以为没事情的，结果吃了退烧药啥的都不管用，一直到了第二天还在发烧，有点慌了，就去医院做了一下核酸检测。

![image-20200822012126040](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/20200822012133.png)

## 过程

总结一下 **核酸检测** 的基本步骤吧:

1. 填表
2. 医生采样
3. 完毕

看上去就这么简单吧, 但是这个采样又是什么样子的呢?

这里其实有两种方案, 第一种就是下面这种,先来看看描述:

> 采样人员一手轻扶被采集人员的头部，一手执拭子，拭子贴鼻孔进入，沿下鼻道的底部向后缓缓深入，由于鼻道呈弧形，不可用力过猛，以免发生外伤出血。**待拭子顶端到达鼻咽腔后壁时，轻轻旋转一周**（如遇反射性咳嗽，应停留片刻） ，然后缓缓取出拭子，将拭子头浸入含2～3ml病毒保存液（也可使用等渗盐溶液、组织培养液或磷酸盐缓冲液）的管中，尾部弃去，旋紧管盖。

听上去是不是云里雾里的? 然而相信我, 直接看到图片之后直接会 **心 肺 停 止** 的, 你看这难道不是处刑吗?

![img](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/20200822085940.jpeg)

![img](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/20200822085949.jpeg)

![img](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/20200822085955.jpeg)

啊哈, 不过好在这里还有第二个方案, 也是更加普及的方案:

> 被采集人员先用生理盐水漱口，采样人员将拭子放入无菌生理盐水中湿润(禁止将拭子放入病毒保存液中，避免抗生素引起过敏)，被采集人员头部微仰，嘴张大，并发“啊”音，**露出两侧咽扁桃体，将拭子越过舌根，在被采集者两侧咽扁桃体稍微用力来回擦拭至少3次，然后再在咽后壁上下擦拭至少3次**，将拭子头浸入含2～3ml病毒保存液（也可使用等渗盐溶液、组织培养液或磷酸盐缓冲液）的管中，尾部弃去，旋紧管盖。咽拭子也可与鼻咽拭子放置于同一管中。

"看上去"是不是更加"温柔"了?啧啧啧, 请看下面这个图:

![img](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/20200822090002.jpeg)

没错! 这个就是直接往你喉咙里捅.......直接捅到嗓子眼的那种......

”什么？你以为是二选一？“哦不，是两个都要做！感觉呢，感觉就是非常酸爽，就像是吃了一斤的芥末混合着催吐剂一样，整个人都不好了。。。

![img](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/20200822090008.jpeg)

## 后续

也不知道怎么作下了，一直发烧到了22号才有所好转，体温恢复了正常，但是头痛难忍+胳膊莫名其妙的极其酸痛使得我现在无法入睡，只得起床写下此篇小记，用以记录和转移注意力缓解疼痛感。。。。

最后附上检查结果：![image-20200823013551713](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/20200823013557.png)

不过医生的字真的是草的不得了。。。。但起码还能看懂点。。。。

![image-20200823013649688](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/20200823013656.png)

记一次核酸检测经历

二分搜索和一些用到二分思想的题目

## 前言

二分搜索可以说是应用非常广泛的一类算法了，非常多的暴力算法优化方案都是在一些条件下用二分，并且二分效率很高，可以让$\mathcal{O}(N)$算法秒变$\mathcal{O}(log_2N)$，效率大大提高~~(超时就先往二分上靠再说)~~，故本篇文章就讨论一下二分算法和一些关于二分的题目。



## 二分搜索

最基础的版本，用于在一个有序序列中查找需要的元素：

```kotlin
/**
 * 在一个列表中二分查找到某个值
 * @author xmmmmmovo
 * @date 2020/7/28 11:46
 * @param list 列表
 * @param key 需要查找的值
 * @param lo 左范围 默认为0
 * @param hi 右范围 默认为list.size - 1
 * @return 查找到了就返回下标，没查找到就返回-1
 * @since version-1.0
 */
fun <T : Comparable<T>> binarySearch(
    list: List<T>, key: T, _lo: Int = 0, _hi: Int = list.size - 1
): Int {

    var lo = _lo
    var hi = _hi

    while (lo <= hi) {
        val mid = lo + (hi - lo) / 2
        when {
            key < list[mid] -> {
                hi = mid - 1
            }
            key > list[mid] -> {
                lo = mid + 1
            }
            else -> {
                return mid
            }
        }
    }

    return -1
}
```

因为每一次都会是比上一次缩减**1/2**的搜查量，$\cfrac{N}{2^k} = 1$，所以时间复杂度为
$$
\mathcal{O}(\log_2N)
$$
空间复杂度为
$$
\mathcal{O}(1)
$$

## 查找列表中是否存在某元素

查找列表中是否存在某元素，这个问题，其实用`遍历`或者`二分`都可以解，并且不会特别影响时间复杂度，因为排序算法时间复杂度$\mathcal{O}(Nlog_2N)$已经决定了这个算法的时间复杂度，但是利用二分搜索更能提升算法效率，说不准就卡那么几毫秒。

```kotlin
/**
 * 查找列表中是否存在某元素，利用[binarySearch]二分查找
 * @author xmmmmmovo
 * @date 2020/7/28 11:49
 * @param list 列表
 * @param key 需要查找的元素
 * @return 返回是否存在
 * @since version-1.0
 */
fun <T : Comparable<T>> containsInList(list: List<T>, key: T): Boolean {
    val sorted = list.sorted()
    // 这里调用了上面的函数
    val res = binarySearch(sorted, key)
    return res != -1
}
```

时间复杂度：
$$
\mathcal{O}(Nlog_2N + log_2N)\\\\
=\mathcal{O}(Nlog_2N)
$$
空间复杂度:
$$
\mathcal{O}(N)
$$
因为启用了额外的数组。

## 三数之和

本题目也可以使用二分搜索做，最开始是使用蛮力法解决，时间复杂度为$\mathcal{O}(N^3)$，将其中最后一个元素的选取改为二分查找后便成为了$\mathcal{O}(N^2)$，复杂度大大降低。原理就是先排序，依旧是两重循环找出前两个数字，第三个数值利用二分法从剩余元素中找。

```kotlin
/**
 * 查找已排序元素中是否有重复元素
 * @author xmmmmmovo
 * @date 2020/7/28 11:50
 * @param list 列表
 * @return 是否存在重复元素
 * @since version-1.0
 */
fun <T : Comparable<T>> containsDuplicatesInSorted(list: List<T>): Boolean {
    for (i in 0 until list.size - 1) {
        if (list[i] == list[i + 1]) return true
    }
    return false
}

/**
 * 二分法[binarySearch]求三数之和
 * @author xmmmmmovo
 * @date 2020/7/28 16:09
 * @param list 数字列表
 * @return 满足和为0的所有组合的列表
 * @throws IllegalArgumentException 数组元素小于3个时抛出异常
 * @since version-1.0
 */
fun threeSumBinaryFast(list: List<Int>, num: Int): List<List<Int>> {
    val res = LinkedList<List<Int>>()
    val sl = list.sorted().run {
        if (containsDuplicatesInSorted(this))
            distinct()
        else
            this
    }
    if (list.size < 3) throw IllegalArgumentException("数组非重复元素小于3个!")
    for (i in sl.indices) {
        for (j in i + 1 until sl.size) {
            val k = binarySearch(sl, num - (sl[i] + sl[j]), j + 1)
            if (k != -1) {
                res.add(listOf(sl[i], sl[j], sl[k]))
            }
        }
    }

    return res
}
```

时间复杂度方面，排序+循环时间复杂度$\mathcal{O}(N\log_2N+N^2\log_2N)$，化简得：
$$
\mathcal{O}(N^2)
$$
空间复杂度:
$$
\mathcal{O}(N)
$$
排序产生的中间数组。

## 数组局部最小元素

题目是这样描述的：

![题目描述](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/20200731122225.png)

思路已经很明确了，即是每一次都往小部分缩小**1/2**的范围，最终查找到的符合条件的mid就成功了。

```kotlin
/**
 * 局部最小元素
 * @author xmmmmmovo
 * @date 2020/7/30 19:36
 * @param list 数字列表
 * @param _lo 左边界 默认为0
 * @param _hi 右边界 默认为list.size - 1
 * @return 最小元素数字
 * @throws IllegalArgumentException 数组元素小于3个时抛出异常
 * @since version-1.0
 */
fun partialMinElem(list: List<Number>, _lo: Int = 0, _hi: Int = list.size - 1): Int {
    if (list.size < 3) throw IllegalArgumentException("数组元素小于3个！")
    var lo = _lo
    var hi = _hi
    // 两边需要单独测试
    if (list[lo] < list[lo + 1]) return lo
    if (list[hi] < list[hi - 1]) return hi

    while (lo in _lo..hi && hi <= _hi) {
        // 取mid
        val mid = lo + (hi - lo) / 2
        /**
         * 这里分为三个情况
         * ↘↗直接返回
         * ↗↗往左走
         * ↗↘都可以，原题是往小的地方走(因为部分排序过的数组会更快)
         * ↘↘往右走
         * 总之就是往小的地方走
         */
        when {
            mid == _lo ->
                if (list[mid] < list[mid + 1]) return mid
                else lo = mid + 1
            mid == _hi ->
                if (list[mid] < list[mid - 1]) return mid
                else hi = mid - 1
            list[mid - 1] > list[mid] && list[mid] < list[mid + 1] -> {
                return mid
            }
            list[mid - 1] < list[mid] && list[mid] < list[mid + 1] -> {
                hi = mid - 1
            }
            list[mid - 1] < list[mid] && list[mid] > list[mid + 1] -> {
                if (list[mid - 1] >= list[mid + 1]) lo = mid + 1
                else hi = mid - 1
            }
            else -> {
                lo = mid + 1
            }
        }
    }

    // 当所有元素都是一样的时候才没有最小值，返回-1
    return -1
}
```

时间复杂度(最差)：
$$
\mathcal{O}(2log_2N)
$$
为什么是这个时间复杂度呢，因为在最差情况下，向一边走完之后发现没有结果，然后就往另一边走，才发现结果，所以总体是$\mathcal{O}(2log_2N)$。

空间复杂度：
$$
\mathcal{O}(1)
$$

## 矩阵局部最小元素

题目是这样描述的：

![题目描述](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/20200731214656.png)

这个题目也是跟上个题目类似，就是每一次缩减**1/2**的大小，不过这个并非数组，而是一个矩阵，所以我们对于复杂度不能用上一个题目那种分析方式来写。本题目的思路便是先从最中间元素开始搜查，根据上一题目的四种情况进行讨论，横向讨论完在下一次用纵向讨论，这样每一次都是缩减**1/2**，最终找到负荷情况的i，j就可以了。

但其实这个题目**混沌的一批**，如果用`遍历+二分`的做法的话，就会使得时间复杂度成为$\mathcal{O}(Nlog_2N)$，而非题目所要求的$\mathcal{O}(N)$，所以才要一直二分下去。

```kotlin
/**
 * 矩阵局部最小元素
 * @author xmmmmmovo
 * @date 2020/7/30 19:36
 * @param matrix 矩阵
 * @return 最小元素数字
 * @throws IllegalArgumentException 矩阵为空的时候抛出异常
 * @since version-1.0
 */
fun <T : Number> matrixPartialMinElem(matrix: List<List<T>>): Pair<Int, Int> {
    if (matrix.isEmpty()) throw IllegalArgumentException("矩阵不能为空！")
    var lor = 0
    var hir = matrix.size - 1

    while (lor <= hir) {
        val mr = lor + (hir - lor) / 2
        val kc = partialMinElem(matrix[mr])

        when {
            kc == -1 -> {
                lor++
            }
            mr == 0 ->
                if (matrix[mr + 1][kc] > matrix[mr][kc])
                    return Pair(mr, kc)
                else
                    lor = mr + 1
            mr == matrix.size - 1 ->
                if (matrix[mr][kc] < matrix[mr - 1][kc])
                    return Pair(mr, kc)
                else
                    hir = mr - 1
            matrix[mr - 1][kc] > matrix[mr][kc] && matrix[mr][kc] < matrix[mr + 1][kc] ->
                return Pair(mr, kc)
            matrix[mr - 1][kc] < matrix[mr][kc] && matrix[mr][kc] < matrix[mr + 1][kc] ->
                hir = mr - 1
            matrix[mr - 1][kc] < matrix[mr][kc] && matrix[mr][kc] > matrix[mr + 1][kc] ->
                if (matrix[mr - 1][kc] >= matrix[mr + 1][kc]) lor = mr + 1 else hir = mr - 1
            else -> lor = mr + 1
        }
    }

    return Pair(-1, -1)
}
```

时间复杂度方面：

这个我怎么推都是$\mathcal{O}((log_2N)^2)$的复杂度（其实有推出一个$\mathcal{O}(2N)$来，但是总感觉不是特别靠谱），如果有大佬能推出来$\mathcal{O}(N)$的复杂度可以在下面留言，感谢！

空间复杂度方面：
$$
\mathcal{O}(1)
$$
没什么好说的。

## 双调查找

题目是这样描述的：

![image-20200802133247034](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/20200802133254.png)

可以发现，这个像是局部最小值的变形，这里面必定有**极大值**，所以我们把问题分解成了三个子问题：

1. 找到最大值
2. 向左二分找值
3. 向右二分找值

这样三个二分查找总共最差则是$\mathcal{O}(3log_2N)$，满足题意。为什么这里可以直接用二分法找最大值呢，因为这个数组很特殊，先增后减，可以说局部最大值就是最大值，所以可以利用二分查找直接找出。

局部最大函数：

```kotlin
/**
 * 局部最大元素
 * @author xmmmmmovo
 * @date 2020/7/30 19:36
 * @param list 数字列表
 * @param _lo 左边界 默认为0
 * @param _hi 右边界 默认为list.size - 1
 * @return 最大元素下标
 * @throws IllegalArgumentException 数组元素小于3个时抛出异常
 * @since version-1.0
 */
fun <T : Comparable<T>> partialMaxElem(
    list: List<T>, _lo: Int = 0, _hi: Int = list.size - 1
): Int {
    var lo = _lo
    var hi = _hi

    while (lo <= hi) {
        // 取mid
        val mid = lo + (hi - lo) / 2
        when {
            mid == _lo ->
                if (list[mid] > list[mid + 1]) return mid
                else lo = mid + 1
            mid == _hi ->
                if (list[mid] > list[mid - 1]) return mid
                else hi = mid - 1
            list[mid - 1] < list[mid] && list[mid] > list[mid + 1] -> {
                return mid
            }
            list[mid - 1] > list[mid] && list[mid] > list[mid + 1] -> {
                hi = mid - 1
            }
            list[mid - 1] > list[mid] && list[mid] < list[mid + 1] -> {
                if (list[mid - 1] <= list[mid + 1]) lo = mid + 1
                else hi = mid - 1
            }
            else -> {
                lo = mid + 1
            }
        }
    }

    // 当所有元素都是一样的时候才没有最小值，返回-1
    return -1
}
```

双栈查找函数：

```kotlin
/**
 * 双调查找
 * @author xmmmmmovo
 * @date 2020/7/31 15:42
 * @param list 数字列表
 * @param _lo 左边界 默认为0
 * @param _hi 右边界 默认为list.size - 1
 * @return 查找元素下标
 * @throws IllegalArgumentException 查不到最大元素时抛出常
 * @since version-1.0
 */
fun <T : Comparable<T>> doubleToneSearch(
    list: List<T>, key: T, _lo: Int = 0, _hi: Int = list.size - 1
): Int {
    val mi = partialMaxElem(list)
    if (mi == -1)
        throw IllegalArgumentException("请输入正确的双调列表！")
    if (list[mi] == key)
        return mi
    val l = binarySearch(list, key, _lo, mi - 1)
    val r = binarySearch(list.subList(mi + 1, _hi + 1).reversed(), key)

    return when {
        r == -1 -> l
        l == -1 -> _hi - r
        else -> l
    }
}
```

时间复杂度（最差）：
$$
\mathcal{O}((\frac{1}{2}+\frac{1}{2}+2)log_2N) =\\\\
\mathcal{O}(3log_2N)
$$

空间复杂度：
$$
\mathcal{O}(N)
$$
用了一半的反转数组。

## 仅用加减实现的二分查找

题目是这样描述的：

![image-20200802233108582](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/20200802233108.png)

说的挺高深的，其实就是利用倒了`斐波那契数列`，个人感觉可能还能有数列满足指数级，暂时还没时间去想，有空可能会去想。

为什么能用`斐波那契数列`来求解呢？这还要跟`斐波那契数列`的特性有关系，我们知道`斐波那契数列`的规律是这样的：
$$
\mathcal{f}(n)=
\begin{cases}
1,  & \mbox{if }n\mbox{ is 1} \\\\
1, & \mbox{if }n\mbox{ is 2} \\\\
\mathcal{f}(n - 1) + \mathcal{f}(n-2), &\mbox{if }n\mbox{ is >=3}
\end{cases}
$$
所以从分割点的左右两边来看，都包含有`f(1)..f(n-2)`的所有信息，只不过右边比左边多出了`f(n-1)`，所以无论是左边分还是右边往下分，都是可以分离直到`f(1)`产生的，这就是为什么能用`斐波那契数列`代替二分搜索的原因。

知道了原因，我们就来思考条件，首先一个首要条件便是：**列表大小必须是斐波那契数列其中的某个元素 - 1**才可以进行，所以我们需要先将数组扩充到大于这个数组长度的最小`斐波那契数列`的值。

```kotlin
/**
 * 创建最大值大于[length]的第一个数
 * @author xmmmmmovo
 * @date 2020/8/3 1:01
 * @param length 最长值
 * @return 数列
 * @since version-1.0
 */
fun makeFibonacciListUntilLength(length: Int): List<Int> {
    return when (length) {
        0 -> emptyList()
        1 -> listOf(1, 1, 2)
        2 -> listOf(1, 1, 2, 3, 5)
        else -> {
            val fl = mutableListOf(1, 1)
            var nv = 2
            while (length > nv - 1) {
                fl.add(nv)
                nv += fl[fl.size - 2]
            }
            fl.add(nv)
            fl
        }
    }
}

/**
 * 斐波那契二分搜索
 * @author xmmmmmovo
 * @date 2020/7/31 16:09
 * @param list 列表
 * @param key 需要查找的值
 * @param _lo 左范围 默认为0
 * @param _hi 右范围 默认为list.size - 1
 * @return 查找到了就返回下标，没查找到就返回-1
 * @since version-1.0
 */
fun <T : Comparable<T>> fibonacciBinarySearch(
    list: List<T>, key: T, _lo: Int = 0, _hi: Int = list.size - 1
): Int {
    if (list.isEmpty()) return -1
    if (list.size < 3) return list.indexOf(key)

    // 此时最末尾的值肯定是刚好大于长度的那个
    val fbl = makeFibonacciListUntilLength(_hi - _lo + 1)
    val tl = list.toMutableList()
    tl.addAll(List((fbl.last() - 1 - list.size)) { list.last() })

    var lo = _lo
    var hi = if (_hi == list.lastIndex) tl.lastIndex else _hi
    var k = fbl.lastIndex

    while (lo <= hi) {
        val mid = lo + fbl[k - 1] - 1
        when {
            tl[mid] > key -> {
                hi = mid - 1
                k--
            }
            // 小堆就-2，因为少了f(n-1)的信息
            tl[mid] < key -> {
                lo = mid + 1
                k -= 2
            }
            else -> return if (mid >= _hi) list.lastIndex else mid
        }
    }

    return -1
}
```

时间复杂度：
$$
\mathcal{O}(log_2N)
$$
空间复杂度：
$$
\mathcal{O}(N)
$$
越往后来说空间增加都近似于前一个数值的$\frac{1}{3}$，所以空间复杂度约为$\mathcal{O}(N)$

## Github

[Github](https://github.com/xmmmmmovo/Algorithms4thEditionKotlinSolutions)

算法(第四版)笔记(7)---二分搜索和一些应用

简单的实践操作

## 前言

这两天一直在写算法，但是一个一个测试太麻烦了，并且也没有文档看，简直累人，所以就写了个`action`让它自动生成并部署到`GithubPage`上面去，爽了。

## 测试

### 引入依赖

```groovy
dependencies {
    ......
    testImplementation(
            'org.assertj:assertj-core:3.12.2',
            'org.junit.jupiter:junit-jupiter-api:5.4.2'
    )
    testRuntime('org.junit.jupiter:junit-jupiter-engine:5.4.2')
}
```

### 编写测试task

```groovy
test {
    useJUnitPlatform()
}
```

完成！看看效果吧~

![test](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/20200728100426.png)

测试成功~

## 文档生成

本次使用的是`kotlin`官方文档生成器[**dokka**](https://github.com/Kotlin/dokka)，内含有多种生成方案，并且可以集成到`Gradle`中，爽的。

### 引入依赖

这里以插件方式引入：

```groovy
plugins {
    ......
    id 'org.jetbrains.dokka' version '0.10.1'
}
```

### 编写task

```groovy
dokka {
    // 样式，具体看官方文档
    outputFormat = 'javadoc'
    outputDirectory = "$buildDir/dokka"
    disableAutoconfiguration = false

    cacheRoot = 'default'

    configuration {
        moduleName = 'doc'

        // Use to include or exclude non public members.
        includeNonPublic = false

        // Do not output deprecated members. Applies globally, can be overridden by packageOptions
        skipDeprecated = false

        // Emit warnings about not documented members. Applies globally, also can be overridden by packageOptions
        reportUndocumented = true

        // Do not create index pages for empty packages
        skipEmptyPackages = true

        // This is a list of platform names that will be shown in the final result. See the "Platforms" section of this readme
        targets = ["JVM"]

        // Platform used for code analysis. See the "Platforms" section of this readme
        platform = "JVM"

        sourceRoot {
            // 源文件目录
            path = "src"
        }

        sourceLink {
            // Unix based directory relative path to the root of the project (where you execute gradle respectively).
            path = "src/main/kotlin" // or simply "./"

            // URL showing where the source code can be accessed through the web browser
            url = "https://github.com/xmmmmmovo/Algorithms4thEditionKotlinSolutions/blob/master/src/main/kotlin" //remove src/main/kotlin if you use "./" above

            // 指定行数前缀，github是#L
            lineSuffix = "#L"
        }

        // 用于链接java官方文档
        jdkVersion = 8

        // Disable linking to online kotlin-stdlib documentation
        noStdlibLink = false

        // Disable linking to online JDK documentation
        noJdkLink = false
    }
}
```

完成！看看效果~

![](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/20200728101048.png)

![](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/20200728101144.png)

成功~

## 自动化

每次都运行脚本太累了，干脆直接用`CI`自动跑了，这里用的是`GithubAction`，具体如何使用可以看：[如何利用GitHubAction和GithubPage部署React应用](https://blog.fivezha.cn/2020/07/21/github-action-demo/) 这篇，这里只写出`yml`文件:

```yaml
# workflow name
name: Test Workflow

on:
  push:
    branches:
      - master

jobs:
  test:
    name: Kotlin Tests
    runs-on: ubuntu-latest
    env:
      TZ: Asia/Shanghai

    steps:
      # check it to your workflow can access it
      # from: https://github.com/actions/checkout
      - name: Checkout Repository master branch
        uses: actions/checkout@master

      # 验证wrapper
      - name: validate wrapper
        uses: gradle/wrapper-validation-action@v1

      # 安装jdk
      - name: Set up JDK 8
        uses: actions/setup-java@v1
        with:
          java-version: 1.8

      # 缓存
      - name: Cache Gradle packages
        uses: actions/cache@v2
        with:
          path: ~/.gradle/caches
          key: ${{ runner.os }}-gradle-${{ hashFiles('**/*.gradle') }}
          restore-keys: ${{ runner.os }}-gradle

      # 给权限
      - name: Grant execute permission for gradlew
        run: chmod +x gradlew

      # 测试程序
      - name: Test with gradle
        run: ./gradlew test
```

```yaml
# workflow name
name: Doc Workflow

on:
  release:
    types: [published]
    branches:
      - master

jobs:
  test:
    name: Kotlin Documentation Generation
    runs-on: ubuntu-latest
    env:
      TZ: Asia/Shanghai

    steps:
      # check it to your workflow can access it
      # from: https://github.com/actions/checkout
      - name: Checkout Repository master branch
        uses: actions/checkout@master

      # 验证wrapper
      - name: validate wrapper
        uses: gradle/wrapper-validation-action@v1

      # 安装jdk
      - name: Set up JDK 8
        uses: actions/setup-java@v1
        with:
          java-version: 1.8

      # 缓存
      - name: Cache Gradle packages
        uses: actions/cache@v2
        with:
          path: ~/.gradle/caches
          key: ${{ runner.os }}-gradle-${{ hashFiles('**/*.gradle') }}
          restore-keys: ${{ runner.os }}-gradle

      # 给权限
      - name: Grant execute permission for gradlew
        run: chmod +x gradlew

      # 缓存
      # 暂时还未找到hash值的解决方案，找到了请pr
      # - name: Cache Dokka
      #   uses: actions/cache@v2
      #   with:
      #     path: ~/.cache/dokka
      #     key: ${{ runner.os }}-dokka-${{ hashFiles('**/*') }}
      #     restore-keys: ${{ runner.os }}-dokka

      # 生成文档
      - name: Generate documentation
        run: ./gradlew dokka

      # 部署到ghpage
      - name: Deploy to gh-pages
        uses: peaceiris/actions-gh-pages@v3
        with:
          deploy_key: ${{ secrets.ACTIONS_DEPLOY_KEY }}
          publish_dir: ./build/dokka

```

完成！测试一下~

![](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/20200728101648.png)

成功~

## 结语

爽到了爽到了~

[GitHub地址](https://github.com/xmmmmmovo/Algorithms4thEditionKotlinSolutions)

如何利用GitHubAction自动化测试你的kotlin程序并部署文档到GithubPage

差点翻车

## 前言

`GithubAction`作为`Github`提供的免费的`CI/CD`服务，让开发者感受到了自动化的爽，相比起`Travis CI`来说，`GitHubAction`集成方便，非常适合快速部署的操作，本教程便是一篇如何利用`GithubAction`对于`GithubPage+Hexo`博客进行自动化部署，并利用`gulp`进行压缩。

## 配置GithubAction

### 生成key

首先依旧是申请key，

```shell
cd ~/.ssh
ssh-keygen -t rsa -b 4096 -C "$(git config user.email)" -f gh-pages -N ""
```

![image-20200724215856700](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/image-20200724215856700.png)

此时会生成**.pub的公钥与没有后缀的私钥**：

![成功生成密钥](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/image-20200721154822499.png)

### 配置仓库

首先新建一个空仓库，用于存放你的博客根目录，新建完成后将**博客根目录**所有文件都上传到这个仓库中，传完项目结构大体如下：

![image-20200724220337436](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/image-20200724220337436.png)

然后开始配置仓库，首先

![image-20200724220449987](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/image-20200724220449987.png)

![image-20200724220517055](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/image-20200724220517055.png)

配置成你的公钥，然后在上传博客的仓库中，上传你的私钥：

![image-20200724220651398](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/image-20200724220651398.png)

**注意这里的私钥名字一定要跟后面Action里面设置的一样！(不知道就跟我一样)**

### 配置workflow

在博客根目录新建`.github`文件夹，再在`.github`文件夹里新建`workflows`文件夹，新建完在`workflows`文件夹里新建`deploy.yml`文件，然后按照如下编写：

```yaml
# workflow name
name: Deploy To Github Pages

# 当有 push 到仓库就运行
on: [push]

jobs:
  deploy: 
    name: Deploy Hexo Public To Pages
    runs-on: ubuntu-latest 
    env:
      TZ: Asia/Shanghai    
        
    steps:
    # 切换到master
    # from: https://github.com/actions/checkout
    - name: Checkout Repository master branch
      uses: actions/checkout@master 
    
    # 安装node
    # from: https://github.com/actions/setup-node  
    - name: Setup Node.js 11.x 
      uses: actions/setup-node@master
      with:
        node-version: "11.x"
    
    # 缓存 node_modules
    - name: Cache node modules
      uses: actions/cache@v2
      with:
        path: ~/.npm
        key: ${{ runner.os }}-node-${{ hashFiles('**/package-lock.json') }}
        restore-keys: |
          ${{ runner.OS }}-build-${{ env.cache-name }}-
          ${{ runner.OS }}-build-
          ${{ runner.OS }}-

    # 安装hexo并生成
    - name: Setup Hexo Dependencies
      run: |
        npm install hexo-cli -g
        npm install
        hexo generate
        
    # 部署到GitHubPage
    # from https://github.com/peaceiris/actions-gh-pages    
    - name: Deploy
      uses: peaceiris/actions-gh-pages@v3
      with:
        deploy_key: ${{ secrets.ACTIONS_DEPLOY_KEY }}
        # 这里写你自己的仓库名
        external_repository: xmmmmmovo/xmmmmmovo.github.io
        publish_branch: master
        publish_dir: ./public
        commit_message: ${{ github.event.head_commit.message }}

```

好了，这样就已经配置完成了，你每次提交到此仓库，便会自动帮你运行部署到GithubPage上去。

### 测试

![image-20200724221510619](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/image-20200724221510619.png)

![image-20200724221450653](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/image-20200724221450653.png)

可以看到，已经成功运行了。

## 配置gulp

我们随便点开一个文件：

![image-20200724221832348](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/image-20200724221832348.png)

可以看到，里面充斥着大量的空格，积少成多，这会占用非常多的时间，让你的博客感觉加载起来很慢，所以既然我们都是全自动化部署了，我们不如直接在进行一遍压缩操作，这样使你博客加载的更加迅速，体验更加良好。

### 安装gulp

首先进到博客根目录，然后打开命令行，输入(这里其实你直接在`package.json`里面写也行(因为node_modules已经没用了)，但是我比较懒)：

```shell
npm install gulp@3.9.1 gulp-minify-css gulp-htmlmin gulp-htmlclean --save-dev
```

待完成后，改写`deploy.yml`：

```yaml
# workflow name
name: Deploy To Github Pages

# 当有 push 到仓库就运行
on: [push]

jobs:
  deploy: 
    name: Deploy Hexo Public To Pages
    runs-on: ubuntu-latest 
    env:
      TZ: Asia/Shanghai    
        
    steps:
    # 切换到master
    # from: https://github.com/actions/checkout
    - name: Checkout Repository master branch
      uses: actions/checkout@master 
    
    # 安装node
    # from: https://github.com/actions/setup-node  
    - name: Setup Node.js 11.x 
      uses: actions/setup-node@master
      with:
        node-version: "11.x"
    
    # 缓存 node_modules
    - name: Cache node modules
      uses: actions/cache@v2
      with:
        path: ~/.npm
        key: ${{ runner.os }}-node-${{ hashFiles('**/package-lock.json') }}
        restore-keys: |
          ${{ runner.OS }}-build-${{ env.cache-name }}-
          ${{ runner.OS }}-build-
          ${{ runner.OS }}-

    # 安装hexo并生成
    - name: Setup Hexo Dependencies
      run: |
        npm install hexo-cli -g
        npm install
        hexo generate
        gulp
        
    # 部署到GitHubPage
    # from https://github.com/peaceiris/actions-gh-pages    
    - name: Deploy
      uses: peaceiris/actions-gh-pages@v3
      with:
        deploy_key: ${{ secrets.ACTIONS_DEPLOY_KEY }}
        # 这里写你自己的仓库名
        external_repository: xmmmmmovo/xmmmmmovo.github.io
        publish_branch: master
        publish_dir: ./public
        # 这里我改成了与原格式相似格式的commit message
        commit_message: 'Site updated: ${{ github.event.head_commit.timestamp }}'

```

然后编写`gulpfile.js`文件用来加载`gulp`：

```javascript
var gulp = require('gulp');
var minifycss = require('gulp-minify-css');
var htmlmin = require('gulp-htmlmin');
var htmlclean = require('gulp-htmlclean');
gulp.task('minify-css', function() {
    return gulp.src('./public/**/*.css')
        .pipe(minifycss())
        .pipe(gulp.dest('./public'))
});
gulp.task('minify-html', function() {
  return gulp.src('./public/**/*.html')
    .pipe(htmlclean())
    .pipe(htmlmin({
         removeComments: true,
         minifyJS: true,
         minifyCSS: true,
         minifyURLs: true
    }))
    .pipe(gulp.dest('./public'))
});
gulp.task('default', ['minify-html', 'minify-css']);
```

此时再次提交，等待`GithubAction`完成之后，便可以查看效果了~

![image-20200724222548668](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/image-20200724222548668.png)

可以看到800多行瞬间变为了16行，是不是很爽~

如何利用GitHubAction和gulp自动化部署压缩你的GithubPage+Hexo博客

第一次看见的前面就标有极难的题目

## 思路

### 参考

本问题其实是有一篇论文作为参考的:

{% pdf https://ecommons.cornell.edu/bitstream/handle/1813/6273/80-433.pdf %}

这篇论文是以`LISP`作为实现语言的，我们本次依旧是使用`kotlin`进行实现。

当然，这里三个栈需要实现的是**双向队列**的**API**，六个栈实现的是**单向队列**。

### 实现思路

首先，先要说明一个事情——其实栈的实现大多数都是利用`顺序表`来进行实现的，但是根据算法第四版里面的实现方案，栈其实是利用链表来实现的，虽然不影响后面复杂度分析，但是底层区别首先在这里说清楚。

然而，队列的实现有着`顺序表`和`链表`两种解决方案，用`顺序表`虽然出队列也依旧是$\mathcal{O}(1)$的效率，但是随着标志位的后移，需要的空间会**线性增长**，但是如果不后移则会变成$\mathcal{O}(N)$的复杂度，所以衍生出了`循环队列`的中间方案。不过`Java`源码中，给出了一个非常巧妙的方案，它将`Queue`和`Deque`作为一个接口，让其他数据结构实现这个接口，这样无论是`链表`还是`线性表`，只要实现了这个接口，就可以作为队列来使用。

言归正传，回到这个问题，要分析多个栈实现队列，我们首先分析双栈情况，就是左右横跳，用另一个栈作为中间栈，每一次出队列先把所有的元素移动到另一个栈中再出栈，这样出栈时间复杂度$\mathcal{O}(N)$，入栈直接压入原栈，时间复杂度$\mathcal{O}(1)$，但如果我们再利用多个栈进行模拟，就可以把所有操作压缩到$\mathcal{O}(1)$的时间复杂度了。

根据算法第四版的题目描述，设定的是利用3个栈进行实现，但是这是均摊时间复杂度之后达到的$\mathcal{O}(1)$，不是真$\mathcal{O}(1)$，所以本文章又给出了第二种利用六个栈实现的方案。

## 三个栈实现双向队列(虚假的$\mathcal{O}(1)$)

主要实现`Deque`的几个方法，具体代码解释已经写到注释里面了，所以直接放代码了：

```kotlin
package ds

/*
 * 使用三个栈实现队列
 * 使得所有操作都是O(1)
 *  @Author xmmmmmovo
 *  @Version 1.0
 **/
class StackDeque<T> {
    // 左栈
    private val lst = Stack<T>()

    // 右栈
    private val rst = Stack<T>()

    // 中间栈
    private val tst = Stack<T>()

    // 表示存储的栈位置
    private var tmpIsRight = false


    fun isEmpty(): Boolean =
            lst.isEmpty() && rst.isEmpty() && tst.isEmpty()

    /**
     * 入左队列
     * */
    fun pushLeft(element: T) {
        lst.push(element)
    }

    /**
     * 入右队列
     * */
    fun pushRight(element: T) {
        rst.push(element)
    }

    /**
     * 出左队列(对应的是入右队列
     * */
    fun popLeft(): T {
        return when {
            /*
            * 这里如果左栈有值的话就说明要么左边插入值了
            * 要么右边或者中转栈转移到了左栈，无论哪种情况都是栈顶就是最左
            * 直接出栈就可以
            * */
            lst.isNotEmpty() -> lst.pop()
            /**
             * 这里先判断中转栈内容是否是存的右栈的内容
             * 判断如果是右栈的内容，再判断中转栈是否是空的
             * 如果不是就说明右栈已经转移到中转栈中了
             * 相当于移动到了左栈，所以直接弹出中转栈
             * */
            tst.isNotEmpty() && tmpIsRight -> tst.pop()
            /**
             * 这里先判断中转栈内容是否是存的右栈的内容
             * 判断如果不是右栈的内容，再判断中转栈是否是空的
             * 如果不是就说明是左栈移动到了中栈了
             * 相当于移动到了右栈，所以先弹出到左栈再弹出左栈
             * */
            tst.isNotEmpty() && !tmpIsRight -> {
                while (tst.isNotEmpty())
                    lst.push(tst.pop())
                lst.pop()
            }
            /**
             * 这里如果是中转栈是空的并且右栈不为空
             * 就直接转移到中转栈再弹出中转栈
             * */
            tst.isEmpty() && rst.isNotEmpty() -> {
                while (rst.isNotEmpty())
                    tst.push(rst.pop())
                tmpIsRight = true // 存的是右栈
                tst.pop()
            }
            /**
             * 所有栈都没有内容，自然就抛出异常
             * */
            else -> throw NoSuchElementException("Stack underflow")
        }
    }

    /**
     * 出右队列(对应的是出左队列
     * */
    fun popRight(): T {
        return when {
            rst.isNotEmpty() -> rst.pop()
            tst.isNotEmpty() && !tmpIsRight -> tst.pop()
            tst.isNotEmpty() && tmpIsRight -> {
                while (!tst.isEmpty())
                    rst.push(tst.pop())
                rst.pop()
            }
            tst.isEmpty() && lst.isNotEmpty() -> {
                while (lst.isNotEmpty())
                    tst.push(lst.pop())
                tmpIsRight = false // 存的是左栈
                tst.pop()
            }
            else -> throw NoSuchElementException("Stack underflow")
        }
    }

    val size: Int
        get() = lst.size + rst.size + tst.size

    fun asList(): List<T> {
        val list = mutableListOf<T>()
        lst.forEach {
            list.add(it)
        }
        // 如果非空那就得判断tmp里面存储的是左还是右了
        // 但是右栈一定要翻转
        tst.run {
            if (tmpIsRight) this else reversed()
        }.forEach { list.add(it) }
        rst.reversed().forEach {
            list.add(it)
        }
        return list
    }

    override fun toString(): String = asList().toString()
}
```

### 测试

```kotlin
val sq = StackDeque<String>()
sq.pushLeft("a")
sq.pushLeft("b")
sq.pushLeft("c")
sq.pushLeft("d")
sq.pushLeft("e")
println(sq.popRight())
sq.pushRight("f")
sq.pushRight("g")
sq.pushRight("h")
println(sq.asList())
```

![image-20200725134752097](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/image-20200725134752097.png)

### 分析

时间复杂度：

这里我们主要分析出队列的时间复杂度，因为入队列操作仅是一个入栈操作，时间复杂度：
$$
\mathcal{O}(1)
$$
出队列方面，因为两端出队列思想相似，所以仅分析其中一边即可。

可以看到，首先先说明一下，队列是先进先出的，所以是`右进左出`，`左进右出`，选择右进左出分析，可以看到出方向首先尝试从另一边栈进行出栈操作，如果成功就是$\mathcal{O}(1)$，如果失败就继续判断中转栈是否是右栈内容，尝试从中转栈进行出栈，成功依旧是$\mathcal{O}(1)$，当中转栈是左栈或者只有右栈不为空的时候，所需要的时间复杂度才为$\mathcal{O}(N)$，所以考虑N个元素，最差情况是便是`左进右出`情况，因为此时才会存在移栈，此时仅在第一次出队列时时间复杂度为$\mathcal{O}(N)$。所以均摊时间复杂度下，出队列操作的时间复杂度为：
$$
\mathcal{O}(N/N)\\\\
= \mathcal{O}(1)
$$
可以看到是均摊后时间复杂度才达到$\mathcal{O}(1)$，所以是虚假的$\mathcal{O}(1)$。

空间复杂度：

虽然这里用到了三个栈，但是所有需求空间加起来是等于添加的总元素的，所以空间是成线性增长的，所以空间复杂度是：
$$
\mathcal{O}(N)
$$

## 六个栈实现单向队列(真正的$\mathcal{O}(1)$)

因为双向会更加绕，所以这里选用单项队列进行讲解，主要方向是`右进左出`。当然，这里的思想跟上面的有些许不同，三个栈的情况是存在单次操作$\mathcal{O}(N)$的，所以在这里我们将解决这个问题。

参考博客文章：[点此跳转](https://www.cnblogs.com/ikesnowy/p/7157813.html)

根据上面的思路，我们发现了整个实现的思路就是**均摊**，作为双向队列，如果仅用三个栈的话，中间栈只能存储一个栈，所以我们无论如何都需要有一次进行单个栈所有元素转存的方案，所以无法均摊到单个操作上(如果有四个栈可能可行)，但是本次仅用作单项队列，所以对于出栈来说只是左栈需要转存，所以可以把转存操作均摊到每一个出栈操作上来。

整体思路上是在入队列的时候便使得左右两个栈尽量相等，然后在出栈的时候再进行判断。

```kotlin
/*
 * Copyright (c) 2020. xmmmmmovo
 */
package ds

/**
 * 用六个栈实现单向队列
 * @author xmmmmmovo
 * @date 2020/7/28 16:43
 * @since version-1.0
 */
class StackDequeOpt<T> {
    /**
     * 左栈
     */
    private var lst = Stack<T>()

    /**
     * 右栈
     */
    private var rst = Stack<T>()

    /**
     * 左栈替换栈 用于复制时转换
     */
    private var tlst = Stack<T>()

    /**
     * 右栈替换栈 用于复制时候入队
     */
    private var trst = Stack<T>()

    /**
     * 左翻转栈，用于保护左栈原有数据
     */
    private var lstrev = Stack<T>()

    /**
     * 用于复制过程中的出栈操作
     */
    private var hlst = Stack<T>()

    /**
     * 判断是否在复制
     */
    private var isCopying = false

    /**
     * 需要复制数量
     */
    private var needCopy = 0

    /**
     * 队列是否为空
     * @author xmmmmmovo
     * @date 2020/7/29 16:54
     * @return 返回是否为空
     * @since version-1.0
     */
    fun isEmpty(): Boolean =
        lst.isEmpty() && rst.isEmpty() && tlst.isEmpty() && trst.isEmpty() && lstrev.isEmpty()


    /**
     * 入右队列
     * @author xmmmmmovo
     * @date 2020/7/29 16:55
     * @param element 入元素
     * @since version-1.0
     */
    fun pushRight(element: T) {
        when {
            /**
             * 左栈大于右栈
             */
            !isCopying && sizeDiff > 0 -> {
                needCopy = 0
                rst.push(element)
            }
            /**
             * 左右栈相等的时候，因为不知道下一步操作
             * 所以提前准备来进行复制操作
             */
            !isCopying && sizeDiff == 0 -> {
                rst.push(element)
                isCopying = true
                hlst = lst.clone()
                oneStep()
                oneStep()
            }
            /**
             * 如果还在复制直接 入栈到中转栈
             * 因为原栈需要别的用处
             */
            isCopying -> {
                tlst.push(element)
                oneStep()
                oneStep()
            }
        }
    }


    /**
     * 出左队列
     * @author xmmmmmovo
     * @date 2020/7/29 16:55
     * @return 返回队列第一个元素
     * @throws NoSuchElementException 没有元素时抛出
     * @since version-1.0
     */
    fun popLeft(): T {
        when {
            /**
             * 如果没有在copy的时候并且左大于右则直接左栈弹出
             */
            !isCopying && sizeDiff > 0 -> {
                return lst.pop()
            }
            /**
             * 如果没有在复制并且左栈刚好等于右栈，那么就直接弹出左栈
             * 这样左栈小于右栈，进入复制状态
             */
            !isCopying && sizeDiff == 0 -> {
                val t = lst.pop()
                hlst = lst.clone()
                isCopying = true
                oneStep()
                oneStep()
                return t
            }
            /**
             * 因为复制状态下，所有左栈元素会到hlst中所以直接hlst出栈
             */
            else -> {
                val t = hlst.pop()
                needCopy--
                oneStep()
                oneStep()
                return t
            }
        }
    }

    /**
     * 预览元素
     * @author xmmmmmovo
     * @date 2020/7/29 16:56
     * @return 返回队列第一个元素
     * @throws NoSuchElementException 没有元素时抛出
     * @since version-1.0
     */
    fun peekLeft(): T = if (isCopying) hlst.peek() else lst.peek()

    /**
     * 中间操作 这里是脱离了入栈出栈操作的额外操作
     * @author xmmmmmovo
     * @date 2020/7/29 20:32
     * @since version-1.0
     */
    private fun oneStep() {
        when {
            /**
             * 正在copy的时候左右栈都不是空的，这说明需要进行交换了
             * 本次这里右栈进入左栈中转栈
             * 左栈进入左栈反转栈(用于后面直接替换
             */
            isCopying && lst.isNotEmpty() && rst.isNotEmpty() -> {
                needCopy++
                tlst.push(rst.pop())
                lstrev.push(lst.pop())
            }
            /**
             * 此状态说明此时左栈已经完成转移，右栈还有剩余
             * 把右栈的元素移动到左栈中转栈中
             */
            isCopying && lst.isEmpty() && rst.isNotEmpty() -> {
                isCopying = true
                tlst.push(rst.pop())
            }
            /**
             * 此时说明左右栈都是空栈了
             * 但是需要复制的数量大于1
             * 就说明lstrev还有剩余可以转移的元素
             * 直接转移到左中转栈用于后面计算
             */
            isCopying && lst.isEmpty() && rst.isEmpty() && needCopy > 1 -> {
                isCopying = true
                needCopy--
                tlst.push(lstrev.pop())
            }
            /**
             * 如果左右栈都为空， 并且仅有一个需要复制的
             * 那么就直接把最后一个元素并入左栈中转栈
             * 中转栈转为主栈 就完成了一个循环
             */
            isCopying && lst.isEmpty() && rst.isEmpty() && needCopy == 1 -> {
                isCopying = false
                needCopy--
                tlst.push(lstrev.pop())
                lst = tlst
                rst = trst
                tlst = Stack()
                trst = Stack()
                lstrev = Stack()
                hlst = Stack()
            }
            /**
             * 同上
             */
            isCopying && lst.isEmpty() && rst.isEmpty() && needCopy == 0 -> {
                isCopying = false
                lst = tlst
                rst = trst
                tlst = Stack()
                trst = Stack()
                lstrev = Stack()
                hlst = Stack()
            }
        }
    }

    /**
     * 左栈-右栈大小的差值
     * @author xmmmmmovo
     * @date 2020/7/29 20:33
     * @since version-1.0
     */
    private val sizeDiff: Int
        get() = lst.size - rst.size

    /**
     * 队列总长度
     * @author xmmmmmovo
     * @date 2020/7/29 20:33
     * @since version-1.0
     */
    val size: Int
        get() = lst.size + rst.size + tlst.size + trst.size + lstrev.size
}
```

### 测试

```kotlin
/*
 * Copyright (c) 2020. xmmmmmovo
 */

package fundamental

import ds.StackDequeOpt
import org.junit.jupiter.api.*

import org.junit.jupiter.api.Assertions.*
import org.junit.platform.commons.logging.LoggerFactory

internal class StackDequeOptTest {
    private val sdo = StackDequeOpt<Int>()

    companion object {
        private val log = LoggerFactory.getLogger(StackDequeOptTest::class.java)

        @BeforeAll
        @JvmStatic
        fun before() {
            log.info { "StackDequeOptTest start" }
        }

        @AfterAll
        @JvmStatic
        fun after() {
            log.info { "StackDequeOptTest end" }
        }
    }

    @Test
    fun isEmpty() {
        assertEquals(true, sdo.isEmpty())
        sdo.pushRight(1)
        assertEquals(false, sdo.isEmpty())
        sdo.popLeft()
        assertEquals(true, sdo.isEmpty())
    }

    @Test
    fun pushRight() {
        sdo.pushRight(1)
        sdo.pushRight(2)
        sdo.pushRight(3)
        assertEquals(3, sdo.popLeft())
        assertEquals(2, sdo.popLeft())
        assertEquals(1, sdo.popLeft())
    }

    @Test
    fun peekLeft() {
        sdo.pushRight(1)
        sdo.pushRight(2)
        sdo.pushRight(3)
        assertEquals(3, sdo.peekLeft())
        sdo.popLeft()
        assertEquals(2, sdo.peekLeft())
    }

    @Test
    fun getSize() {
        assertEquals(0, sdo.size)
        sdo.pushRight(1)
        assertEquals(1, sdo.size)
        sdo.popLeft()
        assertEquals(0, sdo.size)
        sdo.pushRight(1)
        sdo.pushRight(2)
        sdo.pushRight(3)
        assertEquals(3, sdo.size)
    }
}
```

![](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/20200730001450.png)

### 分析

时间复杂度：

这里所有复杂度都均摊到了每一个操作上，不会出现某些情况时间复杂度激升的情况，综合时间复杂度：
$$
\mathcal{O}(1)
$$
空间复杂度：
$$
\mathcal{O}(N)
$$

## 总结

关于这个题目也是众说纷纭，有的人说作者已经将题目改成了有限个栈而非三个栈，但是官方网站上却标注着使用三个栈实现，然而因为疫情原因，纸质书依旧在学校里躺着，没法证明，但就从电子版来看，作者有很大可能也没有改题。其实这个题目在`stackoverflow`上面也有人询问([链接](https://stackoverflow.com/questions/5538192/how-to-implement-a-queue-with-three-stacks))，但是大多数人都暗示了使用三个栈是不可能存在真正的$\mathcal{O}(1)$的，当然也有一些抖机灵的解法——比如某些`套娃栈`的邪道解法，真的是天马行空。不管怎么说，对于一道存在这么个争议的题目，也就仅是能到这里了。

## Github

[Github](https://github.com/xmmmmmovo/Algorithms4thEditionKotlinSolutions)