Leetcode进度：141/448

目前做完的解题集：https://github.com/cittie/Leetcode---Python

继续努力吧……

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%的通过率不符啊……

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/ 妥了……

花了差不多一下午补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]

答完题回来看看，似乎确实不难啊……

378. Kth Smallest Element in a Sorted Matrix的附带收获

神之多重list展开：

matrix_expanded = [element for line in matrix for element in line]

这很Python，写了两个for循环的我给跪了……

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

这样的思路实现起来，真的很简单啊！

又踩了Python的一个小坑

今天因为不熟悉Python的(x for x in y if x is xxx)句式，把if条件写在前面，白白花了两个小时调试……好悲伤！

第一版里面写了个判断句式 if any(x is xxx for x in y)，然后居然没报错，更神奇的是还通过了单元测试……于是在错误的道路上越走越远，第二个单元测试用例通不过的时候，怎么都没有怀疑到句式，以为是编码错误、句式不对或者导入有问题。最后重写了判断才一切正常。

好吧，新手多踩踩坑就好了，以后就没事了！

继续刷题，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……

开始刷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这句导致失败好几次我是不会随便乱说的……

用Python穷举魔兽世界队伍的构成（续）

终于，今天改了改，写出了一个能计算10人团队的代码，但是，一但超过15人，立扑……数量级还是增长得太快。

妈蛋代码格式太烂，删了……

用Python穷举魔兽世界队伍的构成

居然是2015第一篇……

起因是知乎游戏群里，有人出了道题，魔兽世界当前版本里，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的组合会有多少种。
我改完上面代码里的变量，开始运行后几秒，就华丽丽的黑屏了。内存用尽而亡……

代码尚未成功，仍需努力……