翻書問題或者走臺階問題：
- 共有n個臺階上渴，每次只能上1個臺階或者2個臺階冯袍，共有多少種方法爬完臺階。
- 共有n頁書苍鲜，每次只能翻1頁或者2頁書思灰，共有多少種方法翻完全書。
# f(n)為翻完全書的方法
# 遞歸寫法
def f(n):
if n == 1:
return 1
if n == 2:
return 2
if n > 2:
return f(n - 1) + f(n - 2)
# 迭代寫法混滔，或者叫循環(huán)寫法
def f(n):
res = [0 for i in range(n + 1)]
res[1] = 1
res[2] = 2
for i in range(3, n+1):
res[i] = res[i - 1] + res[i - 2]
return res[n]
# 使用緩存
cache = {}
def fib(n):
if n not in cache.keys():
cache[n] = _fib(n)
return cache[n]
def _fib(n):
if n == 1 or n == 2:
return n
else:
return fib(n-1) + fib(n-2)
二分查找
def LinearSearch(array, t):
for i in range(len(array)):
if array[i] == t:
return True
return False
def BinarySearch(array, t):
left = 0
right = len(array) - 1
while left <= right:
mid = int((left + right) / 2)
if array[mid] < t:
left = mid + 1
elif array[mid] > t:
right = mid - 1
else:
return True
return False
array = list(range(100000000))
import time
t1 = time.time()
LinearSearch(array, 100000001)
t2 = time.time()
print('線性查找：', t2 - t1)
t3 = time.time()
BinarySearch(array, 100000001)
t4 = time.time()
print('二分查找：', t4 - t3)
二分查找例題（變種）
題意
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
查找比如16在不在矩陣中洒疚。
解法
class Solution:
# @param matrix, a list of lists of integers
# @param target, an integer
# @return a boolean
def searchMatrix(self, matrix, target):
i = 0
j = len(matrix[0]) - 1
while i < len(matrix) and j >= 0:
if matrix[i][j] == target:
return True
elif matrix[i][j] > target:
j -= 1
else:
i += 1
return False
鏈表
鏈表中最簡單的一種是單向鏈表歹颓，它包含兩個域，一個信息域和一個指針域拳亿。這個鏈接指向列表中的下一個節(jié)點(diǎn)晴股，而最后一個節(jié)點(diǎn)則指向一個空值愿伴。
image
python代碼
# 鏈表中的節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
# 實(shí)例化
A = ListNode('a')
B = ListNode('b')
C = ListNode('c')
A.next = B
B.next = C
# 這樣肺魁，一條鏈表就形成了。
# 'a' -> 'b' -> 'c'
# 遍歷鏈表
tmp = A
while tmp != None:
print(tmp.val)
tmp = tmp.next
# 遞歸遍歷鏈表
def listorder(head):
if head:
print(head.val)
listorder(head.next)
listorder(A)
例題
翻轉(zhuǎn)一條單向鏈表隔节。
例子：
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
解答：
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
dummy = head
tmp = dummy
while head and head.next != None:
dummy = head.next
head.next = dummy.next
dummy.next = tmp
tmp = dummy
return dummy
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
solution = Solution()
reverse_head = solution.reverseList(head)
tmp = reverse_head
while tmp:
print(tmp.val)
tmp = tmp.next
二叉樹
image
python代碼
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
'''
1
/ \
2 3
'''
# root就是一顆二叉樹
中序遍歷(先遍歷左子樹鹅经，再遍歷根節(jié)點(diǎn)，再遍歷右子樹)
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
def inorder(root):
if root:
inorder(root.left)
print(root.val)
inorder(root.right)
前序遍歷(先遍歷根節(jié)點(diǎn)怎诫，再遍歷左子樹瘾晃，再遍歷右子樹)
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def preorder(root):
if root:
print(root.val)
preorder(root.left)
preorder(root.right)
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
preorder(root)
后序遍歷(先遍歷左子樹，再遍歷右子樹幻妓，再遍歷根節(jié)點(diǎn))
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
def postorder(root):
if root:
postorder(root.left)
postorder(root.right)
print(root.val)
測試程序
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def preorder(root):
if root:
print(root.val)
preorder(root.left)
preorder(root.right)
def inorder(root):
if root:
inorder(root.left)
print(root.val)
inorder(root.right)
def postorder(root):
if root:
postorder(root.left)
postorder(root.right)
print(root.val)
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
preorder(root)
inorder(root)
postorder(root)
已知一顆二叉樹的先序遍歷序列為ABCDEFG蹦误，中序遍歷為CDBAEGF，能否唯一確定一顆二叉樹肉津？如果可以强胰，請畫出這顆二叉樹。
A
/ \
B E
/ \
C F
\ /
D G
先序遍歷: ABCDEFG
中序遍歷: CDBAEGF
后序遍歷: DCBGFEA
使用程序根據(jù)二叉樹的先序遍歷和中序遍歷來恢復(fù)二叉樹妹沙。
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def buildTree(preorder, inorder):
if len(preorder) == 0:
return None
if len(preorder) == 1:
return TreeNode(preorder[0])
root = TreeNode(preorder[0])
index = inorder.index(root.val)
root.left = buildTree(preorder[1 : index + 1], inorder[0 : index])
root.right = buildTree(preorder[index + 1 : len(preorder)], inorder[index + 1 : len(inorder)])
return root
preorder_string = 'ABCDEFG'
inorder_string = 'CDBAEGF'
r = buildTree(preorder_string, inorder_string)
preorder(r)
inorder(r)
postorder(r)
棧和隊(duì)列
棧
[圖片上傳失敗...(image-a50703-1532952540811)]
python實(shí)現(xiàn)
class Stack(object):
def __init__(self):
self.stack = []
def pop(self):
if self.is_empty():
return None
else:
return self.stack.pop()
def push(self,val):
return self.stack.append(val)
def peak(self):
if self.is_empty():
return None
else:
return self.stack[-1]
def size(self):
return len(self.stack)
def is_empty(self):
return self.size() == 0
s = Stack()
s.push(1)
s.peak()
s.is_empty()
s.pop()
隊(duì)列
[圖片上傳失敗...(image-5e7134-1532952540811)]
python實(shí)現(xiàn)
class Queue(object):
def __init__(self):
self.queue = []
def enqueue(self,val):
self.queue.insert(0,val)
def dequeue(self):
if self.is_empty():
return None
else:
return self.queue.pop()
def size(self):
return len(self.queue)
def is_empty(self):
return self.size() == 0
q = Queue()
q.enqueue(1)
q.is_empty()
q.dequeue()
使用隊(duì)列模擬棧偶洋。
class StackByQueue(object):
def __init__(self):
self.stack = Queue()
def push(self, val):
self.stack.enqueue(val)
def pop(self):
for i in range(self.stack.size() - 1):
value = self.stack.dequeue()
self.stack.enqueue(value)
return self.stack.dequeue()
使用棧模擬隊(duì)列
class QueueByStack(object):
def __init__(self):
self.queue1 = Stack()
self.queue2 = Stack()
def enqueue(self, val):
self.queue1.push(val)
def dequeue(self):
for i in range(self.queue1.size() - 1):
value = self.queue1.pop()
self.queue2.push(value)
res = self.queue1.pop()
for i in range(self.queue2.size()):
value = self.queue2.pop()
self.queue1.push(value)
return res
插入排序
def insertSort(A):
for j in range(1, len(A)):
key = A[j]
i = j - 1
while i >= 0 and A[i] > key:
A[i + 1] = A[i]
i = i - 1
A[i + 1] = key
return A
A = [5, 2, 4, 6, 1, 3]
print(insertSort(A))
function insertSort(A) {
for (j = 1; j < A.length; j++) {
var key = A[j];
var i = j - 1;
while (i >= 0 && A[i] > key) {
A[i + 1] = A[i];
i = i - 1;
}
A[i + 1] = key;
}
return A;
}
var A = [5, 2, 4, 6, 1, 3];
console.log(insertSort(A));
快速排序
def partition(A, p, r):
x = A[r]
i = p - 1
for j in range(p, r):
if A[j] <= x:
i = i + 1
A[i], A[j] = A[j], A[i]
A[i + 1], A[r] = A[r], A[i + 1]
return i + 1
def quickSort(A, p, r):
if p < r:
q = partition(A, p, r)
quickSort(A, p, q - 1)
quickSort(A, q + 1, r)
A = [2, 8, 7, 1, 3, 5, 6, 4]
quickSort(A, 0, 7)
print(A)
時(shí)間復(fù)雜度
假設(shè)快速排序的時(shí)間復(fù)雜度為f(N)
f(N) = 2 * f(N / 2) + O(N)
f(N) = 2 * (2 * f(N / 4) + O(N/2)) + O(N)
...
f(1) = O(1)
所以f(N) = O(NlogN)
在數(shù)組元素?cái)?shù)量為n的數(shù)組里面尋找第k大的數(shù)
def partition(A, p, r):
x = A[r]
i = p - 1
for j in range(p, r):
if A[j] >= x:
i = i + 1
A[i], A[j] = A[j], A[i]
A[i + 1], A[r] = A[r], A[i + 1]
return i + 1
def findKthLargest(A, p, r, k):
if p <= r:
q = partition(A, p, r)
if k - 1 == q:
return A[q]
elif k - 1 < q:
return findKthLargest(A, p, q - 1, k)
else:
return findKthLargest(A, q + 1, r, k)
A = [2, 8, 7, 1, 3, 5, 6, 4]
ret = findKthLargest(A, 0, 7, 8)
print('ret: ', ret)
