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

链表

    链表是由一系列节点组成的元素集合。每个节点包含两部分,数据域 item 和指向下一个节点的指针 next。通过节点之间的相互连接,最终串联成一个链表。 ```python class Node: def __init__(self, item): self.item = item self.next = None ``` ![链表](http://qiniuyun.iamnancy.top/linklist.png) ##...

    阅读全文>>

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

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

    给一个二维列表,表示迷宫(0 表示通道,1 表示围墙)。给出算法,求一条走出迷宫的路径。 ```python 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...

    阅读全文>>

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

队列

    - 队列(Queue)是一个数据集合,仅允许在列表的一端进行插入,另一端进行删除。 - 进行插入的一端成为队尾(rear),插入动作称为进队或入队 - 进行删除的一端成为队头(front),删除动作称为出队 - 队列的性质:先进先出(First-in, First-out) ### 队列的实现方式——环形队列 - 环形队列:当队尾指针 `rear == Maxsize + 1` 时,再前进一个位置就自动到 0 - 队首指针前进 1:`front = (front + 1)...

    阅读全文>>

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

    - 栈(Stack)是一个数据集合,可以理解为只能在一端进行插入或删除操作的列表 - 栈的特点:后进先出 LIFO(last-in, first-out) - 栈的基本操作 - 进栈(压栈):push - 出栈:pop - 取栈顶:gettop ### 栈的实现 - 使用一般的列表结构实现栈 - 进栈:`li.append()` - 出栈:`li.pop()` - 取栈顶:`li[-1]` ```python class Stack: ...

    阅读全文>>

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

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. - 每行中的整数从左到右按升序排列...

    阅读全文>>

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

基数排序

    基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。 - 时间复杂度:O(kn) - 空间复杂度:O(k+n) - k 表示数字位数 ![基数排序图解](http://qiniuyun.iamnancy.top/radixSort.gif) ```python def radix_sort(lst): max_num...

    阅读全文>>

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

桶排序

    - 在计数排序中,如果元素的范围比较大(比如在1到1亿之间),如何改造算法? - 桶排序(Bucket Sort):首先将元素分在不同的桶中,在对每个桶中的元素排序。 - 桶排序的表现取决于数据的分布。也就是需要对不同数据排序时采取不同的分桶策略。 ![桶排序图解](http://qiniuyun.iamnancy.top/Bucket_sort.png) ```python def bucket_sort(lst, n=100, max_num=10000): ...

    阅读全文>>

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

计数排序

    - 对列表进行排序,已知列表中的数范围都在 0 到 100 之间。设计时间复杂度为 O(n) 的算法。 ![计数排序](http://qiniuyun.iamnancy.top/countingSort.gif) ```python def count_sort(lst, max_count=100): count = [0 for _ in range(max_count+1)] # 生成一个包含 max_count 个零的列表 for val in lst...

    阅读全文>>

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

希尔排序

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

    阅读全文>>

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

归并排序

    ### 归并 - 假设现在的列表分两段有序,如何将其合成为一个有序列表 - 这种操作称为一次归并 ![归并过程](http://qiniuyun.iamnancy.top/merge.png) ### 归并排序 - 使用归并 - 分解:将列表越分越小,直至分成一个元素。 - 终止条件:一个元素是有序的。 - 合并:将两个有序列表归并,列表越来越大。 - 时间复杂度:O(nlogn) - 空间复杂度:O(n) ![归并排序](http://qiniuyun.i...

    阅读全文>>

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