目前做完的解题集：https://github.com/cittie/Leetcode---Python
继续努力吧……
2017年1月4日
2016年12月27日
390. Elimination Game - I really didn't expect it working so perfect
最开始的时候，我写的代码是这样的：
nums = range(n, 0, -1)
while len(nums) > 1:
nums = nums[-2::-2]
毫无疑问，虽然答案对了，但是内存爆了。
于是搜了下其他人的答案，知道了思路是找左右点。然后有了下面的代码：
left, length ,step = 1, n, 1
right = left + (n - 1) * step
while length > 1:
left += step # Drop the first
step <<= 1
length >>= 1
right = left + (length - 1) * step # Get the right point.
left, right = right, left
step = ~step + 1
扔到PyCharm里调试，并和上面那个结果做Assert，居然完美通过，然后我就木凳狗带了——妈蛋我自己都只有个大概思路就撸了啊，没想到居然没什么错，这和我一贯以来20%的通过率不符啊……
nums = range(n, 0, -1)
while len(nums) > 1:
nums = nums[-2::-2]
毫无疑问，虽然答案对了，但是内存爆了。
于是搜了下其他人的答案，知道了思路是找左右点。然后有了下面的代码：
left, length ,step = 1, n, 1
right = left + (n - 1) * step
while length > 1:
left += step # Drop the first
step <<= 1
length >>= 1
right = left + (length - 1) * step # Get the right point.
left, right = right, left
step = ~step + 1
扔到PyCharm里调试，并和上面那个结果做Assert，居然完美通过，然后我就木凳狗带了——妈蛋我自己都只有个大概思路就撸了啊，没想到居然没什么错，这和我一贯以来20%的通过率不符啊……
2016年12月1日
312. Burst Balloons 继续趟pytho的坑……
这次被坑的是初始化二维数组……
[[0] * size] * size != [[0] * size for i in range(size)] == [[0 for i in range(size)] for i in range(size)]
然后读了读 http://ars.me/programming/2014/06/14/py-listmul/ 妥了……
[[0] * size] * size != [[0] * size for i in range(size)] == [[0 for i in range(size)] for i in range(size)]
然后读了读 http://ars.me/programming/2014/06/14/py-listmul/ 妥了……
2016年11月30日
花了差不多一下午补DP相关的东西，终于勉强做完了377. Combination Sum IV
在思路上绕了好久，最后还是没解决，忍不住去搜索了。然后发现是自己不擅长的DP，花了差不多整个下午，终于能勉强答题了。
class Solution(object):
def combinationSum4(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
dp = [1] + [0] * target
for i in range(target + 1):
for num in nums:
if i + num <= target:
dp[i + num] += dp[i]
return dp[target]
答完题回来看看，似乎确实不难啊……
class Solution(object):
def combinationSum4(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
dp = [1] + [0] * target
for i in range(target + 1):
for num in nums:
if i + num <= target:
dp[i + num] += dp[i]
return dp[target]
答完题回来看看，似乎确实不难啊……
2016年11月17日
378. Kth Smallest Element in a Sorted Matrix的附带收获
神之多重list展开：
matrix_expanded = [element for line in matrix for element in line]
这很Python，写了两个for循环的我给跪了……
matrix_expanded = [element for line in matrix for element in line]
这很Python，写了两个for循环的我给跪了……
2016年11月9日
406. Queue Reconstruction by Height 的Python解法
研究了好久算法，最后参考了别人的思路，才发现代码可以这么简单……
思路总结：
1. 预排序，h从大到小，k从小到大
2. 依次把每个元素插到新list的k位置
class Solution(object):
def reconstructQueue(self, people):
"""
:type people: List[List[int]]
:rtype: List[List[int]]
"""
result = []
people.sort(key = operator.itemgetter(1))
people.sort(key = operator.itemgetter(0), reverse = True)
for p in people:
result.insert(p[1], p)
return result
这样的思路实现起来，真的很简单啊！
思路总结：
1. 预排序，h从大到小，k从小到大
2. 依次把每个元素插到新list的k位置
class Solution(object):
def reconstructQueue(self, people):
"""
:type people: List[List[int]]
:rtype: List[List[int]]
"""
result = []
people.sort(key = operator.itemgetter(1))
people.sort(key = operator.itemgetter(0), reverse = True)
for p in people:
result.insert(p[1], p)
return result
这样的思路实现起来，真的很简单啊！
2016年5月18日
2016年4月28日
2016年4月23日
2015年12月17日
工作生涯中遇到的第五次裁员
似乎入了游戏这行，时不时就得遇上裁员。我在Glu第一份合同到期续签的时候，就正好赶上了。昨天早上公司9点多开了个全体会，很简单很直白的告诉大家，因为不景气，裁员了。
不过这也算早有前兆。半年多前腾讯入股Glu时，股价一度到过5刀多，而前段时间最低是2.8左右，几乎少了50%。股价基本是美国公司经营情况的晴雨表，结合行业的大行情，再加上工作室永恒战士4收入也不甚理想，裁员其实也不是那么意外。
游戏行业就是这样，永远不知道下一刻是什么情况。永恒战士4刚立项到做完，国内iOS已经变得面目全非，从以前的混战变成了网易腾讯联手占据前十。偏偏永恒战士4是个重度ARPG游戏，而且还是特意改成了面向中国市场的设计，玩法上却并没有很新颖突出的地方，结果也就是维持着一个能稍稍收回来成本的情况。所以从上线一直到今天，始终也没能改出出彩的玩法，于是今天就各自挥手再见了。
不过还好的是大家都看惯聚散离别，纷纷收拾东西的时候，留恋伤感却并没有什么难过和不舍。而且补偿也很丰厚，连带着年终的部分都给了，至少安心过年是不成问题了。
啊，忘了说，这次我也没有被裁。公司留下了一个小团队，计划把目前的项目做背水一战。所以，再过几个月，就能看看是不是要遇到人生中经历的第六次裁员了。
不过这也算早有前兆。半年多前腾讯入股Glu时，股价一度到过5刀多，而前段时间最低是2.8左右，几乎少了50%。股价基本是美国公司经营情况的晴雨表，结合行业的大行情，再加上工作室永恒战士4收入也不甚理想，裁员其实也不是那么意外。
游戏行业就是这样，永远不知道下一刻是什么情况。永恒战士4刚立项到做完，国内iOS已经变得面目全非，从以前的混战变成了网易腾讯联手占据前十。偏偏永恒战士4是个重度ARPG游戏，而且还是特意改成了面向中国市场的设计，玩法上却并没有很新颖突出的地方，结果也就是维持着一个能稍稍收回来成本的情况。所以从上线一直到今天，始终也没能改出出彩的玩法，于是今天就各自挥手再见了。
不过还好的是大家都看惯聚散离别，纷纷收拾东西的时候，留恋伤感却并没有什么难过和不舍。而且补偿也很丰厚，连带着年终的部分都给了，至少安心过年是不成问题了。
啊，忘了说，这次我也没有被裁。公司留下了一个小团队，计划把目前的项目做背水一战。所以，再过几个月，就能看看是不是要遇到人生中经历的第六次裁员了。
2015年7月13日
又踩了Python的一个小坑
今天因为不熟悉Python的(x for x in y if x is xxx)句式，把if条件写在前面，白白花了两个小时调试……好悲伤！
第一版里面写了个判断句式 if any(x is xxx for x in y)，然后居然没报错，更神奇的是还通过了单元测试……于是在错误的道路上越走越远，第二个单元测试用例通不过的时候，怎么都没有怀疑到句式，以为是编码错误、句式不对或者导入有问题。最后重写了判断才一切正常。
好吧，新手多踩踩坑就好了，以后就没事了！
第一版里面写了个判断句式 if any(x is xxx for x in y)，然后居然没报错，更神奇的是还通过了单元测试……于是在错误的道路上越走越远，第二个单元测试用例通不过的时候，怎么都没有怀疑到句式，以为是编码错误、句式不对或者导入有问题。最后重写了判断才一切正常。
好吧，新手多踩踩坑就好了，以后就没事了！
2015年6月25日
继续刷题，Merge two sorted lists这题，Python暴力排序和判断排序居然是一样的时间……
https://leetcode.com/problems/merge-two-sorted-lists/
先试了试判断排序：
def mergeTwoLists(self, l1, l2):
l = []
while l1 and l2:
if l1.val <= l2.val:
l.append(l1.val)
l1 = l1.next
else:
l.append(l2.val)
l2 = l2.next
while l1:
l.append(l1.val)
l1 = l1.next
while l2:
l.append(l2.val)
l2 = l2.next
return l
然后72ms
然后无聊想看看暴力读取然后排序：
def mergeTwoLists(self, l1, l2):
l = []
while l1:
l.append(l1.val)
l1 = l1.next
while l2:
l.append(l2.val)
l2 = l2.next
l.sort()
return l
居然还是72ms……
先试了试判断排序：
def mergeTwoLists(self, l1, l2):
l = []
while l1 and l2:
if l1.val <= l2.val:
l.append(l1.val)
l1 = l1.next
else:
l.append(l2.val)
l2 = l2.next
while l1:
l.append(l1.val)
l1 = l1.next
while l2:
l.append(l2.val)
l2 = l2.next
return l
然后72ms
然后无聊想看看暴力读取然后排序：
def mergeTwoLists(self, l1, l2):
l = []
while l1:
l.append(l1.val)
l1 = l1.next
while l2:
l.append(l2.val)
l2 = l2.next
l.sort()
return l
居然还是72ms……
2015年6月17日
开始刷Leetcode，然后第一题就TLE了……
今天开始刷leetcode，第一题：Word Break
判断给定的一个字符串能否被拆成字典里的词。
一开始不知道怎么想的，试图用二分加递归做，然后就LTE了……然后发现自己实在是蛋疼，长字符串拆去单词后的部分根本没必要和词典做对比，完全是受了例子的误导。
然后接下来就容易多了，代码是这样的：
class Solution:
# @param s, a string
# @param wordDict, a set
# @return a boolean
def wordBreak(self, s, wordDict):
if not s or not wordDict:
return False
flags = [False for i in range(len(s) + 1)]
flags[0] = True
for s_len in range(1, len(s) + 1):
for i in range(s_len):
if flags[i] and s[i:s_len] in wordDict:
flags[s_len] = True
return flags[len(s)]
当然，漏了flags[0] = True这句导致失败好几次我是不会随便乱说的……
判断给定的一个字符串能否被拆成字典里的词。
一开始不知道怎么想的，试图用二分加递归做，然后就LTE了……然后发现自己实在是蛋疼，长字符串拆去单词后的部分根本没必要和词典做对比，完全是受了例子的误导。
然后接下来就容易多了，代码是这样的：
class Solution:
# @param s, a string
# @param wordDict, a set
# @return a boolean
def wordBreak(self, s, wordDict):
if not s or not wordDict:
return False
flags = [False for i in range(len(s) + 1)]
flags[0] = True
for s_len in range(1, len(s) + 1):
for i in range(s_len):
if flags[i] and s[i:s_len] in wordDict:
flags[s_len] = True
return flags[len(s)]
当然，漏了flags[0] = True这句导致失败好几次我是不会随便乱说的……
2015年6月16日
订阅：
博文 (Atom)
博文
