本博客可能要有一段时间不更新了(泣)

## 前言

已经有一段时间(两个月)没更新过博客了。上下思索，主要有两个原因：一是开学了，事务变多，无心管理博客相关更新，再加上大四的老狗已经无法再在实验室混日子了，导致我现在碰电脑的时间几乎消失掉了；二是面临考研（其实我是不想考的 但是被父母裹挟 很难受），从早晨6：30起床去图书馆再到晚上9：30回去，11点宿舍熄灯，实在是没有时间进行长时间的编程作业，对于博客也没有有效的产出。综上原因，本博客大概率在**12月28日**之前不会更新了。

## 正文

那么开学的这两个月我到底干了什么呢？细细想来大概就几件事情了。

### 物联网大课设

首先便是物联网大课设了，这个课设的全面程度其实大概是和毕设差不多的吧，不仅要前端后端硬件，还需要安卓来辅佐，实在是全(sang)面(xin)完(bing)善(kuang)呢。

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

上面虽然说的四个人组队，但是如果真的经历过课设/大作业的懂得都懂，其实大多是时间就是一个人写完。这个课设说混也好混，因为课设不挂人，只要你过去了，然后项目能跑起来，就能过(分数不在考虑范围)。然而我不知道怎么想的，就愣是想要把这个课设做的尽量的做的多一些，可能是为了给自己大学四年的技术栈做一个总结吧，我这么想着，就做了整整半个多月，甚至还抽出一天通宵写课设。

开源地址：https://github.com/xmmmmmovo/SmartGreenhouse

![通宵时间](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/20201015231958.jpg)

(时间比较赶所以桌子比较乱 斯密马赛)

最后附上一张项目的架构图片：

![架构图](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/flows.png)

和一点截图：

![安卓](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/20201016090532.jpg)

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

### 综测奖学金

这个事情算是近期来最舒服的一件事情了~~(毕竟没有人跟钱过不去)~~，经过了一整年的艰苦学习，终于拿到了一等奖学金了。回首这一年的学习时光，实在是艰辛，前半年每节课都坐在第一排认真听课，在最后一周无数门考试考试周中拼尽力气，在这后半年网课生活中，通宵写文档，可以说这一年，很累，但是确实是我大学三年废物生活中最有意义的一年了。

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

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

对了，为什么非要拿一等奖学金呢，此事还因为大二一些原因导致没拿到奖学金，所以自己决定不蒸馒头争口气，大二结束立下的flag——势必拿下奖学金，最后成功收回一等奖学金flag，舒服~

### 玩乐

虽然考研复习很紧张，本鼠人还是抽出了国庆一天时间跟朋友出去尽情的玩耍，吃了海底捞(我的奖学金​哭了😥​)，看了姜子牙。最大的感触可能就是希望自己像最后彩蛋里那样，一战封神吧。

![快乐的火锅人](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/20201016092156.png)

![等待排队时候的咖啡](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/20201016100714.jpg)

![祝大家一战封神](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/20201016100531.jpg)

### 沉迷看管人

我是一个很容易沉迷一件事情的人，这种性格也带到了看管人这件事情上，在此文之前，我关注列表中唯一一位虚拟主播便是`新科娘Official`，可以说我已经习惯于周五晚上看着新科娘闲聊整活悠闲的度过一个晚上。就在某一天晚上，舍友给晚上正巧闲下来想放松却没有主播~~黑听~~的我推荐之后便让我沉迷于看某位管人这件事情。

起因是这样的：

> 我：速速来点黑听电台
> 
> 能：你可以去看看阿梓
> 
> 我：谁啊？
> 
> 能：直播间510，速看。
> 
> 然后点进去.....
> 
> 我：啊 这不是阿梓吗 以前笙歌经常查房知道的，原来现在也去做V了。
> 
> 能：你这不是知道吗，黑听很爽。
> 
> 我：酱紫啊，那点个关注先！

回到直播内容上来，黑听确实很爽，不论是杂谈还是唱歌都是非常的享受，阿梓干净透亮可爱自信的声音搭配上偶尔有些天然呆的想法让直播间充满了轻松愉快的氛围，粉丝们也互相称呼为扎人，也像是真的扎人们那样互相打趣，同时科班出身的她也有着不俗的歌力，民美流行都能拿捏，再加上每天晚上不迟到和酬勤的日程表，实在是很难理解为什么会是一个只有百舰的小V。自此，我便不再看新科娘了，转而天天晚上点进510看看是不是在播，以至于现在已经养成了生物钟，能够感知到`6：56`左右的时间，便点进直播间去看直播。

P.S. 哔哩哔哩直播间510[阿梓从小就很可爱](https://live.bilibili.com/510)看到的可以点一点关注看一看直播，真的很可爱，红豆泥阿里嘎多！

-- 11月更新

发现没附图，所以附一下。

![](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/QQ20220406-0.jpg)

-- 12月更新：

破防了家人们，阿梓生日直播我`6：56`就在直播间守着了，赶着第一波的抽奖(因为人少)，结果我没抽中，反而被舍友随手一点抽中了，我真的不能接受啊。

![](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/QQ20211226-0.jpg)

反转了，舍友后面又送给我了，嘿嘿嘿🤤。

## 结语

感谢你能有耐心来看本废物的这篇流水账文章，我虽然平日自嘲为废物带学生，但是真的到了该拼一枪的时候还是会去稍微的努力一下的，正所谓"宁可身冷，不可心冷；宁可人穷，不可志穷"。再高耸的山峰，如若自己在山脚便退却，便永世不得参得一览众山小的美貌了。

我停更的这两个月都在干什么

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

## 前言

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

## 起因

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行，是不是很爽~