1、臺(tái)階問(wèn)題、斐波那契

一只青蛙可以跳上一級(jí)臺(tái)階凑保，也可以跳上兩級(jí)臺(tái)階，求青蛙跳上一個(gè)n級(jí)臺(tái)階共有多少種跳法

方法一：

 def fib(n):
    a, b = 0,1
    for _ in range(n):
         a, b = b, a+b
    return b

方法二：

def fib(n):
    a, b = 0,1
    for _ in range(n):
        a, b = b, a+b
    return b

方法三：

def memo(func):
    cache = {}
    def wrap(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]
    return wrap

@memo
def fib(n):
    if n < 2:
        return 1
    return fib(n-1) + fib(n-2)

2涌攻、臺(tái)階問(wèn)題欧引、斐波那契

一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)……它也可以跳上n級(jí)恳谎。
求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法芝此。

fib = lambda n : n if n < 2 else 2*fib(n-1)

3、矩形覆蓋問(wèn)題

第2n個(gè)矩形的覆蓋方法等于第2(n-1)加上第2(n-2)的方法因痛。

area = lambda i :i if i < 2 else area(n-1) + area(n-2)

4婚苹、楊氏矩陣查找

在一個(gè)m行n列二維數(shù)組中，每一行都按照從左到右遞增的順序排序鸵膏，每一列都按照從上到下遞增的順序排序膊升。
請(qǐng)完成一個(gè)函數(shù)，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)谭企，判斷數(shù)組中是否含有該整數(shù)廓译。

data = [[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
def find_young(data,target):
    m = len(data) - 1
    n = len(data[0]) - 1
    r = 0
    c = n
    while c>=0 and r<=m: #從左上方開(kāi)始查詢(xún)
        value = data[r][c]
        if value == target:
            return True
        elif value > target:
            c -= 1
        elif value < target:
            r += 1
    return False

5、去除列表中的重復(fù)元素

list1 = ['b','c','d','b','c','a','a']

• 用集合

  list(set(data))
  

• 用字典

  l2 = {}.fromkeys(list1).keys()
    #說(shuō)明：用于創(chuàng)建一個(gè)新字典债查，以序列seq中元素做字典的鍵
  

• 用字典并保持順序

  l2 = list(set(list1))
  l2.sort(key=l1.index)
  

• 列表推導(dǎo)式

  l2 = []
  [l2.append(i) for i in list1 if not i in l2]
  

6非区、鏈表成對(duì)

1->2->3->4轉(zhuǎn)換成2->1->4->3

obj = Solution()
for i in range(10):
    obj.append(i)

class ListNode:
    def __init__(self, x):
        self.value = 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、創(chuàng)建字典方法

工廠(chǎng)方法

items = [('name','earth'), ('port','80')]
dict2 = dict(items)

fromkeys()方法

dict1 = {}.fromkeys(('x', 'y'),-1)

8盹廷、合并兩個(gè)有序列表

合并排序O(nlogn)

list1 = [33, 37, 38, 39]
list2 = [35, 36, 40, 43, 45, 50]

尾遞歸

def _recursion_merge_sort(list1, list2, tmp):
    if len(list1) == 0 or len(list2) == 0:
        tmp.extend(list1)
        tmp.extend(list2)
        return tmp
    else:
        if list1[0] <list2[0]:
            tmp.append(list1[0])
            del list1[0]
        else:
            tmp.append(list2[0])
            del list2[0]
        return _recursion_merge_sort(list1, list2, tmp)

def recursion_merge_sort(list1, list2):
    tmp = _recursion_merge_sort(list1, list2,[])
    return tmp

循環(huán)

def loop_merge_sort(list1, list2):
    result = []
    while list1 and list2:
        if list1[0] <= list2[0]:
            result.append(list1[0])
            del list1[0]
        else:
            result.append(list2[0])
            del list2[0]
    if list1 == []:
        result.extend(list2)
    if list2 == []:
        result.extend(list1)
    return result

9征绸、交叉鏈表求交點(diǎn)

其實(shí)思想可以按照從尾開(kāi)始比較兩個(gè)鏈表，如果相交，則從尾開(kāi)始必然一致歹垫，只要從尾開(kāi)始比較剥汤，直至不一致的地方即為交叉點(diǎn)。

a = [1,2,3,7,9,1,5]
b = [4,5,7,9,1,5]
for i in range(1, min(len(a),len(b))):
    if i== 1 and (a[-1] != b[-1]):
        print('No')
        break
    else:
        if a[-i] != b[-i]:
            print('交叉節(jié)點(diǎn)：', a[-i+1])
            break
            
#構(gòu)造鏈表類(lèi)
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

#求出鏈表長(zhǎng)度的差值排惨，長(zhǎng)鏈表的指針先想后移動(dòng)lenA-lenB。
#然后兩個(gè)鏈表一起往后走碰凶，若結(jié)點(diǎn)相同則第一個(gè)相交點(diǎn)           
def node(l1, l2):
    len1, len2 = 0, 0
    #求兩鏈表長(zhǎng)度
    while l1.next: 
        l1 = l1.next
        len1 += 1
    while l2.next:
        l2 = l2.next
        len2 += 1
    #如果相交
    if l1.next == l2.next:
        #長(zhǎng)鏈表先走
        if len1 > len2:
            for _ in range(len1 - len2):
                l1 = l1.next
            return l1
        else:
            for _ in range(len2-len1):
                l2 = l2.next
            return l2
    else:
        return 

10暮芭、二分查找

O(logn)

def binary_search(list, item):
    low = 0
    high = len(list) - 1
    while low <= high:
        middle = int((low + high)/2)
        guess = list[middle]
        if guess > item:
            high = middle - 1
        elif guess < item:
            low = middle + 1
        else:
            return middle
    return 'Not Found'

# 排序列表
orded_list = [1,3,4,5,6,7,8,9,11]
print(binary_search(orded_list,3))
        
#補(bǔ)充：
l = [3,7,9,6,4,8,11,1,5]
l = sorted(l)

11、快速排序

O(nlogn)

def quick_sort(list):
    if len(list) < 2:
        return list
    else:
        middle = list[0]
        lessbeforemiddle = [x for x in list[1:] if x <= middle]
        largebefoemiddle = [x for x in list[1:] if x > middle]
        finally_list = quick_sort(lessbeforemiddle) + [middle] + quick_sort(largebefoemiddle)
        return finally_list

quick_sort(l)

12欲低、冒泡排序

O(n^2)

def swap(l, i, j): #交換
    t = l[i]
    l[i] = l[j]
    l[j] = t
    
def bubble_sort(list):
    n = len(list)
    while n > 1:
        i = 1
        while i < n:
            if list[i-1] > list[i]:
                swap(list, i ,i-1)
            i += 1
        n -= 1

13辕宏、廣度優(yōu)先搜索

O(節(jié)點(diǎn)數(shù)+邊數(shù))

graph = {}
graph["you"] = ["alice",'bob',"calm"]
graph["alice"] = ["peggym"]
graph["bob"] = ["anuj","peggym"]
graph["peggym"] = ["anuj"]
graph["anuj"] = ["peggym"]
# print type(graph)
from collections import deque

def person_is_seller(person):
    if 'm' in person:
        return person

def search(name):
    search_queue = deque()
    search_queue += graph[name]
    searched = []
    while search_queue:
        person = search_queue.popleft()
        if person not in searched:
            if person_is_seller(person):
                print(person + 'is seller')
                searched.append(person)
            esle:
                search_queue += graph[person]
                searched.append(person)
    return False
                
search('you')

14、動(dòng)態(tài)規(guī)劃———找零問(wèn)題

#values是硬幣的面值values = [ 25, 21, 10, 5, 1]
#valuesCounts   錢(qián)幣對(duì)應(yīng)的種類(lèi)數(shù),5
#money  總錢(qián)數(shù),63
#coinsUsed   對(duì)應(yīng)于目前錢(qián)幣總數(shù)i所使用錢(qián)幣數(shù)目
def coin_change(values, valuesCounts, money, coinsUsed):
    for i in range(1, money + 1):
        minValue = i
        for num in range(valuesCounts):
            if values[num] <= i:
                count = coinsUsed[i - values[num]] + 1
                if count < minValue:
                    minValue = count
        coinsUsed[i] = minValue
        print('第%d 最少需要 %d 枚錢(qián)幣' %(i, minValue))
        
 
if __name__ == '__main__':
# values = [25, 21, 10, 5, 1]
money = 63
values = [1,2,5,7,9,20]
coinsUsed = [0]*(money + 1)
length = len(values)
coin_change(values, length, money, coinsUsed)

15砾莱、二叉樹(shù)節(jié)點(diǎn)

class Node(object):
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

tree = Node(1, Node(3, Node(7, 0), 6), Node(2, 5, 4)