弱鸡刷题打卡贴

4.7

654. Maximum Binary Tree

stack 加上 while loop 来找最值

补充内容 (2018-4-9 01:47):
从下往上传值

4.8

669. Trim a Binary Search Tree
从上往下 Trim， 每一层recursion都return。 没必要用dummy node的时候别硬用

173. Binary Search Tree Iterator
"Lazy" -- In order traversal 拆成两部分：

1. init时先把所有left node依次推入stack

2. 在每一次next的时候再把当前node的右subtree的left再推入。

4.10

238. Product of Array Except Self

两个loop, 第一个LOOP每一个元素乘以自己左边的， 第二个loop每一个元素乘以自己右边的

4.11

338. Counting Bits

1维 dp： I位元素看floor(I/2) 位元素，如果是奇数则再加1
loop内用Bitwise operater做除以2比除以2要快！ （O(c)操作差距通过for loop放大）


572. Subtree of Another Tree

helper func来决定两个树是否相同，
main里call自己 左子树含有t或者右子树含有t

用不用helper取决于迭代做的事情做的和Main func是不是一样！

4.12

121. Best Time to Buy and Sell Stock

初始化： max_profit , min_price = 0 , float('inf')
一个for  loop 在每个iteration:
找出当前最小的price，
计算当前价格减去min_price
找出当前最大的profit

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的位置

4.18

96. Unique Binary Search Trees

把以下思想化成DP做：

f(n) = f(0)f(n-1) + f(1)f(n-2) + ... + f(n-1)f(0)


108. Convert Sorted Array to Binary Search Tree

preorder traversal

mid = len(num) // 2

        root = TreeNode(num[mid])
        root.left = self.sortedArrayToBST(num[:mid])
        root.right = self.sortedArrayToBST(num[mid+1:])

4/21

110. Balanced Binary Tree

take1: 写一个get_height

然后  abs(get_height(root.left)-get_height(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)

take2: dfs/ post-order traversal
如果unbalanced会更快return而不需要等待所有结果计算完毕

4/23

167. Two Sum II - Input array is sorted

上周五一公司ONSITE题目的相似版。 原题是找一对最接近TARGET的值。
因为ARRAY SORTED, 所以充分利用这个性质，一头一尾各一个指针，如果小于TARGET则右移左POINTER， 如果大于TARGET则左移右POINTER.