弱鸡刷题打卡贴

当时找到现在的工作时只刷了10道EASY，现在来还债了。。。


3.25

136. Single Number
448. Find All Numbers Disappeared in an Array
- 用set

538. Convert BST to Greater Tree
- 右-中-左的 in-order traversal

3.29

101. Symmetric Tree

take1:
def isSymmetric(l_tree, r_tree):
            if l_tree is None:
                return True if r_tree is None else False
            elif r_tree is None:
                return True if l_tree is None else False
            else:
                return l_tree.val == r_tree.val and isSymmetric(l_tree.left, r_tree.right) and isSymmetric(l_tree.right, r_tree.left)

take2:
def isSymmetric(l_tree, r_tree):
            if l_tree is None and r_tree is None:
                return True
            elif l_tree is None or r_tree is None:
                return False
            elif l_tree.val != r_tree.val:
                return False
            else:
                return isSymmetric(l_tree.left, r_tree.right) and isSymmetric(l_tree.right, r_tree.left)

take 2 beats 89%, take1 beats 59%

O(1)操作的微小差值在迭代层数n多了以后还是会有显著的差距！

take3: iterative -> level order traversal/BFS

总结：能早return的就早return

4.17

Riverbed Python面试题

做一个控制飞机的队列
飞机有两种类型P和C，两种大小L和S
要求：
1. P型优先级高于C型
2. L型优先级高于S型
3. 类型和大小都一样的情况下，先进QUEUE的飞机先出

实现的重点在于利用Python 的sort函数对tuple的处理：
sort会对tuple的每一个元素从左到右依次比较！！

self.queue.put( ((aircraft.get_type(), aircraft.get_size(), time.time()) , aircraft))
Python 2.2+ sorting is stable
https://stackoverflow.com/questi ... rtab=active#tab-top

Old way: list decoration
https://www.linuxtopia.org/onlin ... python_ch20s04.html



476. Number Complement

从最低位bit开始每个bit位与其对应的bit位的1用XOR

| or
& and
^ xor

用 << 来移 bit 1的位置

3.27

169. Majority Element     
第一遍做用了个dict，后来看到最优解用一个变量标记当前major另一个变量标记当前major的出现次数

3.28

46. Permutations
backtracking. 在append到result list时需要创建一个shallow copy而不是直接传当前nums list的reference进去(会导致list里的东西都一样）

344. Reverse String
take1: lambda pattern matching -> TC476 超时
take2: 双指针. 傻逼错误： 用str.split转化str为list时未考虑 ' ' 会被split丢弃！
这道题python里性能最高竟然是用 return s[::-1]  -> 粒度为-1

3.30

94. Binary Tree Inorder Traversal
iterative实现

recursion本质是用call stack

4.2

102. Binary Tree Level Order Traversal
傻逼错误： 忘记考虑root is None的情况

240. Search a 2D Matrix II

傻逼错误：Binary Search必须要sorted!!!!  
此题需要找规律。 从第一行最右开始搜索利用了本地从左到右sorted, 从上到下sorted的性质！

4.3

404. Sum of Left Leaves

in-order traversal, 无所谓左中右 右中左
iterative: stack

4.4

513       
Find Bottom Left Tree Value

用deque做bfs

98. Validate Binary Search Tree

确保每个node都在一个区间内

4.5

晚上打了个篮球虚了，强行凑数

771. Jewels and Stones

4.6

563. Binary Tree Tilt

此题从下往上传值，用PostOrder遍历。 其实就是二叉树中的DFS的一种方式