算法 | 故事尾音

秋招算法复习

复习内容

算法

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
            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
        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 iand 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()