LeetCode Contest 49

这次比赛对python不友好啊,第三题在比赛的时候一直TLE,比赛结束后用C++实现同样的算法就过了😭

第一题Longest Continuous Increasing Subsequence

给定一个数组,找出连续严格递增子数组的最大长度。

扫描一遍数组即可:如果nums[i], nums[i+1], ..., nums[j-1]是当前最长严格递增子数组,下次扫描的时候可以直接从j开始。

class Solution(object):
    def findLengthOfLCIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ans = i = 0
        while i < len(nums):
            j = i + 1
            while j < len(nums) and nums[j] > nums[j-1]:
                j += 1
            ans = max(ans, j-i)
            i = j
        return ans

Read More

LeetCode Contest 48

这次比赛有点简单的样子。

第一题Second Minimum Node In a 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 findSecondMinimumValue(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        nums = set()
        def dfs(root):
            if not root:
                return
            nums.add(root.val)
            dfs(root.left)
            dfs(root.right)
        dfs(root)
        return -1 if len(nums)<2 else sorted(list(nums))[1]

Read More

LeetCode Contest 47

这次比赛做完四道题了 😊

第一题Non-decreasing Array

给定一个数组,问是否可以最多修改一个元素,使得整个数组非递降。

我是首先找出第一个i,满足nums[i] < nums[i-1]。这样我们必须要修改i或者i-1的位置,只要分别检查修改这两个位置是否可以得到一个非递降数组就行。因为两个元素相等也是非递降,所以修改一个位置可以等价于将那个位置的数字去除。

class Solution(object):
    def checkPossibility(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        def check(i):
            if i >= len(nums):
                return True
            temp = [nums[j] for j in xrange(len(nums)) if j != i]
            return all(temp[j]>=temp[j-1] for j in xrange(1, len(temp)))
        i = 1
        while i < len(nums) and nums[i] >= nums[i-1]:
            i += 1
        return check(i) or check(i-1)

Read More

意志力

今天早上读完了鲍迈斯特的《意志力》。有趣的是,能看完这本书也是一种意志力的运用吧。

自我损耗造成的影响是双重的:一方面意志力减弱了,另外一方面渴望变强了。

“自我损耗”是作者以及书中提到的研究者在做实验的时候常用的手段。这也有警醒的意味:意志力减弱的时候,渴望还会变强!

面临一个让他们产生内心冲突(一方面非常想要,一方面真不该要)的新诱惑,如果他们已经挡住了之前的诱惑,特别是如果上个诱惑过去没多久新诱惑就来了,那么他们更容易屈服。

1.你的意志力是有限的,使用就会消耗。 2.你从同一账户提取意志力用于各种不同任务。

我们可以把意志力的运用分为四大类,控制思维,控制情绪,控制冲动,控制表现。

Read More

LeetCode Contest 45

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

第一题Judge Route Circle

给定一个只含R(右),L(左),U(上)和D(下)的字符串表示移动方向,问是否能回到出发点。

简单的统计。

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']

Read More

Pelican Signals

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

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

signals.initialized.send(pelican)

Read More

LeetCode Contest 44

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

第一题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

Read More

LeetCode Contest 43

感觉这次比赛除第一题之外都是策略/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

Read More

LeetCode Contest 42

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

第一题Set Mismatch

题目大意:给定一个长度为n数值在1到n之间的数组。已知其中一个数字出现一个,另一个数字没有出现。找出这两个数字。

简单的统计。

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]]

Read More

Lambda Calculus

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: ()

Read More