Leetcode Contest 38

2017-06-25

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

第一题Maximum Product of Three Numbers

给定一个长度不小于3的数组，问任选三个数得到的最大乘积是多少。

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

第一个数 X 第二个数 X 第三个数
倒数第一个数 X 倒数第二个数 X 倒数第三个数
第一个数 X 倒数第一个数 X 倒数第二个数
第一个数 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])

Rademacher functions

2017-06-22

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.

Definition 1. Let \(n \ge 1\) be an integer. The \(n\)-th Rademacher function \(r_n: [0, 1] \to \{-1,1\}\) is defined to be \[r_n(x) = 1 - 2a_n(x).\]

Lüroth expansion

2017-06-20

This post is my note for What is…? seminar on Lüroth expansion.

Definition 1. A Lüroth expansion of a real number \(x \in (0, 1]\) is a (possibly) infinite sequence \((a_1, a_2, \cdots, a_n, \cdots)\) with \(a_n \in \N\) and \(a_n \ge 2\) for all \(n \ge 1\) such that \[\begin{equation} x = \frac{1}{a_1} + \frac{1}{a_1(a_1-1)a_2} + \cdots + \frac{1}{a_1(a_1-1)\cdots a_{n-1}(a_{n-1}-1)a_n} + \cdots \end{equation}\]

By abuse of notation, we will something write the right hand side of Definition 1 as \((a_1, a_2, \cdots, a_n, \cdots)\).

Given a system of representation of real numbers in \((0, 1]\), we need to determine whether these representations are 1 to 1 corresponding the numbers in \((0, 1]\). Aslo we should study the (Lüroth) shift map: \[\begin{equation} T: (a_1, a_2, \cdots, a_n, \cdots) \mapsto (a_2, \cdots, a_n, \cdots). \label{20170620-2} \end{equation}\]

Raspberry Pi Zero W无屏设置

2017-06-19

我最近入手了一个Raspberry Pi Zero W，作为平时消遣的一个小玩具。因为我主要是想在它上面运行一些小程序，所以我希望将它设置为最简单的服务器，然后通过ssh来访问。这篇文章记录了我从网上搜来的设置步骤，方便下次设置。

制作SD启动盘

首先说明一下：我的系统是Mac OSX。在制作SD启动盘过程中，我们需要修改启动盘的内容，Mac OSX是不支持启动盘的格式的，所以我们需要借助其他途径。我是用VitualBox的Ubuntu来修改启动盘的内容。

第一步：下载raspbian lite，解压得到一个后缀名为img的镜像文件。我得到的是：2017-04-10-raspbian-jessie-lite.img。

Leetcode Contest 37

2017-06-18

第一题Maximum Distance in Arrays

给定一个包含数组的数组，每个数组都已经递增排序。我们要做的是从两个数组中各选一个数，使得这两个数的差的绝对值最大。问这个最大的值是多少？

对于第i数组中，取出最大值a，最小值b，然后将(a, i)和(b, i)放进一个数组m里。将数组m按照第一个分量排序，那么对我们有用的只是数组m前面两个元素和后面两个元素。如果第一个元素和最后一个元素来自不一样的数组（第二个分量不一样），那么答案就是这两个元素的第一个分量的差。否则，我们要比较两种情况：第一个元素与倒数第二个元素，第二个元素与最后一个元素。

class Solution(object):
    def maxDistance(self, arrays):
        """
        :type arrays: List[List[int]]
        :rtype: int
        """
        m = []
        for i, a in enumerate(arrays):
            m.append((a[0], i))
            m.append((a[-1], i))
        m.sort(key=lambda x: x[0])
        if m[0][1]!=m[-1][1]:
            return m[-1][0]-m[0][0]
        return max(m[-2][0]-m[0][0], m[-1][0]-m[1][0])

Leetcode Contest 35

2017-06-03

第一题Can Place Flowers

给定一个01数组代表一排花盆，0代表是可以种花，1代表不可以。种花的时候我们要确保左右两边的花盆是空的。问能不能种n株花。

简单的贪心。

class Solution(object):
    def canPlaceFlowers(self, flowerbed, n):
        """
        :type flowerbed: List[int]
        :type n: int
        :rtype: bool
        """
        cnt = 0
        for i in xrange(len(flowerbed)):
            if flowerbed[i] == 1:
                continue
            if i-1>=0 and flowerbed[i-1]==1:
                continue
            if i+1<len(flowerbed) and flowerbed[i+1]==1:
                continue
            flowerbed[i] = 1
            cnt += 1
        return cnt>=n

Leetcode Contest 33

2017-05-20

就着Gin的酒劲，我还能一次不WA的过了这次比赛哈哈。

第一题Longest Harmonious Subsequence

给定一个数组，找出长度最长的子数组，使得其最大值与最小值恰好相差1，返回最大长度。

既然最大值与最小值恰好相差1，那么此子数组必定恰好有两个不一样的元素。我们只要统计每个元素出现的次数，然后枚举找出相邻两个元素出现次数之和的最大值就好。

class Solution(object):
    def findLHS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        cnt = {}
        for n in nums:
            cnt[n] = cnt.get(n, 0) + 1
        ans = 0
        for k, v in cnt.items():
            if k-1 in cnt:
                ans = max(ans, v+cnt[k-1])
            if k+1 in cnt:
                ans = max(ans, v+cnt[k+1])
        return ans

Leetcode Contest 32

2017-05-13

比赛链接

第一题Shortest Unsorted Continuous Subarray

给定一个数组，求其中最短的连续子数组长度，使得对该子数组排序就能完成对整个数组的排序。

首先将数组排好序，然后看排好的数组与原来的数组之间的差异。

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

编写Hexo插件让主页显示特定的文章

2017-05-11

今年三月份我在hostgator买的虚拟主机到期了，衡量几番二月就从wordpress迁到了Hexo。从这三个月左右的使用来看，Hexo让我挺满意的。一方面，它简洁且容易使用；另一方面它又给予用户很大的修改空间。奇怪的是，网上几乎没有编写Hexo插件的教程，以至于最近我折腾了好久才能写出可用的插件来让Hexo生成我预期的网页效果。这篇文章记录我编写Hexo插件的方法，希望对后来者有帮助。

首先描述一下我想要做的事情。最近一直参加Leetcode上面的比赛，而且每次参加之后都会写篇文章记录自己的做法，所以主页就被这些文章占领了。我希望主页只显示最新一篇关于Leetcode的文章。同时，我希望能有一个类似主页的页面，该页面是要列出所有关于Leetcode比赛的文章。总结说一下，我要做的事情是：

(I) 让主页只显示特定文章（或者说过滤掉特定文章）。

(II) 建立一个页面只显示特定文章。

Leetcode Contest 31

2017-05-06

这次比赛简单。

第一题Distribute Candies

给定一个长度为偶数的数组，将所有数分成长度一样的两堆，求其中一堆不一样数字最多的数目。

class Solution(object):
    def distributeCandies(self, candies):
        """
        :type candies: List[int]
        :rtype: int
        """
        kind = set()
        for c in candies:
            kind.add(c)
        n = len(candies)/2
        if (n<=len(kind)):
            return n
        else:
            return len(kind)

Previous 1 ... 6 7 8 9 10 ... 12 Next