只是一篇白开水文章，用来吐槽我们学校的管理系统的。

## 前言

有人问，马老师发生什么事了？我一看，奥，原来是昨天，有两个年轻人，一个码龄，三年多，一个码龄四年多。他们说：“诶...有一个说是毕设系统有问题，马老师你能不能教教我看”，然后上来就是一个html检索，吭，一个sql注入，一个字典查密码。我说年轻人不讲武德，他忙说对不起，他说他是乱注的。他可不是乱注的，一个“; and 1=1 and 1=2”， 一个“and 0<>(select count(*) from *)”，训练有素，看来是有备而来。这两个年轻人不讲武德，来骗！来偷袭我这外包公司写的管理系统，这好吗？这不好。我劝这位年轻人，耗子尾汁。好好反思。以后不要再犯这样的小聪明。武林要以和为贵，要讲武德，不要搞窝里斗。



## 起因

哈哈哈，开个小玩笑，来讲一下昨天一晚上发现的搞笑事情吧，起初题目公布了，我们就是浏览了一下，但是他这个系统选题没有指导老师，很烦，就打算从`api`来看是否有什么思路找出来。结果这一看直接傻眼了，我滴天哪，这个系统竟然把所有数据都写在了一个`api`里面，这我是真的没想到的，各种隐私数据，导师信息，需求分析，题目类别，id，就连导师密码都写在里面了，不禁令人直呼真牛哇！真牛哇！这都可以的吗，这种程度的程序员都能出来拿工资吗？？现在计算机行业这么不饱和？？

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

起初，我就是把这些数据爬了下来然后提取了一下数据发群里然后就没再管，直到晚上朋友发的一句话才有了下面这些剧情.......

## 快乐的耍网站时间

### 裸写在html里面的js和接口

晚上，有一位朋友`L`说这个网站有bug，可以提前选课。起初我是很好奇的，因为提示的api只有一个校验，云端校验并且没有时间戳相关提交字段，怎么说都没办法绕过检测。然后就有了下面的对话：

> "选课的api和校验的api不是一个啊"
> 
> “???不是，你怎么知道的api地址的"
> 
> “直接根据`id`search一下就能找到了”

我立马根据他所说的去搜索了一下，然后就发现了下面的这段令人哭笑不得的代码：

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

奥，闹了半天这个云端校验就是个幌子，选课代码直接裸写到`html`里面，真有你的啊，青峰软件！到了这时，我才明白，这个网站根本就不是`vue`之类的主流框架写的，而是利用`JQuery`和`Html`粗劣的拼接起来的垃圾平台，甚至`JS`文件都不是引入+混淆，而是直接正大光明的写到文件里面，好家伙！我直接™好家伙！

然后我就先自己选了~

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

### 跨专业选题

根据说明，本专业的人本来只能选本专业的题目的，然而既然选课api被发现了,又发现了参数信息，得知这个选题只要一个`id`就可以选了，那么我能不能拿别的专业题目来请求选课呢？答案竟然是可以的，后台完全没有对于专业进行相关的校验，直接就是可以随便选了，再次惊呼好家伙！

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

### SQL注入问题

既然这个平台都这样了，为什么不再进一步呢，然后！就有了更加惊人的发现，这！个！网！站！居！然！没！有！做！防！注！入！

P.S. 数据库貌似是`mongodb`（待验证）

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

再！次！好！家！伙！

### 弱口令问题+密码加密问题

本来弱口令不算做问题，但是教师的\*\*\*\*\*\*\* (此处保密删除)，这就是很大的问题了。起初发现这个问题是因为在最开始获取数据的时候了解到了密码，查看格式知道是`md5`加密，本来这种加密手段直接弱口令表/彩虹表一查就出来的，然而，这里的规律提示所有老师的\*\*\*\*\*\*的......然后果断尝试`**************`(保密)，就........就成功了！？好家伙，这也可以的吗？

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

### session没有黑名单

这个就是老生常谈了，到了这个地步我已经不指望了。果然，没有黑名单处理，session直接持久化保存，不会被顶掉。`CSRF`攻击防御措施也没有，甚至有时候`session id`都是放在`param`里面的，不得不说外包公司的程序员真的是想象力"天马行空"。

## 结语

根据上面的各种漏洞，我们基本可以做到：

> 利用老师的cookie进行sql注入，达到删库或者shell提权操作，搞垮平台或者直接全部删掉，然后直接溜之大吉不被任何人发现。

吐槽到这，心里已经对这个学校失望透顶了，外包都只能找到这种程度的，这种甚至不该是公司产品，只不过是一个学生的课程设计级别的罢了。不，可能真的是学生作品，外包公司二次外包，三次外包，最后流入到学生手上的又有多少呢，这一层层之间回扣又吃了多少占比呢，我不敢想象。

希望学弟学妹们也要引以为戒，写出来能用的代码很容易，写出来可以用的代码却很难，明白自己这个阶段该学习什么，能有什么竞争力，为自己得到什么利益。

> **天下熙熙皆为利来，天下攘攘皆为利往。**

人总是会为了利益不择手段的，哪怕是骗，抢。

关于学校毕设管理系统的吐槽

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

## 前言

已经有一段时间(两个月)没更新过博客了。上下思索，主要有两个原因：一是开学了，事务变多，无心管理博客相关更新，再加上大四的老狗已经无法再在实验室混日子了，导致我现在碰电脑的时间几乎消失掉了；二是面临考研（其实我是不想考的 但是被父母裹挟 很难受），从早晨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)