Python
class ListNode:
def __init__(self, val: int):
self.val: int = val # 节点值
self.next: ListNode | None = None # 指向后继节点的引用
self.prev: ListNode | None = None # 指向前驱节点的引用
大约 2 分钟
Python
class MyList:
"""列表类"""
def __init__(self):
"""构造方法"""
self._capacity: int = 10 # 列表容量
self._arr: list[int] = [0] * self._capacity # 数组（存储列表元素）
self._size: int = 0 # 列表长度（当前元素数量）
self._extend_ratio: int = 2 # 每次列表扩容的倍数
def size(self) -> int:
"""获取列表长度（当前元素数量）"""
return self._size
def capacity(self) -> int:
"""获取列表容量"""
return self._capacity
def get(self, index: int) -> int:
"""访问元素"""
# 索引如果越界，则抛出异常，下同
if index < 0 or index >= self._size:
raise IndexError("索引越界")
return self._arr[index]
def set(self, num: int, index: int):
"""更新元素"""
if index < 0 or index >= self._size:
raise IndexError("索引越界")
self._arr[index] = num
def add(self, num: int):
"""在尾部添加元素"""
# 元素数量超出容量时，触发扩容机制
if self.size() == self.capacity():
self.extend_capacity()
self._arr[self._size] = num
self._size += 1
def insert(self, num: int, index: int):
"""在中间插入元素"""
if index < 0 or index >= self._size:
raise IndexError("索引越界")
# 元素数量超出容量时，触发扩容机制
if self._size == self.capacity():
self.extend_capacity()
# 将索引 index 以及之后的元素都向后移动一位
for j in range(self._size - 1, index - 1, -1):
self._arr[j + 1] = self._arr[j]
self._arr[index] = num
# 更新元素数量
self._size += 1
def remove(self, index: int) -> int:
"""删除元素"""
if index < 0 or index >= self._size:
raise IndexError("索引越界")
num = self._arr[index]
# 将索引 index 之后的元素都向前移动一位
for j in range(index, self._size - 1):
self._arr[j] = self._arr[j + 1]
# 更新元素数量
self._size -= 1
# 返回被删除的元素
return num
def extend_capacity(self):
"""列表扩容"""
# 新建一个长度为原数组 _extend_ratio 倍的新数组，并将原数组复制到新数组
self._arr = self._arr + [0] * self.capacity() * (self._extend_ratio - 1)
# 更新列表容量
self._capacity = len(self._arr)
def to_array(self) -> list[int]:
"""返回有效长度的列表"""
return self._arr[: self._size]
大约 9 分钟
Python
class ListNode:
def __init__(self, val: int):
self.val: int = val # 节点值
self.next: ListNode | None = None # 指向后继节点的引用
self.prev: ListNode | None = None # 指向前驱节点的引用
大约 2 分钟
几年前，我在力扣上分享了“剑指 Offer”系列题解，受到了许多读者的鼓励和支持。在与读者交流期间，我最常被问的一个问题是“如何入门算法”。逐渐地，我对这个问题产生了浓厚的兴趣。
两眼一抹黑地刷题似乎是最受欢迎的方法，简单、直接且有效。然而刷题就如同玩“扫雷”游戏，自学能力强的人能够顺利将地雷逐个排掉，而基础不足的人很可能被炸得满头是包，并在挫折中步步退缩。通读教材也是一种常见做法，但对于面向求职的人来说，毕业论文、投递简历、准备笔试和面试已经消耗了大部分精力，啃厚重的书往往变成了一项艰巨的挑战。
如果你也面临类似的困扰，那么很幸运这本书“找”到了你。本书是我对这个问题给出的答案，即使不是最优解，也至少是一次积极的尝试。本书虽然不足以让你直接拿到 Offer，但会引导你探索数据结构与算法的“知识地图”，带你了解不同“地雷”的形状、大小和分布位置，让你掌握各种“排雷方法”。有了这些本领，相信你可以更加自如地刷题和阅读文献，逐步构建起完整的知识体系。
大约 3 分钟
本项目旨在创建一本开源、免费、对新手友好的数据结构与算法入门教程。
- 全书采用动画图解，结构化地讲解数据结构与算法知识，内容清晰易懂，学习曲线平滑。
- 算法源代码皆可一键运行，支持 Python、C++、Java、C#、Go、Swift、JavaScript、TypeScript、Dart、Rust、C 和 Zig 等语言。
- 鼓励读者在线上章节评论区互帮互助、共同进步，提问与评论通常可在两日内得到回复。
读者对象
若你是算法初学者，从未接触过算法，或者已经有一些刷题经验，对数据结构与算法有模糊的认识，在会与不会之间反复横跳，那么本书正是为你量身定制的！
大约 4 分钟
!!! tip
为了获得最佳的阅读体验，建议你通读本节内容。
行文风格约定
- 标题后标注
*的是选读章节，内容相对困难。如果你的时间有限，可以先跳过。 - 专业术语会使用黑体（纸质版和 PDF 版）或添加下划线（网页版），例如数组（array）。建议记住它们，以便阅读文献。
- 重点内容和总结性语句会 加粗，这类文字值得特别关注。
- 有特指含义的词句会使用“引号”标注，以避免歧义。
- 当涉及编程语言之间不一致的名词时，本书均以 Python 为准，例如使用
None来表示“空”。 - 本书部分放弃了编程语言的注释规范，以换取更加紧凑的内容排版。注释主要分为三种类型：标题注释、内容注释、多行注释。
大约 7 分钟
当我们听到“算法”这个词时，很自然地会想到数学。然而实际上，许多算法并不涉及复杂数学，而是更多地依赖基本逻辑，这些逻辑在我们的日常生活中处处可见。
在正式探讨算法之前，有一个有趣的事实值得分享：你已经在不知不觉中学会了许多算法，并习惯将它们应用到日常生活中了。下面我将举几个具体的例子来证实这一点。
例一：查字典。在字典里，每个汉字都对应一个拼音，而字典是按照拼音字母顺序排列的。假设我们需要查找一个拼音首字母为 的字，通常会按照下图所示的方式实现。
大约 3 分钟
算法定义
算法（algorithm）是在有限时间内解决特定问题的一组指令或操作步骤，它具有以下特性。
- 问题是明确的，包含清晰的输入和输出定义。
- 具有可行性，能够在有限步骤、时间和内存空间下完成。
- 各步骤都有确定的含义，在相同的输入和运行条件下，输出始终相同。
数据结构定义
数据结构（data structure）是计算机中组织和存储数据的方式，具有以下设计目标。
- 空间占用尽量少，以节省计算机内存。
- 数据操作尽可能快速，涵盖数据访问、添加、删除、更新等。
- 提供简洁的数据表示和逻辑信息，以便算法高效运行。
大约 5 分钟
在算法设计中，我们先后追求以下两个层面的目标。
- 找到问题解法：算法需要在规定的输入范围内可靠地求得问题的正确解。
- 寻求最优解法：同一个问题可能存在多种解法，我们希望找到尽可能高效的算法。
也就是说，在能够解决问题的前提下，算法效率已成为衡量算法优劣的主要评价指标，它包括以下两个维度。
- 时间效率：算法运行速度的快慢。
- 空间效率：算法占用内存空间的大小。
大约 4 分钟