不为成仙,只为在这红尘中等你回来。

链表

    链表是由一系列节点组成的元素集合。每个节点包含两部分,数据域 item 和指向下一个节点的指针 next。通过节点之间的相互连接,最终串联成一个链表。

    class Node:
        def __init__(self, item):
            self.item = item
            self.next = None
    

    链表

    创建链表

    class Node:
        def __init__(self, item):
            self.item = item
       ...

    阅读全文>>

2020年11月11日 20:06 作者:nancy 分类:[算法与数据结构] 248

栈和队列的应用——迷宫问题

    给一个二维列表,表示迷宫(0 表示通道,1 表示围墙)。给出算法,求一条走出迷宫的路径。

    maze = [
         [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
         [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
         [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
         [1, 0, 0, 0, 0, 1, 1, 0, 0, 1],
         [1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
         [1,...

    阅读全文>>

2020年11月9日 23:29 作者:nancy 分类:[算法与数据结构] 234

队列

    • 队列(Queue)是一个数据集合,仅允许在列表的一端进行插入,另一端进行删除。
    • 进行插入的一端成为队尾(rear),插入动作称为进队或入队
    • 进行删除的一端成为队头(front),删除动作称为出队
    • 队列的性质:先进先出(First-in, First-out)

    队列的实现方式——环形队列

    • 环形队列:当队尾指针 rear == Maxsize + 1 时,再前进一个位置就自动到 0
      • 队首指针前进 1:front = (front + 1) % Maxsize
      • 队尾指针前进 1:rear ...

    阅读全文>>

2020年11月9日 20:37 作者:nancy 分类:[算法与数据结构] 233

    • 栈(Stack)是一个数据集合,可以理解为只能在一端进行插入或删除操作的列表
    • 栈的特点:后进先出 LIFO(last-in, first-out)
    • 栈的基本操作
      • 进栈(压栈):push
      • 出栈:pop
      • 取栈顶:gettop

    栈的实现

    • 使用一般的列表结构实现栈
      • 进栈:li.append()
      • 出栈:li.pop()
      • 取栈顶:li[-1]
    class Stack:
        def __init__(self):
            self.stack = []
    
        def pu...

    阅读全文>>

2020年11月8日 21:25 作者:nancy 分类:[算法与数据结构] 247

74.Search a 2D Matrix [Medium] [Array | Binary Search]

    题意

    Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
    编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性:

    • Integers in each row are sorted from left to right.
    • 每行中的整数从左到右按升序排列。
    • The first int...

    阅读全文>>

2020年11月7日 16:28 作者:nancy 分类:[LeetCode] 245

基数排序

    基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。

    • 时间复杂度:O(kn)
    • 空间复杂度:O(k+n)
    • k 表示数字位数

    基数排序图解

    def radix_sort(lst):
        max_num = max(lst)
        it = 0  # 最大值 9->1, 99->2, 888->3, 10000->5
        whil...

    阅读全文>>

2020年11月7日 15:15 作者:nancy 分类:[算法与数据结构] 220

桶排序

    • 在计数排序中,如果元素的范围比较大(比如在1到1亿之间),如何改造算法?
    • 桶排序(Bucket Sort):首先将元素分在不同的桶中,在对每个桶中的元素排序。
    • 桶排序的表现取决于数据的分布。也就是需要对不同数据排序时采取不同的分桶策略。

    桶排序图解

    def bucket_sort(lst, n=100, max_num=10000):
        buckets = [[] for _ in range(n)]  # 创建桶
        for val in lst:
            i = min(v...

    阅读全文>>

2020年11月7日 13:24 作者:nancy 分类:[算法与数据结构] 216

计数排序

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

    计数排序

    def count_sort(lst, max_count=100):
        count = [0 for _ in range(max_count+1)] # 生成一个包含 max_count 个零的列表
        for val in lst:
            count[val] += 1
        lst.clear() # 清空原列表
        for ind, val in e...

    阅读全文>>

2020年11月6日 22:50 作者:nancy 分类:[算法与数据结构] 222

希尔排序

    • 希尔排序(shell sort)是一种分组插入排序算法。
    • 首先取一个整数 d₁ = n // 2,将元素分为 d₁ 个组,每组相邻元素之间距离为 d₁,在各组内进行直接插入排序;
    • 取第二个整数 d₂ = d₁ // 2,重复上述分组排序过程,直到 dᵢ = 1,即所有元素在同一组内进行直接插入排序。
    • 希尔排序每趟并不使某些元素有序,而是使整体数据越来越接近有序,最后一趟排序使得所有数据有序。

    希尔排序

    # 希尔排序
    def insert_sort_gap(lst, gap):
        for ...

    阅读全文>>

2020年11月6日 22:15 作者:nancy 分类:[算法与数据结构] 225

归并排序

    归并

    • 假设现在的列表分两段有序,如何将其合成为一个有序列表
    • 这种操作称为一次归并

    归并过程

    归并排序 - 使用归并

    • 分解:将列表越分越小,直至分成一个元素。
    • 终止条件:一个元素是有序的。
    • 合并:将两个有序列表归并,列表越来越大。
    • 时间复杂度:O(nlogn)
    • 空间复杂度:O(n)

    归并排序

    def merge(lst, low, mid, high):
        i = low
        j = mid + 1
        temp = []
        while i <= mid and j <...

    阅读全文>>

2020年11月6日 18:16 作者:nancy 分类:[算法与数据结构] 210