Algorithm

算法基础

算法（Algorithm）：一个计算过程，解决问题的方法。
N.Wirth: “程序=数据结构+算法”

一、时间复杂度

时间复杂度是用来估计算法运行时间的一个式子（单位）
一般来说，时间复杂度高的算法比复杂度低的算法慢。
常见的时间复杂度（按效率排序） O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n²logn) < O(n³)
复杂问题的时间复杂度O(n!) O(2ⁿ) O(nⁿ) …

1、如何简单快速地判断算法复杂度

快速判断算法复杂度（适用于绝大多数简单情况）：
1. 确定问题规模n
2. k层关于n的循环→n^k
3. 循环减半过程→logn
复杂情况：根据算法执行过程判断

二、空间复杂度

空间复杂度：用来评估算法内存占用大小的式子
空间复杂度的表示方式与时间复杂度完全一样
算法使用了几个变量：O(1)
算法使用了长度为n的一维列表：O(n)
算法使用了m行n列的二维列表：O(mn)
“空间换时间”

def hanoi(n, a, b, c):
    if n>0:
        hanoi(n-1, a, c, b)
        print("moving from %s to %s" % (a, c))
        hanoi(n-1, b, a, c)

hanoi(3, 'A', 'B', 'C')
"""
moving from A to C
moving from A to B
moving from C to B
moving from A to C
moving from B to A
moving from B to C
moving from A to C
"""

递归实例：汉诺塔问题

列表查找

查找：在一些数据元素中，通过一定的方法找出与给定关键字相同的数据元素的过程。
列表查找（线性表查找）：从列表中查找指定元素
输入：列表、待查找元素
输出：元素下标（未找到元素时一般返回None或-1）
内置列表查找函数：index()

一、顺序查找 (Linear Search)

顺序查找：也叫线性查找，从列表第1个元素开始，顺序进行搜索，直到找到元素或搜索到列表最后1个元素为止。
时间复杂度：O(n)

from cal_time import *

@cal_time
def linear_search(li, val):
    for ind, v in enumerate(li):
        if v == val:
            return ind
    else:
        return None

@cal_time
def binary_search(li, val):
    left = 0
    right = len(li) - 1
    while left <= right:    # 候选区有值
        mid = (left + right) // 2
        if li[mid] == val:
            return mid
        elif li[mid] > val: # 带查找的值在mid左侧
            right = mid - 1
        else: # li[mid] < val 带查找的值在mid右侧
            left = mid + 1
    else:
        return None

li = list(range(10000000000))
# linear_search(li, 3890000)
binary_search(li, 3890000)

View Code

二、二分查找 (Binary Searh)

二分查找：又叫折半查找，从有序列表的初始候选区li[0:n]开始，通过对待查找的值与候选区中间值的比较，可以使候选区减少一半。
时间复杂度：O(logn)

def bin_search_rec(data_set, value, low, high):
    if low <= high:
        mid = (low + high) // 2
        if data_set[mid] == value:
            return mid
        elif data_set[mid] > value:
            return bin_search_rec(data_set, value, low, mid - 1)
        else:
            return bin_search_rec(data_set, value, mid + 1, high)
    else:
        return

递归版本的二分查找

列表排序

排序：将一组“无序”的记录序列调整为“有序”的记录序列。
列表排序：将无序列表变为有序列表
输入：列表
输出：有序列表
升序与降序
内置排序函数：sort()

一、排序Low B三人组

1、冒泡排序 (Bubble Sort)

列表每两个相邻的数，如果前面比后面大，则交换这两个数。
一趟排序完成后，则无序区减少一个数，有序区增加一个数。
代码关键点：趟、无序区范围
如果冒泡排序中的一趟排序没有发生交换，则说明列表已经有序，可以直接结束算法。
时间复杂度：O(n²)

import time


def cal_time(func):
    def wrapper(*args, **kwargs):
        t1 = time.time()
        result = func(*args, **kwargs)
        t2 = time.time()
        print("%s running time: %s secs." % (func.__name__, t2-t1))
        return result
    return wrapper

计时装饰器

import random
from .timewrap import *

@cal_time
def bubble_sort(li):
    for i in range(len(li) - 1):
        # i 表示趟数
        # 第 i 趟时： 无序区：(0，len(li) - i)
        for j in range(0, len(li) - i - 1):
            if li[j] > li[j+1]:
                li[j], li[j+1] = li[j+1], li[j]

#冒泡排序优化
#如果冒泡排序中执行一趟而没有交换，则列表已经是有序状态，可以直接结束算法。
@cal_time
def bubble_sort_2(li):
    for i in range(len(li) - 1):
        # i 表示趟数
        # 第 i 趟时： 无序区：(0，len(li) - i)
        change = False
        for j in range(0, len(li) - i - 1):
            if li[j] > li[j+1]:
                li[j], li[j+1] = li[j+1], li[j]
                change = True
        if not change:
            return

li = list(range(10000))
# random.shuffle(li)
# print(li)
bubble_sort_2(li)
print(li)

'''
列表每两个相邻的数，如果前边的比后边的大，那么交换这两个数
时间复杂度O(n2)
'''

View Code

2、选择排序 (Select Sort)

一趟排序记录最小的数，放到第一个位置
再一趟排序记录记录列表无序区最小的数，放到第二个位置
……
算法关键点：有序区和无序区、无序区最小数的位置
时间复杂度：O(n²)

def select_sort_simple(li):  #不推荐
    li_new = []
    for i in range(len(li)):
        min_val = min(li)
        li_new.append(min_val)
        li.remove(min_val)
    return li_new


import random
from .timewrap import *

@cal_time
def select_sort(li):
    for i in range(len(li) - 1):
        # i 表示趟数，也表示无序区开始的位置
        min_loc = i   # 最小数的位置
        for j in range(i + 1, len(li) - 1):
            if li[j] < li[min_loc]:
                min_loc = j
        li[i], li[min_loc] = li[min_loc], li[i]


li = list(range(10000))
random.shuffle(li)
print(li)
select_sort(li)
print(li)


'''
一趟遍历记录最小的数，放到第一个位置；
再一趟遍历记录剩余列表中最小的数，继续放置；
时间复杂度：O(n2)
'''

View Code

3、插入排序

初始时手里(有序区)只有一张牌
每次(从无序区)摸一张牌，插入到手里已有牌的正确位置
时间复杂度：O(n²)

import random
from .timewrap import *

@cal_time
def insert_sort(li):
    for i in range(1, len(li)):
        # i 表示无序区第一个数
        tmp = li[i] # 摸到的牌
        j = i - 1 # j 指向有序区最后位置
        while li[j] > tmp and j >= 0:
            #循环终止条件： 1. li[j] <= tmp; 2. j == -1
            li[j+1] = li[j]
            j -= 1
        li[j+1] = tmp


li = list(range(10000))
random.shuffle(li)
print(li)
insert_sort(li)
print(li)

'''
列表被分为有序区和无序区两个部分。最初有序区只有一个元素。
每次从无序区选择一个元素，插入到有序区的位置，直到无序区变空。
O(n2)

'''

View Code

二、排序NB三人组

1、快速排序

快速排序：
- 快
快排思路：
1. 取一个元素p（第一个元素），使元素p归位；
2. 列表被p分成两部分，左边都比p小，右边都比p大；
3. 递归完成排序。
时间复杂度：
1. 时间复杂度：O(nlogn)
问题：
1. 最坏情况
2. 递归

import random
from .timewrap import *
import copy
import sys


sys.setrecursionlimit(100000)

def partition(li, left, right):
    # ri = random.randint(left, right)
    # li[left], li[ri] = li[ri], li[left]
    tmp = li[left]
    while left < right:
        while left < right and li[right] >= tmp:
            right -= 1
        li[left] = li[right]
        while left < right and li[left] <= tmp:
            left += 1
        li[right] = li[left]
    li[left] = tmp
    return left


def _quick_sort(li, left, right):
    if left < right:    # 至少有两个元素
        mid = partition(li, left, right)
        _quick_sort(li, left, mid-1)
        _quick_sort(li, mid+1, right)

@cal_time
def quick_sort(li):
    return _quick_sort(li, 0, len(li)-1)

@cal_time
def sys_sort(li):
    li.sort()

li = list(range(100000))
random.shuffle(li)


#sys_sort(li1)
quick_sort(li)


''''
快速排序：快
快排思路：
取一个元素p（第一个元素），使元素p归位；
列表被p分成两部分，左边都比p小，右边都比p大；
递归完成排序。
时间复杂度:一般为O(nlgn) 最坏情况为O(n2)
'''

View Code

2、堆排序

堆：一种特殊的完全二叉树结构
大根堆：一棵完全二叉树，满足任一节点都比其孩子节点大
小根堆：一棵完全二叉树，满足任一节点都比其孩子节点小
堆的向下调整性质：
1. 假设根节点的左右子树都是堆，但根节点不满足堆的性质
2. 可以通过一次向下的调整来将其变成一个堆。
堆排序过程：
1. 建立堆
2. 得到堆顶元素，为最大元素
3. 去掉堆顶，将堆最后一个元素放到堆顶，此时可通过一次调整重新使堆有序。
4. 堆顶元素为第二大元素。
5. 重复步骤3，直到堆变空。
Python内置模块：
1. heapq
常用函数：
1. heapify(x)
2. heappush(heap, item)
3. heappop(heap)
优先队列：
1. 一些元素的集合，POP操作每次执行都会从优先队列中弹出最大（或最小）的元素。
topk问题：
1. 现在有n个数，设计算法得到前k大的数。（k<n）
2. 解决思路：排序后切片 O(nlogn)
3. 解决思路：排序LowB三人组 O(mn)
4. 取列表前k个元素建立一个小根堆。堆顶就是目前第k大的数。
5. 依次向后遍历原列表，对于列表中的元素，如果小于堆顶，则忽略该元素；如果大于堆顶，则将堆顶更换为该元素，并且对堆进行一次调整；
6. 遍历列表所有元素后，倒序弹出堆顶
时间复杂度：O(nlogn)

from .timewrap import *
import random

def _sift(li, low, high):
    """
    :param li:
    :param low: 堆根节点的位置
    :param high: 堆最有一个节点的位置
    :return:
    """
    i = low  # 父亲的位置
    j = 2 * i + 1  # 孩子的位置
    tmp = li[low]  # 原省长
    while j <= high:
        if j + 1 <= high and li[j + 1] > li[j]:  # 如果右孩子存在并且右孩子更大
            j += 1
        if tmp < li[j]:  # 如果原省长比孩子小
            li[i] = li[j]  # 把孩子向上移动一层
            i = j
            j = 2 * i + 1
        else:
            li[i] = tmp  # 省长放到对应的位置上(干部)
            break
    else:
        li[i] = tmp  # 省长放到对应的位置上(村民/叶子节点)


def sift(li, low, high):
    """
    :param li:
    :param low: 堆根节点的位置
    :param high: 堆最有一个节点的位置
    :return:
    """
    i = low         # 父亲的位置
    j = 2 * i + 1   # 孩子的位置
    tmp = li[low]   # 原省长
    while j <= high:
        if j + 1 <= high and li[j+1] > li[j]: # 如果右孩子存在并且右孩子更大
            j += 1
        if tmp < li[j]: # 如果原省长比孩子小
            li[i] = li[j]  # 把孩子向上移动一层
            i = j
            j = 2 * i + 1
        else:
            break
    li[i] = tmp


@cal_time
def heap_sort(li):
    n = len(li)
    # 1. 建堆
    for i in range(n//2-1, -1, -1):
        sift(li, i, n-1)
    # 2. 挨个出数
    for j in range(n-1, -1, -1):    # j表示堆最后一个元素的位置
        li[0], li[j] = li[j], li[0]
        # 堆的大小少了一个元素 （j-1）
        sift(li, 0, j-1)


li = list(range(10000))
random.shuffle(li)
heap_sort(li)
print(li)

# li=[2,9,7,8,5,0,1,6,4,3]
# sift(li, 0, len(li)-1)
# print(li)

''''
建立堆
得到堆顶元素，为最大元素
去掉堆顶，将堆最后一个元素放到堆顶，此时可通过一次调整重新使堆有序。
堆顶元素为第二大元素。
重复步骤3，直到堆变空。

时间复杂度O(nlgn)
'''

View Code

import heapq, random

li = [5,8,7,6,1,4,9,3,2]

heapq.heapify(li)
print(heapq.heappop(li))
print(heapq.heappop(li))

def heap_sort(li):
    heapq.heapify(li)
    n = len(li)
    new_li = []
    for i in range(n):
        new_li.append(heapq.heappop(li))
    return new_li

li = list(range(10000))
random.shuffle(li)
# li = heap_sort(li)
# print(li)

print(heapq.nlargest(100, li))

View Code

def sift(li, low, high):
    i = low
    j = 2 * i + 1
    tmp = li[low]
    while j <= high:
        if j + 1 <= high and li[j+1] < li[j]:
            j = j + 1
        if li[j] < tmp:
            li[i] = li[j]
            i = j
            j = 2 * i + 1
        else:
            break
        li[i] = tmp


def topk(li, k):
    heap = li[0:k]
    # 1.建堆
    for i in range((k-2)//2, -1, -1):
        sift(heap, i, k-1)
    # 2.遍历
    for i in range(k, len(li)-1):
        if li[i] > heap[0]:
            heap[0] = li[i]
            sift(heap, 0, k-1)
    # 3.出数
    for i in range(k-1, -1, -1):
        heap[0], heap[i] = heap[i], heap[0]
        sift(heap, 0, i - 1)    
    return heap

import random
li = list(range(1000))
random.shuffle(li)

print(topk(li, 10))

topk

3、归并排序

假设现在的列表分两段有序，如何将其合成为一个有序列表这种操作称为一次归并
分解：将列表越分越小，直至分成一个元素。
终止条件：一个元素是有序的。
合并：将两个有序列表归并，列表越来越大
时间复杂度：O(nlogn)

import random
from timewrap import *
import copy
import sys


def merge(li, low, mid, high):
    i = low
    j = mid + 1
    ltmp = []
    while i <= mid and j <= high:
        if li[i] < li[j]:
            ltmp.append(li[i])
            i += 1
        else:
            ltmp.append(li[j])
            j += 1
    while i <= mid:
        ltmp.append(li[i])
        i += 1
    while j <= high:
        ltmp.append(li[j])
        j += 1
    li[low:high+1] = ltmp


def _merge_sort(li, low, high):
    if low < high:  # 至少两个元素
        mid = (low + high) // 2
        _merge_sort(li, low, mid)
        _merge_sort(li, mid+1, high)
        merge(li, low, mid, high)
        print(li[low:high+1])


def merge_sort(li):
    return _merge_sort(li, 0, len(li)-1)


li = list(range(16))
random.shuffle(li)
print(li)
merge_sort(li)

print(li)

View Code

NB三人组小结

时间复杂度都是O(nlogn)
一般情况下，就运行时间而言：快速排序 < 归并排序 < 堆排序
三种排序算法的缺点：
1. 快速排序：极端情况下排序效率低
2. 归并排序：需要额外的内存开销
3. 堆排序：在快的排序算法中相对较慢

三、其他排序

1、希尔排序

希尔排序(Shell Sort)是一种分组插入排序算法。
首先取一个整数d₁=n/2，将元素分为d1个组，每组相邻量元素之间距离为d₁，在各组内进行直接插入排序；
取第二个整数d₂=d₁/2，重复上述分组排序过程，直到d_i=1，即所有元素在同一组内进行直接插入排序。
希尔排序每趟并不使某些元素有序，而是使整体数据越来越接近有序；最后一趟排序使得所有数据有序。
希尔排序的时间复杂度讨论比较复杂，并且和选取的gap序列有关。

def insert_sort(li):
    for i in range(1, len(li)):
        # i 表示无序区第一个数
        tmp = li[i] # 摸到的牌
        j = i - 1 # j 指向有序区最后位置
        while li[j] > tmp and j >= 0:
            #循环终止条件： 1. li[j] <= tmp; 2. j == -1
            li[j+1] = li[j]
            j -= 1
        li[j+1] = tmp

def shell_sort(li):
    d = len(li) // 2
    while d > 0:
        for i in range(d, len(li)):
            tmp = li[i]
            j = i - d
            while li[j] > tmp and j >= 0:
                li[j+d] = li[j]
                j -= d
            li[j+d] = tmp
        d = d >> 1

View Code

2、计数排序

对列表进行排序，已知列表中的数范围都在0到100之间。设计时间复杂度为O(n)的算法

# 0 0 1 1 2 4 3 3 1 4 5 5
import random
import copy
from timewrap import *

@cal_time
def count_sort(li, max_num = 100):
    count = [0 for i in range(max_num+1)]
    for num in li:
        count[num]+=1
    li.clear()
    for i, val in enumerate(count):
        for _ in range(val):
            li.append(i)

@cal_time
def sys_sort(li):
    li.sort()

li = [random.randint(0,100) for i in range(100000)]
li1 = copy.deepcopy(li)
count_sort(li)
sys_sort(li1)

View Code

3、桶排序

在计数排序中，如果元素的范围比较大（比如在1到1亿之间），如何改造算法？
桶排序(Bucket Sort)：首先将元素分在不同的桶中，在对每个桶中的元素排序。
桶排序的表现取决于数据的分布。也就是需要对不同数据排序时采取不同的分桶策略。
平均情况时间复杂度：O(n+k)
最坏情况时间复杂度：O(n²k)
空间复杂度：O(nk)

4、基数排序

多关键字排序：加入现在有一个员工表，要求按照薪资排序，年龄相同的员工按照年龄排序。
先按照年龄进行排序，再按照薪资进行稳定的排序。
时间复杂度：O(kn)
空间复杂度：O(k+n)
k表示数字位数
https://leetcode.com/problemset/all/

import random
from .timewrap import *

def list_to_buckets(li, iteration):
    """
    :param li: 列表
    :param iteration: 装桶是第几次迭代
    :return:
    """
    buckets = [[] for _ in range(10)]
    for num in li:
        digit = (num // (10 ** iteration)) % 10
        buckets[digit].append(num)
    return buckets

def buckets_to_list(buckets):
    return [num for bucket in buckets for num in bucket]
    # li = []
    # for bucket in buckets:
    #     for num in bucket:
    #         li.append(num)

@cal_time
def radix_sort(li):
    maxval = max(li) # 10000
    it = 0
    while 10 ** it <= maxval:
        li = buckets_to_list(list_to_buckets(li, it))
        it += 1
    return li

li = [random.randint(0,1000) for _ in range(100000)]
radix_sort(li)

View Code

给定一个升序列表和一个整数，返回该整数在列表中的下标范围

def twoSum(nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[int]
    """
    for i in range(len(nums)):
        for j in range(i+1,len(nums)):
            if nums[i]+nums[j] == target:
                return [i,j]

View Code

def twoSum(nums, target):

    d = {}
    for i in range(len(nums)):
        if target - nums[i] in d:
                return i, d[target-nums[i]]
        else:
            d[nums[i]] = i

View Code

找出第k大的数

def partition(array, left, right):
    well = left
    for i in range(left, right):
        if array[i] > array[right]:
            array[i], array[well] = array[well], array[i]
            well += 1
    array[well], array[right] = array[right], array[well]
    return well

def findk(l,low,high,k):
    if low<=high:
        mid=partition(l, low, high)
        if mid==len(l)-k:
            res=l[mid]
            return res
        elif mid>len(l)-k:
            return findk(l,low,mid-1,k)
        else:
            return findk(l,mid+1,high,k)



l=[1,23,4,5,64,68,12,45,666,999,69]
res=findk(l,0,len(l)-1,6)
print("res:",res,l)

View Code

def kp(data, left, right):
    tem = data[left]
    while left < right:
        while left < right and data[right] >= tem:
            right -= 1
        data[left] = data[right]
        while left < right and data[left] <= tem:
            left += 1
        data[right] = data[left]

    data[right] = tem
    return left

def qk(data, left, right):
    if left <right:
        mid = kp(data, left,right)
        qk(data,left, mid-1)
        qk(data,mid+1, right)




k=5
data = [1, 23, 4, 5, 64, 68, 12, 45, 666, 999, 69]
qk(data, 0, len(data)-1)
data.reverse()
print(data)
print(data[len(data) -1-k-1])

View Code

贪心算法

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。
贪心算法并不保证会得到最优解，但是在某些问题上贪心算法的解就是最优解。要会判断一个问题能否用贪心算法来计算。

一、找零问题

假设商店老板需要找零n元钱，钱币的面额有：100元、50元、 20元、5元、1元，如何找零使得所需钱币的数量最少？

二、背包问题

一个小偷在某个商店发现有n个商品，第i个商品价值v_i元，重w_i千克。他希望拿走的价值尽量高，但他的背包最多只能容纳W千克的东西。他应该拿走哪些商品？
0-1背包：对于一个商品，小偷要么把它完整拿走，要么留下。不能只拿走一部分，或把一个商品拿走多次。（商品为金条）
分数背包：对于一个商品，小偷可以拿走其中任意一部分。（商品为金砂）

三、拼接最大数字问题

有n个非负整数，将其按照字符串拼接的方式拼接为一个整数。如何拼接可以使得得到的整数最大？

四、活动选择问题

假设有n个活动，这些活动要占用同一片场地，而场地在某时刻只能供已个活动使用。
每个活动都有一个开始时间s_i和结束时间f_i（题目中时间以整数表示）,表示活动在[s_i, f_i)区间占用场地。
问：安排哪些活动能够使该场地举办的活动的个数最多？
贪心结论：最先结束的活动一定是最优解的一部分。
证明：假设a是所有活动中最先结束的活动，b是最优解中最先结束的活动。
如果a=b，结论成立。
如果a≠b，则b的结束时间一定晚于a的结束时间，则此时用a替换掉最优解中的b，a一定不与最优解中的其他活动时间重叠，因此替换后的解也是最优解

t = [100, 50, 20, 5]

def change(t, n):
    m = [0 for _ in range(len(t))]
    for i, money in enumerate(t):
        m[i] = n // money
        n = n % money
    return m, n

print(change(t, 376))

change_money

goods = [(60, 10),(100, 20),(120, 30)]  # 每个商品元组表示(价格, 重量)
goods.sort(key=lambda x: x[0]/x[1], reverse=True)


def fractional_backpack(goods, w):
    m = [0 for _ in range(len(goods))]
    total_v = 0
    for i, (prize, weight) in enumerate(goods):
        if w >= weight:
            m[i] = 1
            total_v += prize
            w -= weight
        else:
            m[i] = w / weight
            total_v += m[i] * prize
            w = 0
            break
    return total_v, m

print(fractional_backpack(goods, 50))

fractional_backpack

from functools import cmp_to_key

li = [32, 94, 128, 1286, 6, 71]

def xy_cmp(x, y):
    if x+y < y+x:
        return 1
    elif x+y > y+x:
        return -1
    else:
        return 0

def number_join(li):
    li = list(map(str, li))
    li.sort(key=cmp_to_key(xy_cmp))
    return "".join(li)

print(number_join(li))

number_join

activities = [(1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), (8,11), (8,12), (2,14), (12,16)]
# 保证活动是按照结束时间排好序的
activities.sort(key=lambda x:x[1])

def activity_selection(a):
    res = [a[0]]
    for i in range(1, len(a)):
        if a[i][0] >= res[-1][1]:   # 当前活动的开始时间小于等于最后一个入选活动的结束时间
            # 不冲突
            res.append(a[i])
    return res

print(activity_selection(activities))

activity_selection

动态规划

从斐波那契数列看动态规划
斐波那契数列：F_n= F_n−1 + F_n−2
练习：使用递归和非递归的方法来求解斐波那契数列的第n项

一、钢条切割问题

二、动态规划问题关键特征

最优子结构：

原问题的最优解中涉及多少个子问题
在确定最优解使用哪些子问题时，需要考虑多少种选择

重叠子问题

三、最长公共子序列

# 子问题的重复计算
def fibnacci(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fibnacci(n-1) + fibnacci(n-2)


# 动态规划（DP）的思想 = 递推式 + 重复子问题
def fibnacci_no_recurision(n):
    f = [0,1,1]
    if n > 2:
        for i in range(n-2):
            num = f[-1] + f[-2]
            f.append(num)
    return f[n]

print(fibnacci_no_recurision(100))

fibnacci

import time


def cal_time(func):
    def wrapper(*args, **kwargs):
        t1 = time.time()
        result = func(*args, **kwargs)
        t2 = time.time()
        print("%s running time: %s secs." % (func.__name__, t2 - t1))
        return result
    return wrapper


p = [0, 1, 5, 8, 9, 10, 17, 17, 20, 21, 23, 24, 26, 27, 27, 28, 30, 33, 36, 39, 40]
# p = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]


def cut_rod_recurision_1(p, n):
    if n == 0:
        return 0
    else:
        res = p[n]
        for i in range(1, n):
            res = max(res, cut_rod_recurision_1(p, i) + cut_rod_recurision_1(p, n-i))
        return res

@cal_time
def c1(p, n):
    return cut_rod_recurision_1(p, n)


def cut_rod_recurision_2(p, n):
    if n == 0:
        return 0
    else:
        res = 0
        for i in range(1, n+1):
            res = max(res, p[i] + cut_rod_recurision_2(p, n-i))
        return res

@cal_time
def c2(p,n):
    return cut_rod_recurision_2(p, n)


@cal_time
def cut_rod_dp(p, n):
    r = [0]
    for i in range(1, n+1):
        res = 0
        for j in range(1, i+1):
            res = max(res, p[j] + r[i - j])
        r.append(res)
    return r[n]


def cut_rod_extend(p, n):
    r = [0]
    s = [0]
    for i in range(1, n+1):
        res_r = 0 # 价格的最大值
        res_s = 0 # 价格最大值对应方案的左边不切割部分的长度
        for j in range(1, i + 1):
            if p[j] + r[i - j] > res_r:
                res_r = p[j] + r[i - j]
                res_s = j
        r.append(res_r)
        s.append(res_s)
    return r[n], s


def cut_rod_solution(p, n):
    r, s = cut_rod_extend(p, n)
    ans = []
    while n > 0:
        ans.append(s[n])
        n -= s[n]
    return ans


r, s = cut_rod_extend(p,20)
print(s)

print(cut_rod_dp(p, 20))
print(cut_rod_solution(p, 20))

cut_rod

def lcs_length(x, y):
    m = len(x)
    n = len(y)
    c = [[0 for _ in range(n+1)] for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if x[i-1] == y[j-1]:    # i j 位置上的字符匹配的时候，来自于左上方+1
                c[i][j] = c[i-1][j-1] + 1
            else:
                c[i][j] = max(c[i-1][j], c[i][j-1])
    return c[m][n]

def lcs(x, y):
    m = len(x)
    n = len(y)
    c = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
    b = [[0 for _ in range(n + 1)] for _ in range(m + 1)] # 1 左上方 2 上方 3 左方
    for i in range(1, m+1):
        for j in range(1, n+1):
            if x[i-1] == y[j-1]:    # i j 位置上的字符匹配的时候，来自于左上方+1
                c[i][j] = c[i-1][j-1] + 1
                b[i][j] = 1
            elif c[i-1][j] > c[i][j-1]: # 来自于上方
                c[i][j] = c[i-1][j]
                b[i][j] = 2
            else:
                c[i][j] = c[i][j-1]
                b[i][j] = 3
    return c[m][n], b


def lcs_trackback(x, y):
    c, b = lcs(x, y)
    i = len(x)
    j = len(y)
    res = []
    while i > 0 and j > 0:
        if b[i][j] == 1:    # 来自左上方=>匹配
            res.append(x[i-1])
            i -= 1
            j -= 1
        elif b[i][j] == 2:  # 来自于上方=>不匹配
            i -= 1
        else: # ==3 来自于左方=>不匹配
            j -= 1
    return "".join(reversed(res))


print(lcs_trackback("ABCBDAB", "BDCABA"))

lcs

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


def gcd2(a, b):
    while b > 0:
        r = a % b
        a = b
        b = r
    return a


print(gcd2(12,16))

gcd

class Fraction:
    def __init__(self, a, b):
        self.a = a
        self.b = b
        x = self.gcd(a,b)
        self.a /= x
        self.b /= x

    def gcd(self, a, b):
        while b > 0:
            r = a % b
            a = b
            b = r
        return a

    def zgs(self, a, b):
        # 12 16 -> 4
        # 3*4*4=48
        x = self.gcd(a, b)
        return a * b / x

    def __add__(self, other):
        a = self.a
        b = self.b
        c = other.a
        d = other.b
        fenmu = self.zgs(b, d)
        fenzi = a * fenmu / b + c * fenmu / d
        return Fraction(fenzi, fenmu)



    def __str__(self):
        return "%d/%d" % (self.a, self.b)


a = Fraction(1,3)
b = Fraction(1,2)
print(a+b)

fraction

欧几里得算法

一、最大公约数

约数：如果整数a能被整数b整除，那么a叫做b的倍数，b叫做 a的约数。
给定两个整数a,b，两个数的所有公共约数中的最大值即为最大公约数（Greatest Common Divisor, GCD）。
例：12与16的最大公约数是4

RSA加密算法简介

传统密码：加密算法是秘密的
现代密码系统：加密算法是公开的，密钥是秘密的
对称加密系统
非对称加密系统:
1. 公钥：用来加密，是公开的
2. 私钥：用来解密，是私有的

一、RSA加密算法过程

随机选取两个质数p和q
计算n=pq
选取一个与φ(n)互质的小奇数e,φ(n)=(p-1)(q-1)
对模φ(n),计算e的乘法逆元d，即满足 (e*d) mod φ(n) = 1
公钥(e, n) 私钥(d, n)
加密过程：c = (m^e) mod n
解密过程：m = (c^d) mod n