在思路上绕了好久，最后还是没解决，忍不住去搜索了。然后发现是自己不擅长的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]
答完题回来看看，似乎确实不难啊……
2016年11月30日
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日
2015年6月1日
用Python穷举魔兽世界队伍的构成
居然是2015第一篇……
起因是知乎游戏群里，有人出了道题，魔兽世界当前版本里，1坦1治疗3输出，能有多少种组合？前置条件是，只看职业组合，不分具体天赋。例如1德鲁依1武僧3法师，无论是德鲁依还是武僧做坦，都算作一种组合。
然后大家陷入了各种排列组合的陷阱中……各种答案都有，并且看上去都没错。于是最后我决定用代码暴力验算。最后几个人的验算结果一致得出结论，排列是2450种。
代码如下：
然后，我们决定玩个更刺激的，算算25人团队副本里，2T6H17DPS的组合会有多少种。
我改完上面代码里的变量，开始运行后几秒，就华丽丽的黑屏了。内存用尽而亡……
代码尚未成功，仍需努力……
起因是知乎游戏群里，有人出了道题，魔兽世界当前版本里，1坦1治疗3输出，能有多少种组合？前置条件是，只看职业组合，不分具体天赋。例如1德鲁依1武僧3法师，无论是德鲁依还是武僧做坦，都算作一种组合。
然后大家陷入了各种排列组合的陷阱中……各种答案都有，并且看上去都没错。于是最后我决定用代码暴力验算。最后几个人的验算结果一致得出结论，排列是2450种。
代码如下：
import itertools
WOW_classes = { "war": "Warrior",
"dk": "Dark Knight",
"pal": "Paladin",
"ht": "Hunter",
"sm": "Shaman",
"dru": "Druid",
"rog": "Rogue",
"monk": "Monk",
"mage": "Mage",
"wl": "Warlock",
"pri": "Priest"
}
all_DPS = [WOW_classes[dps] for dps in WOW_classes]
T = ["war", "dk", "dru", "pal", "monk"]
all_T = [WOW_classes[t] for t in T]
H = ["pal", "sm", "dru", "monk", "pri"]
all_H = [WOW_classes[h] for h in H]
team_queue = [all_T] * 1 + [all_H] * 1 + [all_DPS] * 3
print("Generating possible teams...")
possible_team = list(itertools.product(*team_queue))
print("Generating possible teams are generated.")
all_team = []
print("Start sorting and removing duplicate team...")
for team in possible_team:
if sorted(team) not in all_team:
all_team.append(sorted(team))
print("Sorting and removing are done.")
print("Begin to write to file...")
file = open("team.txt", "w+")
for team in all_team:
file.write(str(team) + '\n')
file.write(("\nTotal combination is %d!" % len(all_team)))
file.close()
print("Writing finished.")
然后，我们决定玩个更刺激的，算算25人团队副本里，2T6H17DPS的组合会有多少种。
我改完上面代码里的变量，开始运行后几秒，就华丽丽的黑屏了。内存用尽而亡……
代码尚未成功，仍需努力……
2014年12月31日
2014年终总结之随笔乱写
终于有机会乱写一气2014的年终总结了……
体重从历史最高的68公斤降到了63公斤，从每次做3组，1组15个俯卧撑变成了6组20个俯卧撑。
Python学得马马虎虎，距离自己搭个网站还有不少距离，倒是单元测试用例写得炉火纯青。
应该是进了目前为止自己最满意的公司了，收入也很满意目前到手的数似乎差不多和合同税前的数一样了。
股市大概有了6k的收益，但还没到手的算不上收益吧。
多了一只认识不久的喵星人和一个认识了一年多的师妹。
在美国亚马逊破戒后一发不可收拾，任性了好多次。
其他的，想到再慢慢写吧。
体重从历史最高的68公斤降到了63公斤，从每次做3组，1组15个俯卧撑变成了6组20个俯卧撑。
Python学得马马虎虎，距离自己搭个网站还有不少距离，倒是单元测试用例写得炉火纯青。
应该是进了目前为止自己最满意的公司了，收入也很满意目前到手的数似乎差不多和合同税前的数一样了。
股市大概有了6k的收益，但还没到手的算不上收益吧。
多了一只认识不久的喵星人和一个认识了一年多的师妹。
在美国亚马逊破戒后一发不可收拾，任性了好多次。
其他的，想到再慢慢写吧。
2014年12月23日
订阅：
博文 (Atom)
博文
