1 红黑树
红黑树与AVL的比较：
AVL是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多；
红黑是用非严格的平衡来换取增删节点时候旋转次数的降低；
所以简单说，如果你的应用中，搜索的次数远远大于插入和删除，那么选择AVL，如果搜索，插入删除次数几乎差不多，应该选择RB。
1 台阶问题/斐波纳挈
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
1fib = lambda n: n if n <= 2 else fib(n - 1) + fib(n - 2)
第二种记忆方法
def memo(func):
cache = {}
def wrap(*args):
if args not in cache:
cache[args] = func(*args)
return cache[args]
return wrap
@ memo
def fib(i):
if i < 2:
return 1
return fib(i-1) + fib(i-2)
第三种方法
def fib(n):
a, b = 0, 1
for _ in xrange(n):
a, b = b, a + b
return b
2 变态台阶问题
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
1fib = lambda n: n if n < 2 else 2 * fib(n - 1)
3 矩形覆盖
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
第2*n个矩形的覆盖方法等于第2*(n-1)加上第2*(n-2)的方法。
1f = lambda n: 1 if n < 2 else f(n - 1) + f(n - 2)
4 杨氏矩阵查找
在一个m行n列二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
5 去除列表中的重复元素
用集合
1list(set(l))
用字典
l1 = ['b','c','d','b','c','a','a']
l2 = {}.fromkeys(l1).keys()
print l2
用字典并保持顺序
l1 = ['b','c','d','b','c','a','a']
l2 = list(set(l1))
l2.sort(key=l1.index)
print l2
l1 = ['b','c','d','b','c','a','a']
l2 = []
[l2.append(i) for i in l1 if not i in l2]
面试官提到的,先排序然后删除.
6 链表成对调换
1->2->3->4转换成2->1->4->3.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
# @param a ListNode
# @return a ListNode
def swapPairs(self, head):
if head != None and head.next != None:
next = head.next
head.next = self.swapPairs(next.next)
next.next = head
return next
return head
7 创建字典的方法
1 直接创建
1dict = {'name':'earth', 'port':'80'}
2 工厂方法
items=[('name','earth'),('port','80')]
dict2=dict(items)
dict1=dict((['name','earth'],['port','80']))
3 fromkeys()方法
dict1={}.fromkeys(('x','y'),-1)
dict={'x':-1,'y':-1}
dict2={}.fromkeys(('x','y'))
dict2={'x':None, 'y':None}
网友评论