kitt blog (欢迎留言，最近刷的题目放到github上了)

Python处理字符串的巨大优势。

动态规划, 看一位是0还是1~9，看两位是不是在10~26之间。dp[N] = M 表示字符串s的前N位有M种解码方式。

利用hash的和，即如果words中有n个单词，无论顺序如何，sum(hash(word1), hash(word2), ... hash(wordN))都是相等的。

动态规划或递归。

来自1楼的光芒, 不解释。Thanks for the link in 1st floor.

    看了水中的鱼的解题报告，用快慢两个指针, 很巧妙的解法。快指针fast一次走两步, 慢指针slow一次走一步, 假设环外有X个节点, 即从head走X步可以到达环的第一个节点。再假设环有Y个节点, fast和slow指针在环中的第K+1个节点相遇。那么相遇时fast指针和slow指针都走了 X + mY + K 次。因为fast一次走两步, 所以实际走过的节点数fast是slow的两倍, 两者的差一定是Y的倍数, 2(X + mY + K) - (X + mY + K) = nY, 于是就有 X + K = (n - m)Y。

    此时让fast ＝ head, 从头开始走, slow在原位置继续走, 两者都一次走一步, fast和slow再次指向同一节点时, 这个节点就正好是环的第一个节点, 而且此时fast和slow正好走了X步。因为fast从head走了X步正好进入环, slow从原来位置走X步, 根据上一段末的等式, 有 X + mY + K + X = X + mY + (n - m)Y = X + nY, 即slow此时也在环的第一个节点。

同Binary Tree Level Order Traversal一样, 需要记录层的信息。dict[0] = [3], dict[1] = [9, 20]。

同Binary Tree Level Order Traversal题目一样，也需要一个dict来记录层的信息。dict[1] = [9, 20]。

开一个大小为32的数组, 记录每一位上1出现的个数, 然后模3即可得到所要求的single number。要注意正负号, 最高位为0(正)和1(负)时分开讨论。

要求只能扫一遍而且要in place, 只能通过交换A中的元素来实现。p0是指向0的指针, p2是指向2的指针, i是用于遍历的指针。如果当前元素A[i]是2, 则交换A[i]和A[p2]的值, 然后p2前移, i不动, 当i > p2就终止, 这样就排除了2的干扰，因为i前面的元素总是0或1。若A[i]是0, 交换A[i]和A[p0]的值, p0和i都后移, 若A[i]是1, 只要i后移即可, 换句话说, 总是把0往前放。

Python 6/-132结果为－1, 系统认为结果为0, 所以对除法使用了int(op1 * 1.0 / op2)。

Python的dictionary查找元素O(1)时间, 但缺点是无序。而collections.OrderedDict是有序的, 后加入的元素一定排在先加入元素的后面, 操作和dictionary类似:

import collections
a = collections.OrderedDict()
a[1] = 10 # 若1在a中就更新其值, 若1不在a中就加入(1, 10)这一对key-value。
a[2] = 20
a[3] = 30
del a[2]
a.popitem(last = True) # 弹出尾部的元素
a.popitem(last = False) # 弹出头部的元素

一开始总超时, 因为手动判断了一个key在不在OrderedDict中, 使用try...except...就过了。由于except只有KeyError一种, 所以不用写明。实际上except: 比 except KeyError: 要快一点点。但是使用OrderedDict纯属作弊，所以以下的Solution 1仅供说明Python的丰富数据类型:

使用BFS, 单词和length一块记录, dict中每个单词只能用一次, 所以用过即删。dict给的是set类型, 检查一个单词在不在其中(word in dict)为O(1)时间。设单词长度为L, dict里有N个单词, 每次扫一遍dict判断每个单词是否与当前单词只差一个字母的时间复杂度是O(N*L), 而每次变换当前单词的一个字母, 看变换出的词是否在dict中的时间复杂度是O(26*L), 所以要选择后者。Python真是慢啊, 同样的代码C++ 668ms过, Python 1416ms过。看到双向BFS的做法, 应该能更快, 再研究研究。

board最外面四条边上的'O'肯定不会被'X'包围起来, 从这些'O'入手, 使用BFS求出所有相邻的'O', 把这些'O'改为另一种符号, 比如'$'。然后再扫描一遍board, 把'O'换成'X', 把'$'换成'O'。

使用一个快指针和一个慢指针遍历，如果两者相遇说明有环。