ARTS 第 44 周

每周完成一个 ARTS:
Algorithm: 每周至少做一个 LeetCode 的算法题
Review: 阅读并点评至少一篇英文技术文章
Tips: 学习至少一个技术技巧
Share: 分享一篇有观点和思考的技术文章

Contents

Algorithm

217. Contains Duplicate

题目:217. Contains Duplicate

难度:Easy

题意:Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

示例 1:

Input: [1,2,3,1]
Output: true

示例 2:

Input: [1,2,3,4]
Output: false

示例 3:

Input: [1,1,1,3,3,4,3,2,4,2]
Output: true

解法 1:

首先这道题也是非常的简单,我们最容易想到的办法就是使用两个 for loop 遍历这个数组,看是否存在有两个相等的元素,如果有,那么就返回 True,否则遍历完毕返回 False。但是这样的解法时间复杂度为 $O(n^2)$,非常不建议使用。

解法 2:

第二种解法如果稍微有一点经验的同学都能够想到,就是使用空间换时间的思路:创建一个新的字典(或者数组),遍历 nums,如果新的字典中存在遍历到的元素,那么返回 True,否则将这个元素添加到新的字典中去。时间复杂度和空间复杂度都是 $O(n)$。代码很简单,就不放上来了。

解法 3:

这个方法思路比较独特:先将 nums 进行排序,再遍历,如果当前元素和下一个元素相同,那么返回 True,否则遍历完毕返回 False

代码:

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        nums.sort()
        for i in range(len(nums) - 1):
            if nums[i] == nums[i + 1]:
                return True
        return False

时间复杂度 $O(n\log{n})$,因为 sort() 的时间复杂度为 $O(n\log{n})$,大于遍历的 $O(n)$,取较大的那一个;空间复杂度 $O(1)$。

解法 4:

这个解法是利用了 Python 中的函数 set(),如果 set(nums) 的长度和 nums 原本的长度不同则说明有重复元素,返回 True,否则返回 False。这个方法不提倡,因为练习的时候应该尽量减少对某种语言的特性的依赖,否则练习也就失去了本身的意义。

Review

Programming Biology: Read (r), Write (w), Execute (x)

本周阅读的文章来自于 a16z,经由 Dailyio 推荐,《Programming Biology: Read (r), Write (w), Execute (x)》。

没有人怀疑生物科技是下一个技术热点,但我们如何去衡量生物技术的发展水平,以及如何去定义某家生物创业公司或某个产品的技术价值,还需要一个基本标准。a16z 这篇文章给出了一个分析框架,利用计算机领域的基本概念,将「读」、「写」、「执行」嫁接在生物技术领域,可以帮助我们快速确定生物技术的思维框架。

文章从「读」、「写」和「执行」三个角度,审视了当前生物科技的发展和趋势:

文章结尾的点题非常有趣:

Medicine is becoming programmable; and biology is eating the world.

医学已经能够编程化了,生物学正在蚕食这个世界,引用了 a16z 的 slogan:

Software Is Eating the World.

Tips

分享一本针对 Mac 的程序员用户的效率提升手册

如题,地址如下:EffectiveMac

Share

关于邮件订阅及推荐

今天收到了订阅的 Dailyio 作者 Saipo 先生的邮件,起因是他的在 Dailyio 的「iPad Power User」栏目中推荐了两个 Markdown 的编辑服务,我都有尝试过,但都不十分令我满意,于是向他推荐了 mdnice 这个我上周在打卡中推荐过的服务。Saipo 先生体验过之后觉得相当满意,特地发邮件来感谢,并表示会在下周的「iPad Power User」中进行推荐。

(有时候人与人的连接就是这么简单,现代科技的快速发展让我们可以近乎实时地连接上任何我们想要连接的人,前提是不要给自己设限。)

关于邮件订阅和 RSS,我个人虽然是微信的重度用户,但基于国内的网络环境,以及个人进行文件管理的方便程度,我还是偏向于使用邮件或者 RSS 的方式来订阅自己想看的内容。一方面可以避免陷入智能推荐造成的「信息深井」之中,另一方面这种技术壁垒稍高一点的方式能降低我卷入流量生意的概率。

这周给大家推荐几个我常读的几个邮件订阅源,其中大部分都不是技术类订阅,而是更多地注重于开拓眼界、了解世界上都在发生什么、其他人都在做什么看什么以及想什么:

  1. Dailyio
  2. 好奇心日报【大公司头条】
  3. 狗熊有话说
  4. Wait but why
  5. Recomendo
  6. News From the Future
  7. a16z
  8. The Profile

另外,推荐大家使用「Spark」(不是「Apache Spark」 (~ ̄▽ ̄)~)这个第三方的邮件客户端,全平台通用。