[数据结构与算法]LeetCode算题准备内容

一、数据结构与算法

????????算法 + 数据结构 = 程序

????????算法（Algorithm） 就是解决问题的方法或者过程

????????数据结构（Data Structure） 是数据的计算机表示和相应的一组操作。

????????程序（Program） 则是算法和数据结构的具体实现。

1.1?数据结构

????????数据结构（Data Structure）：带有结构特性的数据元素的集合。

????????简单而言：「数据结构」?指的是?数据的组织结构，用来组织、存储数据。

????????数据结构有??「逻辑结构」?和?「物理结构」

1.1.1数据的逻辑结构

????????逻辑结构（Logical Structure）：数据元素之间的相互关系

????????根据元素之间具有的不同关系，通常我们可以将数据的逻辑结构分为以下四种：

①?集合结构

• 集合结构：数据元素同属于一个集合，除此之外无其他关系。

集合结构中的数据元素是无序的，并且每个数据元素都是唯一的，集合中没有相同的数据元素。集合结构很像数学意义上的「集合」。

②线性结构

• 线性结构：数据元素之间是「一对一」关系。

线性结构中的数据元素（除了第一个和最后一个元素），左侧和右侧分别只有一个数据与其相邻。线性结构类型包括：数组、链表，以及由它们衍生出来的栈、队列、哈希表

③树形结构?

• 树形结构：数据元素之间是「一对多」的层次关系。

最简单的树形结构是二叉树。这种结构可以简单的表示为：根， 左子树， 右子树。 左子树和右子树又有自己的子树。当然除了二叉树，树形结构类型还包括：多叉树、字典树等。

④图形结构

• 图形结构：数据元素之间是「多对多」的关系。

图形结构是一种比树形结构更复杂的非线性结构，用于表示物件与物件之间的关系。一张图由一些小圆点（称为?顶点?或?结点）和连结这些圆点的直线或曲线（称为?边）组成。

在图形结构中，任意两个结点之间都可能相关，即结点之间的邻接关系可以是任意的。图形结构类型包括：无向图、有向图、连通图等

1.2 数据的物理结构

????????物理结构（Physical Structure）：数据的逻辑结构在计算机中的存储方式。

计算机内有多种存储结构，采用最多的是这两种结构：顺序存储结构、链式存储结构。

①顺序存储结构

????????顺序存储结构（Sequential Storage Structure）：将数据元素存放在一片地址连续的存储单元里，数据元素之间的逻辑关系通过数据元素的存储地址来直接反映。

????????在顺序存储结构中，逻辑上相邻的数据元素在物理地址上也必然相邻 。

这种结构的优点是：简单、易理解，且实际占用最少的存储空间。

缺点是：需要占用一片地址连续的存储单元；并且存储分配要事先进行；

另外对于一些操作的时间效率较低（移动、删除元素等操作）

②链式存储结构

链式存储结构（Linked Storage Structure）：将数据元素存放在任意的存储单元里，存储单元可以连续，也可以不连续。

????????链式存储结构中，逻辑上相邻的数据元素在物理地址上可能相邻，可也能不相邻。其在物理地址上的表现是随机的。链式存储结构中，一般将每个数据元素占用的若干单元的组合称为一个链结点。每个链结点不仅要存放一个数据元素的数据信息，还要存放一个指出这个数据元素在逻辑关系的直接后继元素所在链结点的地址，该地址被称为指针。换句话说，数据元素之间的逻辑关系是通过指针来间接反映的。

????????这种结构的优点是：存储空间不必事先分配，在需要存储空间的时候可以临时申请，不会造成空间的浪费；一些操作的时间效率远比顺序存储结构高（插入、移动、删除元素）。

????????缺点是：不仅数据元素本身的数据信息要占用存储空间，指针也需要占用存储空间，链式存储结构比顺序存储结构的空间开销大。

2 算法

????????算法（Algorithm）：解决特定问题求解步骤的准确而完整的描述，在计算机中表现为一系列指令的集合，算法代表着用系统的方法描述解决问题的策略机制。???????

简单而言：「算法」?指的就是解决问题的方法。????????

2.1 算法的基本特性??????????

算法其实就是一系列的运算步骤，这些运算步骤可以解决特定的问题。除此之外，算法?应必须具备以下特性。

1.输入

????????对于待解决的问题，都要以某种方式交给对应的算法。在算法开始之前最初赋给算法的参数称为输入。比如例一中的输入就是出发地和目的地的参数（北京，上海），例三中的输入就是 n 个整数构成的数组。

????????一个算法可以有多个输入，也可以没有输入。比如例二是对固定问题的求解，就可以看做没有输入。

2.输出

????????算法是为了解决问题存在的，最终总需要返回一个结果。所以至少需要一个或多个参数作为算法的输出。比如例一中的输出就是最终选择的交通方式，例二中的输出就是和的结果。例三中的输出就是排好序的数组。

3.有穷性

????????算法必须在有限的步骤内结束，并且应该在一个可接受的时间内完成。比如例一，如果我们选择五一从上海到北京去旅游，结果五一纠结了三天也没决定好怎么去北京，那么这个旅游计划也就泡汤了，这个算法自然也是不合理的。????????????????

4.确定性

????????组成算法的每一条指令必须有着清晰明确的含义，不能令读者在理解时产生二义性或者多义性。就是说，算法的每一个步骤都必须准确定义而无歧义。????????

5.可行性

????????算法的每一步操作必须具有可执行性，在当前环境条件下可以通过有限次运算实现。也就是说，每一步都能通过执行有限次数完成，并且可以转换为程序在计算机上运行并得到正确的结果。???????

2.2 算法追求的目标??

1. 所需运行时间更少（时间复杂度更低）；
2. 占用内存空间更小（空间复杂度更低）。

一个好的算法还应该追求以下目标：

1. 正确性：正确性是指算法能够满足具体问题的需求，程序运行正常，无语法错误，能够通过典型的软件测试，达到预期的需求。
2. 可读性：可读性指的是算法遵循标识符命名规则，简洁易懂，注释语句恰当，方便自己和他人阅读，便于后期修改和调试。
3. 健壮性：健壮性指的是算法对非法数据以及操作有较好的反应和处理。

这 3 个目标是算法的基本标准，是所有算法所必须满足的。一般我们对好的算法的评判标准就是上边提到的?所需运行时间更少（时间复杂度更低）、占用内存空间更小（空间复杂度更低）。

二、算法复杂度

1. 算法复杂度简介?

算法复杂度（Algorithm complexity）：在问题的输入规模为 n 的条件下，程序的时间使用情况和空间使用情况。

2. 时间复杂度?

2.1 时间复杂度简介?

时间复杂度（Time Complexity）：在问题的输入规模为 n 的条件下，算法运行所需要花费的时间，可以记作为 T(n)。

3. 空间复杂度?

3.1 空间复杂度简介?

空间复杂度（Space Complexity）：在问题的输入规模为 n 的条件下，算法所占用的空间大小，可以记作为 S(n)。一般将?算法的辅助空间?作为衡量空间复杂度的标准。