这次比赛也是卡在第三题上！😂
机智小伙伴是用状态机做的，非常厉害。

第一题Judge Route Circle

简单的统计。

class Solution(object):
    def judgeCircle(self, moves):
        """
        :type moves: str
        :rtype: bool
        """
        cnt = collections.Counter(moves)
        return cnt['L']==cnt['R'] and cnt['D']==cnt['U']

Pelican的插件系统是使用blinker的signal实现的。Pelican所有可以用的signals可以在signals.py找到。本文的目的是记录这些signals是在Pelican运行中什么时候发出的。

(1) Pelican有一个叫做Pelican的类，含有程序的主体框架。当Pelican的一个实例pelican初始化完成之后（基本设置，加载插件），发出第一个signal。

signals.initialized.send(pelican)

这次比赛很遗憾只能做出三题，没有做出第三题。第三题其实不难，只是比赛的时候脑袋就像面粉加水一团浆糊没有反应过来。

第一题Two Sum IV - Input is a BST

好吧，我是写博客的时候才发现原来输入的是一颗搜索树。题目大概是想让我们快速判定一个数是否在给定的二叉搜索树中吧。我是首先遍历二叉树统计每个数出现的次数，然后枚举每个出现的数a，如果目标值减去a也出现过则返回True。注意要考虑a和目标值减去a是一样的情况。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def findTarget(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: bool
        """
        nums = collections.defaultdict(int)
        def dfs(root):
            if not root:
                return
            n = root.val
            nums[n] += 1
            dfs(root.left)
            dfs(root.right)
        dfs(root)
        for n in nums.keys():
            m = k - n
            if n != m and m in nums:
                return True
            if n == m and nums[n] > 1:
                return True
        return False

感觉这次比赛除第一题之外都是策略/DP题啊。

第一题Find Duplicate Subtrees

我们要对树的结构进行统计，因此这题关键是对树进行编码。可以参考 606. Construct String from Binary Tree。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def findDuplicateSubtrees(self, root):
        """
        :type root: TreeNode
        :rtype: List[TreeNode]
        """
        seen = {}
        def dfs(root):
            if not root:
                return ''
            left = dfs(root.left)
            right = dfs(root.right)
            s = '{}({})({})'.format(root.val, left, right)
            if s not in seen:
                seen[s] = [1, root]
            else:
                seen[s][0] += 1
            return s
        dfs(root)
        ans = []
        for c, node in seen.values():
            if c > 1:
                ans.append(node)
        return ans

今天晚上在朋友家做好饭已经过了比赛时间了，我们是边吃着饭边喝着酒来写代码。牛肉炖土豆是一如既往的美味，新尝试的豆腐煮白菜也很不错。这次朋友买了Habanero，辣味惊人，我是打着喷嚏做菜的😢

第一题Set Mismatch

简单的统计。

class Solution(object):
    def findErrorNums(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        ans = [0, 0, 0]
        cnt = [0] * len(nums)
        for i in nums:
            cnt[i-1] += 1
        for i, c in enumerate(cnt):
            ans[c] = i+1
        return [ans[2], ans[0]]

This post is my note for What is seminar on Lambda Calculus.

Lambda calculus was created by Alonzo Church in the 1930s, and was used by him to solve Entscheidungsproblem in 1936, which is related to Hilbert's tenth problem. In the same year, Alan Turing independently solved Entscheidungsproblem using his invention Turing machine. Shortly after, Turing realized that these two models are actually equivalent as models of computation.

In this note, I will first give the formal definition of lambda expressions. Then with the help of Python, I am going to show how to do Boolean algebra and basic arithmetic using lambda calculus, which to some extend gives an illustration that Turing machine and lambda calculus are equivalent.

Definition

Lambda calculus consists of lambda expressions and operations on them. There are three basic elements in Lambda expression:

1. variables: x, y, z, ...
2. symbols in abstraction: λ and .
3. parentheses for association: ()

我现在用的博客生成软件是Hexo。这个软件可以快速将Markdown格式的文章转成html格式，并且包含发布到github page的工具。Hexo是基于Nodejs，所以某天我就在想有没有一个基于Python的博客生成软件。为什么我会这样想？因为

人生苦短，我用Python。

当然会有基于Python的博客生成软件：Pelican是最为突出的一个。事实上，我很喜欢Pelican！其中一个亮点是它的主题都是基于Jinja，这种简单统一的模版格式让用户很容易设计自己喜欢的主题。出于练手的原因，我将我喜欢的一个Hexo主题maupassant移植到Pelican了。

This post is my note for What is seminar on Cassini Ovals.

Definition

An ellipse is a geometric object formed by locus of points which have fixed sum of distances to two fixes foci.

In the above figure, we can express the definition of ellipses in one simple equation:

for some \(c>0\). What if we change the addition in the above equation to multiplication? This comes the definition of Cassini ovals.

这次比赛我表现得比较差，只能做出第一题和第三题。第四题比赛结束之后很快也写出来了，而第二题确实花了我一个多小时才能想出来。

第一题Maximum Product of Three Numbers

先将数组排序，那么最大值必然在下面四种情况中：

1. 第一个数 X 第二个数 X 第三个数
2. 倒数第一个数 X 倒数第二个数 X 倒数第三个数
3. 第一个数 X 倒数第一个数 X 倒数第二个数
4. 第一个数 X 第二个数 X 倒数第一个数

class Solution(object):
    def maximumProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        return max(nums[0]*nums[1]*nums[2],
                    nums[-1]*nums[-2]*nums[-3],
                    nums[0]*nums[-1]*nums[-2],
                    nums[0]*nums[1]*nums[-1])

This post is my note for What is…? seminar on Rademacher function.

For a real number \(x\) in \([0, 1]\), let \((a_1(x), a_2(x), \cdots, a_n(x), \cdots)\) be its binary representation. That is to say, \[\begin{equation} x = \sum_{n=1}^\infty \frac{a_n(x)}{2^n}. \label{20170623-1} \end{equation}\]

For some \(x\), there might be two possible binary representation. Take \(\frac{1}{2}\) for example, it can be represented as \((1, 0, 0, \cdots)\) or \((0, 1, 1, \cdots)\). In this situation, we always prefer the former representation, in which all terms become \(0\) eventually.