ARTS - Week 2

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种十分相似类型的设计模式之后，我突然明白了一个道理，在学习设计模式的道路上，我一直都在纠结于“形”而不是“神”。

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

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

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

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

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