ARTS - Week 2

用户头像
Khirye
关注
发布于: 2020 年 06 月 04 日

Algorithm

LeetCode 239 :Sliding Window Maximum

本身这道题是非常easy的一道题,但是它是hard难度的,就知道肯定不一般,因为它要求O(n)复杂度内的求解。

正常能想到基本思路是:维护一个size为k的大顶堆,每次移动窗口,需要一次从堆中移除元素和一次堆中元素添加的操作。取最大值的操作是O(1)时间复杂度。所以整个过程下来是O(nlogk).时间复杂度是不达标的。

那么这道题的具体解的思路是:采用双向队列Deque,队列存放数组的下标,这里要注意,存的是数组的下标而不是数组的值,主要目的是用下标来表示一个数的“年龄”。数据结构确定下来之后,每一次的窗口的移动,要做两个操作,用i表示当前下标,k表示窗口的大小:

  1. 取队列的head跟i-k比较,head小于i-k则说明最左边的元素太老了,要移出窗口

  2. 从tail开始遍历,剔除Deque中所有比当前值小的下标。

经过这一轮操作,双向队列的head值就一定是窗口的最大值。

相对于维护一个大顶堆,维护这个双向队列的平均时间复杂度接近常数级。所以总的时间复杂度趋近于O(n)



Review

来自的hackernoon网站的 Why I love Java

这一周看了好几篇文章,并没有找到值得分享的优秀的文章。这篇Why I love Java质量非常差,之所以还拿出来说,是因为我想分享一个观点:来自《三体》里面的一句话——无知和弱小重来不是生存的障碍,傲慢才是。

当我看到这篇文章时,他的标题吸引了我。说实话,从我毕业以来,看到的都是说Java不好的文章,很少看到挺Java的文章(尽管Java的市场占有率依然巨高不下)。所以我以为这个作者必有高论。

然而这篇文章通篇都在展示Kotlin的语法,展示Kotlin从语法上解决的一些Java不太行的问题。最后却得出了一个结论:Kotlin不行。。。因为他觉得Kotlin的语法不适合人类理解语言的习惯。。。

其实我个人一直很反感语言间的优劣争论,尤其是一些对其他语言仅仅尝试了一下就下结论的文章。这种傲慢对于个人的提升毫无益处。



Tips

来自日常工作重构代码过程中的一个小tip。用git diff验证测试结果。

我们都知道,重构代码时最大的保障就是单元测试。然而现实很骨感,如果你身边有重构意识的同事并不多,而你又想要做一些不一样的东西——尝试重构。那么你面临的可能是一个个超过几百行代码的Function,以及一个个返回数据结构超长的接口。但是你很有勇气,依然决定小步快跑,一点一点的重构它。但是面对这样的代码,你实在难以补充单元测试。只能依靠Postman模拟调用,比较重构前和重构后接口的返回结果。然后两次接口的返回又是巨长无比的JSON,难以用肉眼分辨差异。简单地利用git,就可以完美的解决这个问题。

  1. 初始化一个本地仓库,新建一个文件test.txt

  2. 将重构前的接口返回JSON写入test.txt中并commit

  3. 将test.txt清空,然后写入重构后接口的返回JSON。运行git diff命令,轻松对比两次测试结果



Share

来自王争的《设计模式之美》中的适配器模式:代理、适配器、桥接、装饰,这四个模式有何区别?

通过连续的学习了4种十分相似类型的设计模式之后,我突然明白了一个道理,在学习设计模式的道路上,我一直都在纠结于“形”而不是“神”。

我总是在想,抽象工厂模式的代码要怎么写,工厂模式的代码应该怎么写。。等等;今天我突然顿悟,设计模式重要的不是“代码的样子”,而是“思想的样子”——它是一种能解决某个特定问题的方法或者套路。每一个设计模式的背后都是一种思想——通常是能够通过代码优雅实现出来的。我们不应该拘泥于如何写出这样“优雅的代码”,而是理解背后的思想,以及解决问题的思路

  • 代理模式是为了解决在不改变原来的接口情况下,控制它的访问,而非增强它的功能

  • 桥接模式的目的是将接口部分和实现部分分离,从而让它们可以较为容易、也相对独立地加以改变

  • 装饰器模式是为了在不改变原有接口的情况下,增强它的功能,同时允许多个子功能嵌套使用,灵活组合

  • 适配器模式是为了补救!它产生的新接口和旧的接口不一样,是为了统一一些功能类似,由于历史原因无法修改的接口。



发布于: 2020 年 06 月 04 日 阅读数: 63
用户头像

Khirye

关注

还未添加个人签名 2018.03.31 加入

还未添加个人简介

评论

发布
暂无评论
ARTS - Week 2