Leetcode Contest 33

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

第一题Longest Harmonious Subsequence

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

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

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

Read More

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

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

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

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

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

Read More

Cabaret

昨天晚上并没有参加每周一次的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

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

Induced representations and Mackey theory

Let \(G\) be a group. A linear representation of \(G\) is a pair \((\rho, V)\), where \(V\) is a finite dimensional vector space over \(\mathbb{C}\) and \(\rho: G \to GL(V)\) is a group homomorphism. Without ambiguity, we will call \(\rho\) a representation of \(G\). Let \((\rho_1, V_1)\) and \((\rho_2, V_2)\) be two representations of \(G\), an intertwining operator between them is a linear map \(T: V_1 \to V_2\) such that for any \(g \in G\), the following diagram commutes: \[\begin{equation}\label{eq:diagram} \require{AMScd}\begin{CD} V_1 @>T>> V_2 \\ @V{\rho_1(g)}VV @VV{\rho_2(g)}V \\ V_1 @>T>> V_2 \end{CD} \end{equation}\] Let \(\text{Hom}_G(\rho_1, \rho_2)\) be the space of all intertwining operators between \(\rho_1\) and \(\rho_2\).

Let \((\rho, V)\) be a representation of \(G\). Let \(H\) be a subgroup of \(G\), then we can restrict \(\rho\) to \(H\) to get a representation of \(H\). We will use \(\text{Res}^G_H \, \rho\) to denote the restricted representation of \(H\) from \(\rho\). Conversely, if \(\pi\) is a representation of \(H\), then we can construct a representation of \(G\) from \(\pi\), which is known as induced representation of \(G\) from \(\pi\), denoted as \(\text{Ind}_H^G \, \pi\). In this post, I will first talk about the precise description of induced representations and the relations between \(\text{Res}^G_H\) and \(\text{Ind}_H^G\). I will then discuss Mackey’s theorem, which dictates a further relation between restricted and induced representations.

Read More

Tensor product of two linear maps

Let \(A \in End(V)\) and \(B \in End(W)\) be two linear maps. We can define naturally the tensor product \(A \otimes B\) of \(A\) and \(B\), from \(V \otimes W\) to \(V \otimes W\), sending \(v \otimes w\) to \(Av \otimes Bw\). In this post, I am going to realize \(A \otimes B\) as a matrix and relate the determinant and trace of \(A \otimes B\) to the ones of \(A\) and \(B\).

Let \(V\) and \(W\) be two vector spaces over a field \(K\) with \(\dim V=n\) and \(\dim W=m\). Let \(e_1, \dots, e_n\) be a basis of \(V\) and let \(f_1, \dots, f_m\) a basis of \(W\). Under the basis, a linear map \(A: V \to V\) can be realized as an \(n \times n\) matrix \((a_{ij})_{1 \le i,j \le n}\), where \(a_{ij} \in K\). Similarly, a linear map \(B: W \to W\) can be realized as a \(m \times m\) matrix \((b_{kl})_{1 \le k, l \le m}\). Now, \(V \otimes W\), as a vector space, has basis \(\{e_i \otimes f_j: 1 \le i \le n, 1 \le j \le m\}\). And, \[\begin{align*} A \otimes B (e_i \otimes f_j) &= A(e_i) \otimes B(f_j) \\ &= \sum_{k}a_{ki}e_k \otimes \sum_{l}b_{lj}f_l \\ &= \sum_{k,l}a_{ki}b_{lj} e_k \otimes f_l. \end{align*}\]

Read More