链表

链表是由一系列节点组成的元素集合。每个节点包含两部分，数据域 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 分类：[算法与数据结构] 1756

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

给一个二维列表，表示迷宫（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 分类：[算法与数据结构] 1743

队列

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

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

• 环形队列：当队尾指针 rear == Maxsize + 1 时，再前进一个位置就自动到 0
  • 队首指针前进 1：front = (front + 1) % Maxsize
  • 队尾指针前进 1：rear ...
阅读全文>>

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

栈

• 栈（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 分类：[算法与数据结构] 1551

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] 1533

基数排序

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

• 时间复杂度：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 分类：[算法与数据结构] 1587

桶排序

• 在计数排序中，如果元素的范围比较大（比如在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 分类：[算法与数据结构] 1783

计数排序

• 对列表进行排序，已知列表中的数范围都在 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 分类：[算法与数据结构] 1502

希尔排序

• 希尔排序（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 分类：[算法与数据结构] 1610

归并排序

归并

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



归并排序 - 使用归并

• 分解：将列表越分越小，直至分成一个元素。
• 终止条件：一个元素是有序的。
• 合并：将两个有序列表归并，列表越来越大。
• 时间复杂度：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 分类：[算法与数据结构] 1652