Leetcode Contest 24

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

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

第一题Diameter of Binary Tree

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# 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

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

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

第一题Reverse String II

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
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

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

除了第一题WA了一次之外,其他三题都一次过了!

第一题K-diff Pairs in an Array

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
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

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

我的2015

最近在练习法语翻译的时候遇到Vigny的两句诗1

Quand on voit ce qu’on fut sur terre et ce qu’on laisse

Seul le silence est grand; tout le reste est faiblesse

无论生活过得精彩或者惨淡,记忆也都是若干断断续续的画面,最终也都是黑白的,没有声音。我喜欢写日记,因为日记可以帮助我回忆。今年的年度我是先在日记里写好了,然后再从里面挑出一些合成了这篇短短的博客。因此,我总觉得这篇博客怪怪的。

-----

2015年中我觉得对我最重要的事情就是换导师了。我原来的导师Prof. Yuval Flicker今年三四月份的时候退休了,我只好另选导师了。我对表示论感兴趣,但是系里只有三两个教授在做表示论,再仔细考虑一下自己以后可能要做的方向,那么就只剩下Prof. Yuval Flicker和Prof. James Cogdell了。我并没有其他选择,所以当Prof. Flicker退休之后,我在他们两人都同意之下,就正式更换了导师。Prof. Cogdell主要的工作在于L函数方面,所以我慢慢也往L函数这个方向靠拢了。如果现在有人问我是做什么方向的,我会回答是Representation theory of p adic groups。而现在我主要的研究一些表示的L函数的性质。在Prof. Cogdell的帮助下,我在12月考过了Candidacy Exam。希望我能在2016年里做出一些成果。

Read More

Gelfand pairs of finite groups

In this post, I mainly focus on introducing Gelfand pairs of finite groups.

Representations of finite groups

Let’s recall some concepts. Let \(G\) be a finite group. A (complex) representation of \(G\) is a pair \((\rho, V)\) where \(V\) is a vector space over \(\C\) and \(\rho: G \to GL(V)\) is a group homomorphism. Let \((\rho_1, V_1)\) and \((\rho_2, V_2)\) be representations of \(G\), a \(G\)-morphism, or simply a morphism, between these two representations is a linear map \(\varphi: V_1 \to V_2\) such that for any \(g \in G\) and \(v \in V_1\), \[\varphi(\rho_1(g)v) = \rho_2(g)\varphi(v).\] Then \(\mathrm{Hom}_G(\rho_1, \rho_2)\), the set of morphisms between \(\rho_1\) and \(\rho_2\), is a vector space over \(\C\). A representation \((\rho, V)\) is irreducible, if there is no proper subspace \(W \subset V\), such that \(\rho(g)w \in W\) for any \(g \in G\) and \(w \in W\). Between irreducible representations, we have Schur’s lemma.

Theorem 1 (Schur’s lemma). Let \(\rho_1\) and \(\rho_2\) be irreducible representations of \(G\). Then \[\begin{equation*} \mathrm{Hom}_G(\rho_1, \rho_2) \cong \left\{ \begin{array}{ll} \C, & \text{ if } \rho_1 \cong \rho_2; \\ 0, & \text{ otherwise.} \end{array} \right. \end{equation*}\]

It’s well known that \(G\) is semisimple, i.e., any representation of \(G\) decomposes into a direct sum of irreducible representations. A representation \((\rho, V)\) of \(G\) is called multiplicity free, if any irreducible representation appearing in the decomposition of \((\rho, V)\) appears exactly once, up to isomorphism.

Let \(H\) be a subgroup of \(G\). If \((\rho, V)\) is a representation of \(G\), we can certainly restrict the group homomorphism \(\rho: G \to GL(V)\) to \(H\) so that we can regard \((\rho, V)\) as a representation of \(H\). This is called the restriction of representations from \(G\) to \(H\), and the restricted representation of \(\rho\) will be denoted as \(r^G_H(\rho)\). Conversely, if \((\pi, W)\) is a representation of \(H\), we can build a representation \((\rho, V)\) of \(G\) out of \(\pi\), which is the induced representation, as follow.

Read More

Unfolding of a global integral for $GL_n \times GL_m$

Let \((\pi, V_\pi)\) and \((\pi^\prime, V_{\pi^\prime})\) be cuspidal, unitary, irreducible automorphic representations of \(GL_n(\mathbb{A})\) and \(GL_m(\mathbb{A})\) respectively. We assume \(m < n\). Let \(\varphi \in V_\pi\) and \(\varphi \in V_{\pi^\prime}\). To pair \(\varphi\) and \(\varphi^\prime\) suitably together, we first need to project \(\varphi\) correspondingly.

Let \(\psi\) be a additive continuous automorphic character of \(\mathbb{A}\). We can extend it to a character of \(N_n(\mathbb{A})\), the standard Borel subgroup of \(GL_n(\mathbb{A})\), in the standard way: \[\psi(u) = \psi\left(\sum_{i=1}^{n-1}u_{i,i+1}\right),\] for \(u = (u_{i,j}) \in N_n(\mathbb{A})\). Let \(Y=Y_{n, m}\) be the standard unipotent radical associated to the partition \((m+1, 1, \dots, 1)\) of \(GL_n\), i.e., \[Y=\left\{\left(\begin{array}{cc}I_{m+1}&*\\ 0&u\end{array}\right): u \in N_{n-m-1}\right\} \subset N_n.\] Let \(P_{m+1}\) be the mirabolic subgroup of \(GL_{m+1}\), then for \(p \in P_{m+1}(\mathbb{A})\) define \[\mathbb{P}^n_m \varphi(p) = |\det p|^{-\frac{n-m-1}{2}}\int_{Y(k)\backslash Y(\mathbb{A})} \varphi\left(y\left(\begin{array}{cc} p& \\ & I_{n-m-1} \end{array}\right)\right)\psi^{-1}(y) dy.\]

Now we can pair \(\varphi\) and \(\varphi^{\prime}\) in the following way: \[I(s; \varphi, \varphi^\prime) = \int_{GL_m(k)\backslash GL_m(\mathbb{A})} \mathbb{P}^n_m \varphi\left(\begin{array}{cc} h& \\ &1\end{array}\right)\varphi^\prime(h)|\det h|^{s-\frac{1}{2}}dh.\]

Read More

2014年

我本来想着从Florida回到Columbus就为2014写点东西,可是一直拖延到了今天眼看着新的学期快开始了才急急忙忙着手这事。其实写年度总结之类的博文还是挺有趣的,能看看自己这一年以来做过什么趣事傻事、做出什么样的进步。

2014年我经历了哥村的零下20度,听了马友友的小提琴,暑假回国跟亲人好友见面,过了口语可以教书,选了导师成了Tango Club的President,第一次教书是教微积分1,现在在Florida的迪士尼等烟花。新年快乐。

这是我在2014年最后一天发的微博,发微博的时候我正在迪士尼外面的停车场等凌晨的烟花,心情实际上并不是兴奋而是有点因孤单而生出的伤感。迪士尼并不适合单身一人游玩,一个人行走在拥挤且快乐的人群里总是有点尴尬,以至于我在一个小岛的岸边静静地坐了一个下午,看着一艘轮船一圈又一圈地环绕着小岛。晚上八点半左右我就从迪士尼里出来了,回到停车场的巴士上了。让我想不到的是已经有人比我先回到了巴士上了,是一群男生,所以我也不是太惊讶了。这次出来Florida玩我是跟团的,只是团里的人我一个不认识。跟一群陌生的人出去玩是一件很有挑战性的事情:他们基本上都是三三两两认识的人参团的,我要做的第一件事情就是打进“敌人”内部,难度在于我要用我那蹩脚的英语进行这项任务。后来我是跟一个来自印度尼西亚的家庭混熟了,母亲是OSU的博士(可是看起来比我母亲大人还老啊),父亲和女儿跟了过来在美国这边生活。他们就坐在我对面,聊起来也实在方便,在旅途的车上,有人能对上话倒也不至于太无聊。这次出来玩了一个星期,除了在迪士尼那天之外,我还是玩得挺开心的。在旅途的最后一天,我还很幸运地见到了一位高中同学。说起这件事也是挺巧合的,最后一天我们再次来到了环球影城,我在冒险岛开心游荡着,很快就把我感兴趣的点玩遍了(single rider太贴心了)。在下午两点的时候,我就打算离开了,走到大门刷了一下朋友圈竟然发现一位高中同学刚发了一张环球影城里的黄油啤酒的图。于是我又跑到哈利波特那里坐了趟列车到环球影城那边与朋友见上一面。与朋友见面的地方是我前天去的时候没有去过的地方,我也在她的推荐下尝了那美味的黄油啤酒。这旅途的惊喜,让我感到十分高兴。

沙滩上的日落-2014.12.28@St Petersburg

Read More