141. Linked List Cycle

使用快慢指针，快指针总是比慢指针多走一步，若有环，两个指针会在环内相遇。时间复杂度 O(n)，空间复杂度 O(1)。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def hasCycle(self, head):
	"""
	:type head: ListNode
	:rtype: bool
	"""
	fast = slow = head
	while(fast and fast.next):
	    fast = fast.next.next
	    slow = slow.next
	    if fast == slow:
		return True
	return False

Python 中的 MRO(Method Resolution Order)

这里只讨论新式类的 MRO ，采用了 C3算法。

几个定义：

• C1 C2 ... CN 代表类的列表 [C1, C2, ... , CN]
• head = C1 , head 代表列表的第一个元素，剩余的用 tail = C2 ... CN 表示
• C + (C1 C2 ... CN) = C C1 C2 ... CN 代表列表相加 [C] + [C1, C2, ... ,CN]

类 C 的线行化 L(C) 是类 C，再加上它的各个父类的线性化与各个父类形成列表的唯一合并的结果。父类列表作为合并过程的最后实参，保持了直接父类的本地前趋序。 即 L[C(B1 ... BN)] = C + merge(L[B1] ... L[BN], B1 ... BN) ，如果 C 是 object ，没有父类，那么 L(object)=object ， 合并（merge）的计算规则如下：

• 先取第一个列表的 head 即 L[B1][0] ，如果 head 不在其他列表的 tail 中，那么就将其加到 C 的线性化 中，并从 merge 的列表中都移除，否则，跳过此列表，检查下一个列表。
• 重复上一步骤，直到移除所有类或者抛错

单继承比较简单：L[C(B)] = C + merge(L[B],B) = C + L[B]

看一下多继承

>>> O = object
>>> class F(O): pass
>>> class E(O): pass
>>> class D(O): pass
>>> class C(D,F): pass
>>> class B(D,E): pass
>>> class A(B,C): pass

O,D,E 和 F 的线性化:

L[O] = O
L[D] = D O
L[E] = E O
L[F] = F O

那么 B 和 C 的线性化可以这么计算：

L[B] = B + merge(DO, EO, DE)
L[B] =  B D E O

L[C] = C + merge(DO,FO,DF)
     = C + D + merge(O,FO,F)
     = C + D + F + merge(O,O)
     = C D F O

A 的线性化计算：

L[A] = A + merge(BDEO,CDFO,BC)
     = A + B + merge(DEO,CDFO,C)
     = A + B + C + merge(DEO,DFO)
     = A + B + C + D + merge(EO,FO)
     = A + B + C + D + E + merge(O,FO)
     = A + B + C + D + E + F + merge(O,O)
     = A B C D E F O

检验下：

>>> A.mro()
[<class '__main__.A'>, <class '__main__.B'>, <class '__main__.C'>, <class '__main__.D'>, <class '__main__.E'>, <class '__main__.F'>, <type 'object'>]

• 推荐一个录屏软件 GIF Brewery , 可以生成 gif，随意拖拽位置和调节大小，并可以压缩 gif 的大小，可以在写文章时对于一些动态过程使用 gif 记录
• org mode 插入引用 <q + tab , 保留换行 <v + tab ，文字居中 <c + tab

本周想谈一下*做技术减法* 。

当然这里的减法，不是指去放弃某项技术，而是指在学习技术的过程中，如何做到更好地对量（质量和数量）的控制。前听过一个知乎 live，谈到读书数量的问题，具体的 描述我记不太清了，大体的意思是一类知识的体系就像一个一棵大树，而不是网状的，只需要把关注点放在核心人物和书籍上系统地学习即可。在了解一门技术或某个知识时， 往往在搜集过程中会汇集了许多的文档、书籍或是博客，有时候会陷入一个怪圈，觉得收集地越全面，就能学的更好，导致后面反而被过多的干扰，反而没有一个是系统地学习。 所以我们可以选取1-2个资源做对比，系统地、完整地去学习，再对这个领域有了全面认识后，那么再去扩展的时候，对于共通的部分就能更好地理解，也更容易发现差异点， 反而会加快学习的速度。

好好吃透一个人参果