Leetcode Contest 28

2017-04-15

今晚吃的是烤鱼以及手撕鸡。

这次的比赛让我开始怀疑自己的智商了。

第一题Student Attendance Record I

题目大意：给定一个表示只含A、L和P的字符串，问字符串是否满足以下条件：不含多于1个的A或者不含有长度大于2的连续L子字符串。

简单的字符串处理。

class Solution(object):
    def checkRecord(self, s):
        """
        :type s: str
        :rtype: bool
        """
        a = 0
        for c in s:
            if c == 'A':
                a += 1
        if a > 1:
            return False
        if s.find('LLL') != -1:
            return False
        return True

Read More

Leetcode Contest 27

2017-04-08

今晚肉特别多：红烧羊肉，焖排骨，手撕鸡和罗非鱼。

第一题Reverse Words in a String III

题目大意：给定一个句子，将其中所有单词逆序。
class Solution(object):
    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str
        """
        lst = s.split(' ')
        for i in xrange(len(lst)):
            if lst[i] == '':
                continue
            lst[i] = ''.join(reversed(lst[i]))
        return ' '.join(lst)

Read More

Cabaret

2017-04-02

昨天晚上并没有参加每周一次的Leetcode比赛，而是跟朋友去看Cabaret了。按照惯例要说一下吃了什么好吃的：我们去了Columbus Fish Market吃海鲜去了。前菜有fresh oysters与crab & shrimp dumplings，主菜有rainbow trout, lobster & shrimp stuffed cod和sea scallops。饭后甜点是key lime pie！这家的海鲜做法有点像广东那边，味道很清淡，试图突显海鲜的味道。我感觉最好吃的是前菜中的fresh oysters。上桌的时候，生蚝是平放在一大碗冰之上的，其纹理很清晰，也正是这种黑白分明显示出了生蚝的新鲜。可惜的是他们家的酱料相对之下粗糙简单，只有一碟类似番茄酱的酱料和一碟油，并没有蒜蓉之类可以提鲜的调料。还好的是生蚝本身已经够新鲜了，猛地一吸，生蚝的鲜甜立马在舌尖绽放，让人十分快意。

Cabaret是一部音乐剧，一部充满黄段子的音乐剧。Cabaret一开幕我就明白朋友路上说的少儿不宜是什么意思了。虽然我并不能完全明白剧中的对话（估计错过了好多黄段子 😛 ），但是剧中的大致剧情还是明白的。这里我就不剧透了，有兴趣的朋友也很容易在网上找到简介。一开始根据剧中反映的性泛滥以及对金钱的崇拜，我还以为是说战后经济大低谷时期的事情。后来剧中出现了纳粹红袖章我才意识到自己搞错了。原来剧中的人们正活着1928～1930期间，正是纳粹主义开始猖獗的时候。

Read More

Leetcode Contest 25

2017-03-26

昨天晚上有红烧牛排骨，白灼罗非鱼，烤翅和我喜欢的草莓蛋糕。

这次比赛我表现比较弱，只做出了前三道，而且第三道还WA了5次。最后一题是很有趣的DP，可惜比赛的时候做不出来。

第一题Perfect Number

题目大意：给定一个整数num，判断是否为完美数。如果num是一个正整数，并且其所有正因子（除num本身之外）之和等于本身，那么num是一个完美数。

思路：关键的观察是正因子是成对出现的，例如d是num的一个因子，那么num/d也是num的一个因子，所以我们只要搜索到\(\sqrt{num}\)就行。

class Solution(object):
    def checkPerfectNumber(self, num):
        """
        :type num: int
        :rtype: bool
        """
        if num <= 1:
            return False

        s = 1
        for i in xrange(2, int(num**(0.5))+1):
            if num % i == 0:
                s += i
                if i != num/i:
                    s += num/i
        return s == num

Read More

Leetcode Contest 24

2017-03-18

今晚吃的是韩式烧烤：羊肉和豆腐。

这次比赛有四题，题目都比较基础，可惜打错了一个变量名字WA了一次。

第一题Diameter of Binary Tree

题目大意：一棵树的直径定义为树中最长路径的长度。给定一棵二叉树，求树的直径。

递归想法：对于每个树节点，计算经过该树节点最长路径的长度。只要修改求每个节点高度的程序就行。先算当前左子树的高度l和右子树的高度r，那么以该经过该节点最长路径的长度就是l+r+1，然后返回该节点的高度max(l, r)+1

# 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 diameterOfBinaryTree(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        def height(root, ans):
            if not root:
                return 0
            l = height(root.left, ans)
            r = height(root.right, ans)
            ans[0] = max(ans[0], l+r+1)
            return max(l, r)+1

        ans = [0]
        height(root, ans)
        return ans[0]-1

Read More

Leetcode Contest 23

2017-03-11

今晚有手撕鸡，玉米鸡汤，红烧牛排骨和金鲳鱼。本来还准备了要做个豆豉炒苦瓜的，但是那手撕鸡实在太大了，所以就苦瓜没有必要做了。这手撕鸡很好吃：先是用鸡熬两个小时做鸡汤，然后将鸡过冷水去骨撕条，在鸡肉上放上辣椒面与白芝麻并浇以热油，最后加上些许醋拌匀即可。

这次比赛比较简单，但是还是WA了两次了，顺带吐槽一下自己写代码的速度。

第一题Reverse String II

题目大意：给定一个字符串和一个数k，对于字符串的每2k长度的子字符串，逆序前k个字符串。

没什么好说的，就直接干就好：首先将字符串按长度为2k分块，然后处理每一个分块。

class Solution(object):
    def reverseStr(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: str
        """
        lst = []
        for i in xrange(0, len(s), 2*k):
            lst.append(s[i:i+2*k])
        for i, s in enumerate(lst):
            lst[i] = s[:k][::-1]+s[k:]
        return ''.join(lst)

Read More

Leetcode Contest 22

2017-03-04

今晚吃得有点撑：排骨汤，花池鱼，红烧羊肉和炒青菜。

除了第一题WA了一次之外，其他三题都一次过了！

第一题K-diff Pairs in an Array。

题目大意：给定一个数组和一个数k，求数组中所有不同的差值绝对值为k的二元对的数目。

思路比较简单：首先用哈希表统计所有数出现的频率。对于k＝0的情况，我们返回所有出现次数大于1的数的数目，对于k>0的情况，我们只要统计所有n+k也出现的数n的数目。对于k<0的情况，直接返回0。我第一次提交忘记考虑k<0的情况了。

class Solution(object):
    def findPairs(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        if k < 0:
            return 0
        ans = 0
        d = {}
        for n in nums:
            d[n] = d.get(n, 0) + 1
        if k == 0:
            for a, b in d.items():
                if b > 1:
                    ans += 1
        else:
            for a in d.keys():
                if a+k in d:
                    ans += 1
        return ans

Read More

Leetcode Contest 21

2017-02-25

今晚是一次丰盛的聚餐：羊肉汤，金鲳鱼，红烧排骨，炒牛肉和炒青菜。

这次比赛我全都做出来了！可惜前三题都WA了一次，而且都是粗心大意的错。

第一题Minimum Absolute Difference in BST，我采取了简单粗暴的方法：首先中序遍历将所有数放在一个数组里，然后返回相邻两个数之间差的最小值。

# 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 getMinimumDifference(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        ans = []
        def inorder(root):
            if not root:
                return
            inorder(root.left)
            ans.append(root.val)
            inorder(root.right)
        inorder(root)
        return min(ans[i+1]-ans[i] for i in xrange(len(ans)-1))

Read More

Leetcode Contest 20

2017-02-20

这周六的菜单是牛排骨、金鲳鱼和土豆丝，甜点是蛋糕。

这次比赛有四题，我只做出来了前三道。

第一道是简单的字符串处理。

class Solution(object):
    def detectCapitalUse(self, word):
        """
        :type word: str
        :rtype: bool
        """
        if all('A' <= c <= 'Z' for c in word):
            return True
        if all('a' <= c <= 'z' for c in word):
            return True
        return 'A' <= word[0] <= 'Z' and all('a' <= c <= 'z' for c in word[1:])

Read More

Idempotented algebra

2016-10-04

This post is a reading note to Bernstein’s Le “centre” de Bernstein, on the part of idempotented algebras (section 1.1 to 1.7, ibid.). Let \(R\) be a ring, an element \(e\) is called an idempotent if \(e^2=e\). Let \(k\) be a field.

Definition 1. A \(k\)-idempotented algebra \((H, I)\) is a \(k\)-algebra \(H\) together with the set idempotents \(I\) satisfying

(*) For any finite family \((x_i)\), there exists an idempotent \(e \in I\) such that \(ex_ie = x_i\) for all \(i\).

The \(k\)-structures of \(H\) is not involved in the discussion of this post, so we will ignore it. Let \((H, I)\) be an idempotented algebra for the rest of the post.

Lemma 2. Let \(e, f \in I\). The following are equivalent.

(1) \(eHe \subset fHf\)
(2) \(e \in fHf\)
(3) \(e = fef\)

Read More

1 ... 7 8 9 10 11