算法
秋招算法复习
复习内容
算法
1、排序算法：快速排序、归并排序、计数排序 2、搜索算法：回溯、递归、剪枝 3、图论：最短路径、最小生成树、网络流建模 4、动态规划：背包问题、最长子序列、计数问题 5、基础技巧：分治、倍增、二分法、贪心算法
数据结构
1、数组和链表 2、栈与队列 3、树和图 4、哈希表 5、大/小跟堆，可并堆 6、字符串：字典树、后缀树
排序算法
快速排序
递归写法
def quick_sort(data):
if len(data) < 2:
return data
base = data[0]
left = [i for i in data[1:] if i <= base]
right = [i for i in data[1:] if i > base]
return quick_sort(left) + [base] + quick_sort(right)
if __name__ == "__main__":
data = [1,2,3,4,3,5,2,8,1,4]
print(quick_sort(data))双指针写法
归并排序
堆排序
计数排序
查找算法
二分查找
非递归
def binary_search(data,value):
left = 0
right = len(data)-1
while left<=right:
mid = (left+right)//2
if value == data[mid]:
return mid
if value<data[mid]:
right = mid -1
if value>data[mid]:
left = mid +1
return None
if __name__ == "__main__":
print(binary_search([1,2,3,4,5,6],5))递归
def binary_search(data,left, right, value):
if left>right:
return -1
mid = (left+right)//2
if value == data[mid]:
return mid
if value<data[mid]:
right = mid -1
if value>data[mid]:
left = mid +1
return binary_search(data, left, right, value)
if __name__ == "__main__":
print(binary_search([1,2,3,4,5,6],0,5,5))剑指offer
二维数组中的查找
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
思路：沿着对角线，以左下角为例子。如果目标整数大于当前值，则说明目标整数在该列右侧。 如果目标整数小于当前值，则说明目标整数在该行上侧。 如果目标整数等于当前值，则找到。如果从左下角沿着对角线走到右上角，则说明找不到目标整数。
def Find(target, array):
rows = len(array)
cols = len(array[0])
i,j = 0,cols-1
while i<rows and j>=0:
if array[i][j] == target:
return True
if array[i][j] > target:
j -= 1
else:
i += 1
return Falsepython不支持i++这种写法，改用i+=1
替换空格
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
思路：空格一个字符，替换后变成3个字符，因此字符串变长了，应该从后向前替换。
class Solution:
def replace_space(self, s):
result = ''
for i in range(len(s)-1, -1, -1):
if s[i] == ' ':
result = '%20' + result
else:
result = s[i] + result
return result从尾到头打印链表
输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
思路: (栈):读入数组，逆序输出
class Solution:
# 返回从尾部到头部的列表值序列，例如[1,2,3]
def printListFromTailToHead(self, listNode):
# write code here
temp = list()
current_node = listNode
while current_node != None:
temp.append(current_node.val)
current_node = current_node.next
return temp[::-1]重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
思路：前序遍历第一个是根节点，在中序遍历中根据根节点可划分左右子树
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回构造的TreeNode根节点
def reConstructBinaryTree(self, pre, tin):
# write code here
if not pre or not tin:
return None
root = TreeNode(pre.pop(0))
index = tin.index(root.val)
root.left = self.reConstructBinaryTree(pre, tin[:index])
root.right = self.reConstructBinaryTree(pre, tin[index + 1:])
return root用两个栈实现队列
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.stack1 = []
self.stack2 = []
def push(self, node):
# write code here
self.stack1.append(node)
def pop(self):
# return xx
if len(self.stack2) == 0:
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2.pop()