学习核心

• 数据结构分类（逻辑结构、物理结构）

  • 按“逻辑结构”：线性结构、非线性结构

    • 线性数据结构：数组、链表、栈、队列、哈希表，元素之间是一对一的顺序关系

    • 非线性数据结构：树、堆、图、哈希表（非线性数据结构可以进一步划分为树形结构和网状结构）

      • 树形结构：树、堆、哈希表，元素之间是一对多的关系

      • 网状结构：图，元素之间是多对多的关系

  • 按“物理结构”：连续、分散

• 数字编码：原码、反码、补码

• 字符编码（ASCII、GBK、Unicode、UTF-8）

学习核心

• 算法学习记录

• todo：leetcode 热题100

• 算法基础：数据结构、复杂度分析、算法

学习核心

学习资料

算法基础概念

什么是算法？

算法（algorithm）是在有限时间内解决特定问题的一组指令或操作步骤，它具有以下特性

• 问题是明确的，包含清晰的输入和输出定义
• 具有可行性，能够在有限步骤、时间和内存空间下完成
• 各步骤都有确定的含义，在相同的输入和运行条件下，输出始终相同

学习核心

学习资料

数组

​ 数组（array）是一种线性数据结构，其将相同类型的元素存储在连续的内存空间中。将元素在数组中的位置称为该元素的索引（index）。下图展示了数组的主要概念和存储方式

1.数组常用操作

初始化数组

​ 可以根据需求选用数组的两种初始化方式：无初始值、给定初始值。

/* 初始化数组 */
int[] arr = new int[5]; // { 0, 0, 0, 0, 0 }
int[] nums = { 1, 3, 2, 5, 4 };

学习核心

• 栈是一种遵循先入后出原则的数据结构，可通过数组或链表来实现
  • 在时间效率方面，栈的数组实现具有较高的平均效率，但在扩容过程中，单次入栈操作的时间复杂度会劣化至 O(n) 。相比之下，栈的链表实现具有更为稳定的效率表现
  • 在空间效率方面，栈的数组实现可能导致一定程度的空间浪费。但需要注意的是，链表节点所占用的内存空间比数组元素更大
• 队列是一种遵循先入先出原则的数据结构，同样可以通过数组或链表来实现
  • 在时间效率和空间效率的对比上，队列的结论与前述栈的结论相似
• 双向队列是一种具有更高自由度的队列，它允许在两端进行元素的添加和删除操作

学习核心

学习资料

哈希表

​ 哈希表（hash table），又称散列表，它通过建立键 key 与值 value 之间的映射，实现高效的元素查询。向哈希表中输入一个键 key ，可以在 O(1) 时间内获取对应的值 value

​ 除哈希表外，数组和链表也可以实现查询功能，它们的效率对比如下所示

• 添加元素：仅需将元素添加至数组（链表）的尾部即可，使用 O(1) 时间
• 查询元素：由于数组（链表）是乱序的，因此需要遍历其中的所有元素，使用 O(n) 时间
• 删除元素：需要先查询到元素，再从数组（链表）中删除，使用 O(n) 时间

学习核心

学习资料

学习核心

学习资料

学习核心

学习资料

学习核心

学习资料