20180722_ARTS_week04

ARTS 是耗子哥（左耳朵耗子）发起的一个活动。

A -- Algorithm 每周一道算法题

R -- Review 每周阅读并点评一篇英文技术文章

T -- Tip 每周学习一个技术技巧

S -- Share 每周分享一篇技术文章

坚持一年 :-)

这是我的第三周 ARTS

Algorithm

/**
 * https://leetcode.com/problems/median-of-two-sorted-arrays/description/
 * 
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
// 2080 / 2080 test cases passed.
// Runtime: 128 ms  56.85%
var findMedianSortedArrays = function (nums1, nums2) {
    nums1 = nums1.concat(nums2)
    nums1.sort(function(a,b){  // V8 下 平均时间复杂度 O(nlogn)
        return a -b;
    })

    var len = nums1.length
    if (len % 2 == 0) {
        return ( nums1[parseInt(len / 2)] + nums1[parseInt(len / 2)-1] ) / 2
    } else {
        return nums1[parseInt(len/2)]
    }
};

console.log( findMedianSortedArrays([1,3], [2]) )
console.log( findMedianSortedArrays([1,2], [3,4]) )
console.log(findMedianSortedArrays([1], [2, 3, 4, 5, 6, 7, 8, 9, 10]))

这题寻找两个已经排好序的数组的中值，一开始思路比较简单，两个数组合一起，然后排个序就很容易找到中值了。

但是这个实现没有很好的利用两个数组都已经是排好序的这个条件，重新使用 JavaScript 的 sort 方法又排了一次序，这个方法在不同浏览器下实现不一样，这里就参考 Google Chrome 的 V8 内核，V8 内核对 sort 方法的实现是插入 排序 和快速排序，大于 10 个数的是快速排序，的平均复杂度是 O(nlogn)。关于各个浏览器对 sort 的实现，可以参考 https://segmentfault.com/a/1190000010648740

可以看到 2080 个 test case 跑了 128 ms，打败 56.85% 的实现。恩，这不是一个比较好的实现方式。

因为给到的两个数组都是已经排好序的，其实可以做个循环，两个数组都循环到，然后按序放到新数组里面，这样时间复杂度是 O(m+n)

// 2080 / 2080 test cases passed.
// Runtime: 112 ms   93%
var findMedianSortedArrays = function (nums1, nums2) {
    var mergeList = []

    var i=0, j=0;
    while( i<nums1.length && j<nums2.length){

        if(nums1[i] < nums2[i]) {
            mergeList.push(nums1.shift())
        } else {
            mergeList.push(nums2.shift())
        }
    }

    if (nums1.length > 0) {
        mergeList = mergeList.concat(nums1)
    }
    if (nums2.length > 0) {
        mergeList = mergeList.concat(nums2)
    }

    var len = mergeList.length
    if (len % 2 == 0) {
        return (mergeList[parseInt(len / 2)] + mergeList[parseInt(len / 2) - 1]) / 2
    } else {
        return mergeList[parseInt(len / 2)]
    }
};

console.log( findMedianSortedArrays([1,3], [2]) )
console.log( findMedianSortedArrays([1,2], [3,4]) )
console.log(findMedianSortedArrays([1], [2, 3, 4, 5, 6, 7, 8, 9, 10]))

这个实现，2080 个 test case 跑了 112ms 打败了 93% 的实现。

Review

https://medium.com/the-mission/the-5-hour-rule-if-youre-not-spending-5-hours-per-week-learning-you-re-being-irresponsible-791c3f18f5e6

这篇文章前面大段主要表达了【知识是这个时代的财富】，我想这个观点在碎片化学习，终生学习的大背景下应该没有反对吧，如果你还没认识到这点，建议可以细细读一下这篇文章。作者提倡每周至少学习 5 个小时。

文中介绍了 6 种技巧来掌握新的知识经济：

1. 在正确的时间识别有价值的知识。这个比较好理解，很多东西如果不讲时点，就是耍流氓。而什么事有价值的知识呢？我觉得可以从趋势来理解，就拿现在前端的发展来说，前后端分离，ES6，以 Vue/Reac/Angular 为首的新一代前端框架肯定是未来的趋势，所以这个时候如果你还在专研以前的 ExtJs/Sencha 之类的可能就不是很合适。还有一点就是这个知识大爆炸的时代，要注意甄别筛选。
2. 学习和掌握新知识要快。这就要在日常保持学习，有一个敏感度。
3. 学到的东西与别人交流。除了面对面的交流，写写博客，公众号，做一些记录沉淀都是不错的交流，写博客的时候，也是与自己交流的过程，也可能激发新的认识。
4. 把知识变成钱和价值。这是验证学习的东西价值是否被挖掘的一种方法，一个有价值的东西应该是经济上能体现的，比如工作加薪，知识付费，或者一些名声上的影响力。毕竟，生活除了诗和远方，还有眼前的苟且。
5. 学习如何在财务上投资，学习如何获得高回报。赚钱与理财是生活的两面，你不理财财不理你。这里还有一点，作者同时指出可以将理财上的风险管理，对冲，增长率等和知识投资联系在一起，我觉得挺值得思考的。
6. 掌握学习技巧。可能学习能力是比知识更重要或者说更核心的东西。

对于学习，可能很多人会有犯懒的时候，这个是可以理解的，毕竟学习就是逆人性的事情，但首先要认识到 要在这个时代幸存和繁荣，我们必须持续学习 ，也有人觉得努力工作，就够了，其实如果每天都做重复的事情，天花板是显而易见的，10000 小时并不是说把重复的东西做上 10000 小时。这就是作者说的 努力工作是工业时代取得成功的方法。努力学习是知识经济取得成功的方法。

最后，作者说了三个开始学习的步骤： 1. 不管多忙，找时间阅读和学习； 2. 利用好找到的时间，不要拖延或者分心； 3. 通过各种技巧提升每小时的学习效果，记住和应用学到的东西。

Don’t be lazy. Don’t make excuses. Just get it done.

Tip

分享一下这周了解的哈希表碰撞进行攻击的原理。

攻击原理: 哈希表是用数组来保存键值对，键值对存放的下标由键的哈希值决定，键的哈希值可以在参数时间内计算出来，这样哈希表插入、查找和删除的时间复杂度为 O(1)，但是这是理想的情况下，真实的情况是，键的哈希值存在冲突碰撞，也就是不同的键的哈希值可能相等，一个好的哈希函数应该是尽可能的减少碰撞。解决冲突碰撞的方法有分为两种：开放地址法和链接法。哈希表一般都采用链接法来解决冲突碰撞，也就是用一个链表来将分配到同一个键的键值对保存起来。

哈希碰撞攻击就是，针对哈希函数的特性，精心构造数据，使所有数据的哈希值相同，当这些数据保存到哈希表中，哈希表就会退化为单链表，哈希表的各种操作的时间复杂度提升一个数量级，因此会消耗大量 CPU 资源，导致系统无法快速响应请求，从而达到拒绝服务攻击（DDos）的目的。

因为哈希表在所有的 Web 应用框架上都有应用，我们对 Web 应用每次发起请求所提交的参数，服务器端都会将其存储在哈希表中供后台代码调用，所以哈希碰撞攻击的攻击方式一般都是通过发送包含大量碰撞键值的参数的 post 请求，来达到攻击的目的。

防护方式: 1. 限制POST请求的参数个数 2. 限制冲突链表的长度

Share

刚好这周看到学习的文章，分享一下我以前写的关于前端的一些思考。

前端的10000小时

如果哪天你看到一个没接触的技术，简单了解之后觉得以后会有很大的发展空间，那就应该多花时间去学，去看。大概 3-4 年前，第一次机缘巧合之下接触了解到 docker 当时觉得这个技术以后一定会火，可惜没有持续了解下去，也是有点遗憾吧。

所以，一定程度上押宝你觉得未来会火的技术，持续了解，学习，会有不错的收获的。

碎碎念

记录一些所思所想，写写科技与人文，写写生活状态，写写读书心得，主要是扯淡和感悟。 欢迎关注，交流。

微信公众号：程序员的诗和远方

公众号ID : MonkeyCoder-Life