Android开发面试：数据结构与算法知识答案精解

目录

数据结构与算法

线性表

数组

链表

栈

队列

树

二叉树

红黑树

哈夫曼树

排序算法

冒泡排序

选择排序

插入排序

希尔排序

堆排序

快速排序

归并排序

查找算法

线性查找

二分查找

插值查找

斐波拉契查找

树表查找

分块查找

哈希查找

动态规划算法

贪心算法

LeetCode算法题

---

数据结构与算法

线性表

数组

1. 线性表是一种线性结构，它是具有相同类型的n(n≥0)个数据元素组成有限序列
2. 描述：数组有上界和下界，数组元素在上下界内是连续的；复杂一点是多维数组和动态数组，多维数组本质上是通过一维实现，动态数组Java中实现有ArrayList和Vector
3. 特点：数据是连续的，随机访问速度快

链表

1. 单向链表：a、是链表的一种，它由节点组成，每个节点都包含下一个节点的指针；b、节点的链接方向是单向的；c、相对于数组来说，单链表随机访问速度较慢，但删除/添加数据效率高
2. 双向链表：a、是链表的一种，和单链表一样，双链表也是由节点组成，每个数据结点中都有两个指针，分别指向直接后继和直接前驱；b、从双向链表中任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点，一般我们都构造双向循环链表，LinkedList实现了双链表

栈

1. Java中Stack(继承自Vector)实现了栈，栈中数据是按照"后进先出(LIFO, Last In First Out)"方式进出栈的，向栈中添加/删除数据时只能从栈顶进行操作
2. 通常包括的三种操作：push向栈中添加元素、peek返回栈顶元素、pop返回并删除栈顶元素

队列

1. 队列中数据是按照"先进先出(FIFO, First-In-First-Out)"方式进出队列的，队列只允许在队首进行删除操作，而在队尾进行插入操作，通常包括两种操作，入队列和出队列
2. Java中Queue接口实现了队列，用的最多的是LinkedList

树

二叉树

1. 包括满二叉树、完全二叉树和二叉查找树
2. 二叉查找树：若任意节点的左子树不空，则左子树上所有结点的值均小于它根结点的值；任意节点的右子树不空，则右子树上所有结点的值均大于它根结点的值
3. 遍历：前序、中序、后序遍历算法，也就是根结点的访问顺序，前序遍历算法是先访问根节点，然后左子树，而后右子树
4. 深度、广度优先遍历算法：树的深度优先遍历需要用到额外数据结构栈，而广度优先遍历需要队列来辅助，深度遍历算法包括前中后序遍历算法

红黑树

1. 定义：红黑树是特殊的二叉查找树，每个节点上都有存储位表示节点颜色，可以是红(Red)或黑(Black)
2. 特征：a、每个节点或者是黑色，或者是红色；b、根节点是黑色；c、每个叶子节点(NIL)是黑色；d、如果一个节点是红色的，则它的子节点必须是黑色的；e、从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点
3. 应用：红黑树的应用比较广泛，主要是用它来存储有序数据，它的时间复杂度是O(lgn)，效率非常之高。 例如，Java集合中的TreeMap和HashMap，都是通过红黑树去实现的

哈夫曼树

1. 定义：给定n个权值作为n个叶子结点，构造一棵二叉树，若树的带权路径长度达到最小，则这棵树被称为哈夫曼树，哈夫曼树是最优二叉树

排序算法

冒泡排序

1. 最大到右边。每一轮从头开始两两比较，将较大的项放在较小项的右边，这样每轮下来保证该轮最大的数在最右边
2. 时间复杂度O(n^2)，空间复杂度O(1)，算法是稳定的

选择排序

1. 最小到左边。在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止
2. 时间复杂度O(n^2)，空间复杂度O(1)，算法不稳定，性能优于冒泡排序，交换次数少

插入排序

1. 从后向前插入位置。每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的字序列的合适位置(从后向前找到合适位置后)，直到全部插入排序完为止
2. 时间复杂度O(n^2)，空间复杂度O(1)，算法是稳定的，性能优于冒泡排序和选择排序

希尔排序

1. 将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序
2. 时间复杂度O(n^1.5)，空间复杂度O(1)，算法不稳定

堆排序

1. 堆排序是一种树形选择排序，是对直接选择排序的有效改进
2. 堆的定义：具有n个元素的序列 (h1,h2,...,hn)，当且仅当满足 (hi>=h2i,hi>=h2i+1)或(hi
3. 思想：初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储序，使之成为一个堆，这时堆根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数
4. 时间复杂度O(nlogn)，空间复杂度O(1)，算法不稳定，不适合排序数据较少的情况

快速排序

1. 左小右大。通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分关键字小，则分别对这两部分继续进行排序，直到整个序列有序
2. 时间复杂度O(nlogn)，空间复杂度O(nlogn)，算法不稳定，快速排序在序列中元素很少时效率将比较低，此时不如插入排序，一般使用插入排序提高整体效率

归并排序

1. 归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新有序表，即：把待排序序列分为若干个子序列，每个子序列是有序的，然后再把有序子序列合并为整体有序序列
2. 时间复杂度O(nlogn)，空间复杂度O(1)，算法是稳定的

排序算法Java实现

查找算法

线性查找

1. 一个个往后顺序查找

二分查找

1. 有序数组，折半查找

插值查找

1. 数据有序且分布均匀，优化二分查找

斐波拉契查找

树表查找

分块查找

哈希查找

动态规划算法

贪心算法

LeetCode算法题

---

数据结构与算法

线性表

数组

链表

栈

队列

树

二叉树

红黑树

哈夫曼树

排序算法

冒泡排序

选择排序

插入排序

希尔排序

堆排序

快速排序

归并排序

查找算法

线性查找

二分查找

插值查找

斐波拉契查找

树表查找

分块查找

哈希查找

动态规划算法

贪心算法

LeetCode算法题

---

Android开发面试系列文章：

• Android开发面试：Android知识答案精解
• Android开发面试：Java知识答案精解
• Android开发面试：架构设计和网络知识答案精解
• Android开发面试：数据结构与算法知识答案精解
• Android开发面试：Kotlin面试知识答案精解

---