秋招算法复习
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))
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
思路:沿着对角线,以左下角为例子。如果目标整数大于当前值,则说明目标整数在该列右侧。 如果目标整数小于当前值,则说明目标整数在该行上侧。 如果目标整数等于当前值,则找到。如果从左下角沿着对角线走到右上角,则说明找不到目标整数。
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 False
python不支持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()