github我的刷题 https://github.com/chaor/LeetCode_Python_Accepted | 我翻译的python3.4官网教程 kitt.me/py3
使用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'。
递归方法, 判断左右子树是否对称: 1)左右子树的根节点都为空或者val相同, 2)左子树的左子树与右子树的右子树对称, 3)左子树的右子树与右子树的左子树对称。
和Permutation那道题目差不多，也是递归，不过要去重。先排序，再利用prevNum变量区分是否重复。
一开始我用被除数一次一次地减除数，这样太慢了，遇到被除数为2147483648除数为1的情况就挂了。可以用被除数不断地减除数的1倍、2倍、4倍、8倍...这样就快了。使用位运算，被除数与除数同号时商为正，异号时商为负。
PyDev是Eclipse的一个Python IDE插件, Eclipse Marketplace里只能安装最新的3.3.3版本，装完以后PyDev并没有出现。可以手动安装PyDev2。系统是OSX 10.9.1, Eclipse版本是Kepler SP1。
C++使用两种memory: heap和stack。Stack存储每个函数的信息，包括instructions, variables defined in that function。如果函数1 call 函数2, 函数2的信息存到stack顶部。函数return时，它的所有信息被pop。Heap存global variables, C++允许程序员自己在heap上分配内存, 即new(), new总是返回指向分配在heap的内存的指针。程序员必须自己释放掉不再需要的内存, 即delete。
先对所有intervals按start值排序, 然后遍历, 如果当前Interval.start <= 已merged的大的Interval.end, 则扩展已merged的大的Interval.end。
BST中序遍历就是一个sorted list, 要求O(1) space, 经1楼提醒, 用first, second两个变量记录可能交换的节点即可。如果只有一个降序对(如20, 10, 30, 40, 50), 用first, second记录。如果有两个降序对(如10, 40, 30, 20, 50或50, 20, 30, 40, 10), 用第二个降序对中小的数更新second。while循环中19~23行换成"print root.val"就是非递归的中序遍历。
The result of BST inorder traversal is a sorted list. This problem requires O(1) space, according to the first comment below, only two variables (first, second) are enough to record nodes to be exchanged. If there's only one descending order pair (e.g. 20, 10, 30, 40, 50), use first & second to record it. If there are two descending order pairs (e.g. 10, 40, 30, 20, 50 or 50, 20, 30, 40, 10), use the smaller number in second pair to update second. If we change line 19-23 in while loop to "print root.val", then it's non-recursive inorder traversal of binary tree.
用dictionary, get item的平均时间复杂度为O(1), 可以把key设为list中的数, value用于标记是否访问过。遍历所有的key, 不断找寻其+1和-1得到的值是否在dictionary中, 记下最长的连续序列长度。
父节点把已有的值传给子节点, 子节点把这个值乘以10再加上自身的值。
记录最远能到达的范围, 每次在这个范围内搜, 找出下一跳的最远范围, 更新最远范围和跳数。
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param root, a tree node
# @return a boolean
def isBalanced(self, root):
return self.check(root)[1]
# @param root, a tree node
# @return a tuple (int height, bool isBalanced)
def check(self, root):
if root == None: return (0, True)
LH, LisB = self.check(root.left)
RH, RisB = self.check(root.right)
return ( max(LH, RH) + 1, LisB and RisB and abs(LH - RH) <= 1 )
左右子树只存在一个时不能返回0, 而是要沿着那个子树继续找下去。
递归, 对于[start, end]范围内的每个节点, 产生所有可能的左、右子树, 再产生(#左子树 x #右子树)棵树, 返回所有的root nodes。gen函数返回一个list of root nodes, 每个root node所表示的树是由[start, end]这个范围内的数构成的BST。