继续刷题，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的组合会有多少种。
我改完上面代码里的变量，开始运行后几秒，就华丽丽的黑屏了。内存用尽而亡……

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