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 当时觉得这个技术以后一定会火,可惜没有持续了解下去,也是有点遗憾吧。

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


本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏一个会写诗的程序员的博客

附录B 编程的本质附录B 编程的本质编程的本质N小结编程简史名词纪要参考资料

尼古拉斯·沃斯(Niklaus Wirth,1934年2月15日—),生於于瑞士温特图尔,是瑞士计算机科学家。Pascal语言之父。

923
来自专栏恰同学骚年

[转] Agile Software Development 敏捷软件开发

  敏捷开发是一种软件开发方法,基于迭代和增量开发,通过自组织,跨团队,沟通协作完成开发工作。

1032
来自专栏java一日一条

如何掌握所有的程序语言

很多编程初学者至今还在给我写信请教,问我该学习什么程序语言,怎么学习。由于我知道标题问题的答案,所以总感觉这个问题是如此“低级”,一直没来得及回复 : P 可是...

560
来自专栏高性能服务器开发

从“成都-go-戒炸鸡”的面试题开始说起

今天晚上“高性能服务器开发”QQ群(群号:49114021,有兴趣的读者可以加一下)里面一名叫“成都-go-戒炸鸡”的群友提出了他最近面试的一些面试题,面试题内...

1813
来自专栏佳爷的后花媛

Java编程思想之每天两小时(一)

之前也学过Java,但是因为很少用,所以一直没有当回事,现在想想,那时真是太年轻啊。后来朋友推荐这本Java编程思想给我,刚拿到这本书,被这厚厚的一本惊呆了,里...

1052
来自专栏北京马哥教育

快速掌握一个语言最常用的50%

现在的开发工作要求我们能够快速掌握一门语言。一般来说应对这种挑战有两种态度:其一,粗粗看看语法,就撸起袖子开干,边查Google边学习;其二是花很多时间完整地把...

2879
来自专栏深度学习那些事儿

学习C语言的必备书籍-从入门到精通

不同学校教材不通,大部分书都把C语言的基本内容讲出来了,不推荐谭浩强的C语言书,如果仅仅是当第一本C语言书是可以的。

3464
来自专栏程序人生

[技术] 谈谈Python

昨天的文章收获了不少有价值的回复。不少人发现了一个大bug,那就是「上帝的归上帝,撒旦的归撒旦」。囧死我了。脑手不同步这病怎么治啊~以后我写完文章争取好好复查一...

3725
来自专栏java架构师

设计模式学习笔记之桥接模式

这个模式在看书时,一直没想到更好的应用场景,由此感慨一下《设计模式之禅》这本书, 通过这本书,的确对各种模式有了个比较清晰的理解,甚至对模式的结构也能很明确。也...

3597
来自专栏高性能服务器开发

去BAT,你应该要看一看的面试经验总结

说下我的面试经验吧,都是亲身经历,不喜勿喷: 我去年12月份从上一家公司离职,一直到今年3月份,基本上都在面试中度过来的。 先交代下背景:坐标上海,做技术开发,...

3984

扫码关注云+社区