无锡新吴区住房建设交通局网站,建一个网站怎么赚钱,舆情分析报告格式,如何建设手机网站目录
数据结构与算法
线性表
数组
链表
栈
队列
树
二叉树
红黑树
哈夫曼树
排序算法
冒泡排序
选择排序
插入排序
希尔排序
堆排序
快速排序
归并排序
查找算法
线性查找
二分查找
插值查找
斐波拉契查找
树表查找
分块查找
哈希查找
动态规划算法…目录
数据结构与算法
线性表
数组
链表
栈
队列
树
二叉树
红黑树
哈夫曼树
排序算法
冒泡排序
选择排序
插入排序
希尔排序
堆排序
快速排序
归并排序
查找算法
线性查找
二分查找
插值查找
斐波拉契查找
树表查找
分块查找
哈希查找
动态规划算法
贪心算法
LeetCode算法题 数据结构与算法
线性表
数组
线性表是一种线性结构它是具有相同类型的n(n≥0)个数据元素组成有限序列描述数组有上界和下界数组元素在上下界内是连续的复杂一点是多维数组和动态数组多维数组本质上是通过一维实现动态数组Java中实现有ArrayList和Vector特点数据是连续的随机访问速度快
链表
单向链表a、是链表的一种它由节点组成每个节点都包含下一个节点的指针b、节点的链接方向是单向的c、相对于数组来说单链表随机访问速度较慢但删除/添加数据效率高双向链表a、是链表的一种和单链表一样双链表也是由节点组成每个数据结点中都有两个指针分别指向直接后继和直接前驱b、从双向链表中任意一个结点开始都可以很方便地访问它的前驱结点和后继结点一般我们都构造双向循环链表LinkedList实现了双链表
栈
Java中Stack(继承自Vector)实现了栈栈中数据是按照后进先出(LIFO, Last In First Out)方式进出栈的向栈中添加/删除数据时只能从栈顶进行操作通常包括的三种操作push向栈中添加元素、peek返回栈顶元素、pop返回并删除栈顶元素
队列
队列中数据是按照先进先出(FIFO, First-In-First-Out)方式进出队列的队列只允许在队首进行删除操作而在队尾进行插入操作通常包括两种操作入队列和出队列Java中Queue接口实现了队列用的最多的是LinkedList
树
二叉树
包括满二叉树、完全二叉树和二叉查找树二叉查找树若任意节点的左子树不空则左子树上所有结点的值均小于它根结点的值任意节点的右子树不空则右子树上所有结点的值均大于它根结点的值遍历前序、中序、后序遍历算法也就是根结点的访问顺序前序遍历算法是先访问根节点然后左子树而后右子树深度、广度优先遍历算法树的深度优先遍历需要用到额外数据结构栈而广度优先遍历需要队列来辅助深度遍历算法包括前中后序遍历算法
红黑树
定义红黑树是特殊的二叉查找树每个节点上都有存储位表示节点颜色可以是红(Red)或黑(Black)特征a、每个节点或者是黑色或者是红色b、根节点是黑色c、每个叶子节点(NIL)是黑色d、如果一个节点是红色的则它的子节点必须是黑色的e、从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点应用红黑树的应用比较广泛主要是用它来存储有序数据它的时间复杂度是O(lgn)效率非常之高。 例如Java集合中的TreeMap和HashMap都是通过红黑树去实现的
哈夫曼树
定义给定n个权值作为n个叶子结点构造一棵二叉树若树的带权路径长度达到最小则这棵树被称为哈夫曼树哈夫曼树是最优二叉树
排序算法
冒泡排序
最大到右边。每一轮从头开始两两比较将较大的项放在较小项的右边这样每轮下来保证该轮最大的数在最右边时间复杂度O(n^2)空间复杂度O(1)算法是稳定的
选择排序
最小到左边。在要排序的一组数中选出最小的一个数与第一个位置的数交换然后在剩下的数当中再找最小的与第二个位置的数交换如此循环到倒数第二个数和最后一个数比较为止时间复杂度O(n^2)空间复杂度O(1)算法不稳定性能优于冒泡排序交换次数少
插入排序
从后向前插入位置。每步将一个待排序的记录按其顺序码大小插入到前面已经排序的字序列的合适位置(从后向前找到合适位置后)直到全部插入排序完为止时间复杂度O(n^2)空间复杂度O(1)算法是稳定的性能优于冒泡排序和选择排序
希尔排序
将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序待整个序列中的记录“基本有序”时再对全体记录进行依次直接插入排序时间复杂度O(n^1.5)空间复杂度O(1)算法不稳定
堆排序
堆排序是一种树形选择排序是对直接选择排序的有效改进堆的定义具有n个元素的序列 (h1,h2,...,hn)当且仅当满足 (hih2i,hih2i1)或(hi思想初始时把要排序的数的序列看作是一棵顺序存储的二叉树调整它们的存储序使之成为一个堆这时堆根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推直到只有两个节点的堆并对它们作交换最后得到有n个节点的有序序列。从算法描述来看堆排序需要两个过程一是建立堆二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数二是反复调用渗透函数实现排序的函数时间复杂度O(nlogn)空间复杂度O(1)算法不稳定不适合排序数据较少的情况
快速排序
左小右大。通过一趟排序将待排序记录分割成独立的两部分其中一部分记录的关键字均比另一部分关键字小则分别对这两部分继续进行排序直到整个序列有序时间复杂度O(nlogn)空间复杂度O(nlogn)算法不稳定快速排序在序列中元素很少时效率将比较低此时不如插入排序一般使用插入排序提高整体效率
归并排序
归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新有序表即把待排序序列分为若干个子序列每个子序列是有序的然后再把有序子序列合并为整体有序序列时间复杂度O(nlogn)空间复杂度O(1)算法是稳定的
排序算法Java实现
查找算法
线性查找
一个个往后顺序查找
二分查找
有序数组折半查找
插值查找
数据有序且分布均匀优化二分查找
斐波拉契查找
树表查找
分块查找
哈希查找
动态规划算法
贪心算法
LeetCode算法题 数据结构与算法
线性表
数组
链表
栈
队列
树
二叉树
红黑树
哈夫曼树
排序算法
冒泡排序
选择排序
插入排序
希尔排序
堆排序
快速排序
归并排序
查找算法
线性查找
二分查找
插值查找
斐波拉契查找
树表查找
分块查找
哈希查找
动态规划算法
贪心算法
LeetCode算法题 Android开发面试系列文章
Android开发面试Android知识答案精解Android开发面试Java知识答案精解Android开发面试架构设计和网络知识答案精解Android开发面试数据结构与算法知识答案精解Android开发面试Kotlin面试知识答案精解
