Leetcode Contest 29

今晚有鱼、豆腐和西芹。

这次比赛是久违的全一次就AC了,开心😄

第一题Binary Tree Tilt

题目大意:对于一个二叉树节点,定义它的tilt为左子树之和与右子树之和差的绝对值。给定一棵二叉树,求出所有节点tilt值之和。

感觉是简单的dfs套路。对于每个节点,递归算左右子树之和,那么它的tilt值就很容易求出来加到一个全局的变量里,然后返回当前子树之和:左子树+右子树+根节点

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
# 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 findTilt(self, root):
"""
:type root: TreeNode
:rtype: int
"""
ans = [0]
def dfs(root):
if not root:
return 0
left = dfs(root.left)
right = dfs(root.right)
ans[0] += abs(left-right)
return left+right+root.val
dfs(root)
return ans[0]

Read More

Leetcode Contest 28

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

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

第一题Student Attendance Record I

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

简单的字符串处理。

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

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

第一题Reverse Words in a String III

题目大意:给定一个句子,将其中所有单词逆序。
1
2
3
4
5
6
7
8
9
10
11
12
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

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

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

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

第一题Perfect Number

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

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

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

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

这次比赛有四题,题目都比较基础,可惜打错了一个变量名字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