数据结构及算法介绍
** 一、数据结构 **
数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。
常用的数据结构有：数组、栈、链表、队列、树、图、堆、散列表等。
**1.1 概念介绍**
数组
数组是可以在内存中连续存储多个元素的结构，在内存中的分配也是连续的，数组中的元素通过数组下标进行访问。
栈
栈是一种特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作。
栈的特点是：先进后出，或者说是后进先出，从栈顶放入元素的操作叫入栈，取出元素叫出栈。
链表
链表是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，每个元素包含两个结点，一个是存储元素的数据域
(内存空间)，另一个是指向下一个结点地址的指针域。根据指针的指向，链表能形成不同的结构，例如单链表，双向链表，循环链表等。
队列
队列与栈一样，也是一种线性表，不同的是，队列可以在一端添加元素，在另一端取出元素，也就是：先进先出。
从一端放入元素的操作称为入队，取出元素为出队。
树
树是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做 “树” 是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
它具有以下的特点：
1\. 每个节点有零个或多个子节点
2\. 没有父节点的节点称为根节点
3\. 每一个非根节点有且只有一个父节点
4\. 除了根节点外，每个子节点可以分为多个不相交的子树
二叉树
图
图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。
堆
堆是一种比较特殊的数据结构，可以被看做一棵树的数组对象，具有以下的性质：
1\. 堆中某个节点的值总是不大于或不小于其父节点的值
2\. 堆总是一棵完全二叉树
散列表
散列表，也叫哈希表，是根据关键码和值 (key和value)
直接进行访问的数据结构，通过key和value来映射到集合中的一个位置，这样就可以很快找到集合中的对应元素。
左边是个数组，数组的每个成员包括一个指针，指向一个链表的头。我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。
**二、算法**
**2.1 概念介绍**
概念
算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
特征
1\. 有穷性：算法的有穷性是指算法必须能在执行有限个步骤之后终止。
2\. 确切性：算法的每一步骤必须有确切的定义。
3\. 输入项：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件。
4\. 输出项：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。
5\. 可行性：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步骤，即每个计算步骤都可以在有限时间内完成（也称之为有效性）。
评定
1\. 时间复杂度：算法的时间复杂度是指执行算法所需要的计算工作量。
2\.
空间复杂度：空间复杂度是指算法需要消耗的内存空间。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。
3\. 正确性：算法的正确性是评价一个算法优劣的最重要的标准。
4\. 可读性：算法的可读性是指一个算法可供人们阅读的容易程度。
5\. 棒鲁性：鲁棒性是指一个算法对不合理数据输入的反应能力和处理能力，也称为容错性。
** 2.2 常见的算法 **
常见的算法有递归算法，贪心算法，回溯法，还有七个排序算法：快速排序，堆排序，冒泡排序，选择排序，插入排序，希尔排序，归并排序等
递归法
直接或者间接不断反复调用自身来达到解决问题的方法。这就要求原始问题可以分解成相同问题的子问题。
通常在EBS当中查找BOM的每层的组件的时候可以用到如下sql：
1\. 定位到START WITH指示的根节点，如果没有START WITH子句，Oracle会将每一行依次作为根节点递归检索各自的层次树
2\. 依据CONNECT BY指明的关系先找到根节点下一级的子行
3\. 每找到一层子行，便再向下检索一层，如此递进，直至所有叶子节点（没有下层的行）被找到
** 2.3 算法实战 **
两数之和
题目：
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值
target的那两个整数，并返回它们的数组下标。（你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案）
示例：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1]
输入：nums = [3,2,4], target = 6
输出：[1,2]
解法一：枚举数组中的每一个数x，寻找数组中是否存在target – x
代码实现：
时间复杂度：O(N^2)，其中N是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。
空间复杂度：O(1)。
解法二：创建一个哈希表，对于每一个x，我们首先查询哈希表中是否存在target - x，如果不存在，则将x插入到哈希表中。
代码实现：
时间复杂度：O(N)，其中N是数组中的元素数量。对于每一个元素x，我们可以O(1)地寻找target - x。
空间复杂度：O(N)，其中N是数组中的元素数量。主要为哈希表的开销。
相对于方法一，方法二使用散列表(哈希表)提高空间复杂度，以此为代价来降低时间复杂度。
比较含退格的字符串
题目：
给定 a 和 b 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
注意：如果对空文本输入退格字符，文本继续为空。
示例：
输入：a= "ab#c", b ="ad#c"
输出：true
解释：a和b都会变成"ac"
输入：a= "ab#", b ="a"
输出：true
解释：a和b都会变成"a"
输入：a= "ab#c", b ="b"
输出：false
解释：a会变成"ac",b还是"b"
解法一：将给定的字符串中的退格符和应当被删除的字符都去除，还原给定字符串的一般形式。然后直接比较两字符串是否相等即可。
具体地，我们用栈处理遍历过程，每次我们遍历到一个字符：
1\. 如果它是退格符，那么我们将栈顶弹出；
2\. 如果它是普通字符，那么我们将其压入栈中。
代码实现：
时间复杂度：O(a+b)。
空间复杂度：O(a+b)。
作者：胡 伟
审核：邓金边
编辑：王 锐
