Android开发面试:数据结构与算法知识答案精解
创始人
2024-06-02 19:22:15
0

目录

数据结构与算法

线性表

数组

链表

队列

二叉树

红黑树

哈夫曼树

排序算法

冒泡排序

选择排序

插入排序

希尔排序

堆排序

快速排序

归并排序

查找算法

线性查找

二分查找

插值查找

斐波拉契查找

树表查找

分块查找

哈希查找

动态规划算法

贪心算法

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面试知识答案精解

相关内容

热门资讯

安卓系统车机互联软件 你有没有发现,现在开车的时候,手机和车机之间的互动越来越频繁了呢?想象你正驾驶着爱车,一边享受着音乐...
荣耀play4安卓系统,智能生... 你有没有发现,最近手机圈里又掀起了一股热潮?没错,就是荣耀Play4这款新机!它不仅外观时尚,性能强...
安卓模拟苹果多开系统,打造跨平... 你有没有想过,在安卓手机上也能享受到苹果系统的多开功能呢?没错,这就是今天我要跟你分享的神奇话题——...
广汽埃安是安卓系统吗,搭载安卓... 你有没有想过,你的爱车广汽埃安,它的操作系统是不是安卓呢?这个问题,估计不少车友都在心里默默琢磨过。...
安卓系统是google的吗,谷... 你有没有想过,安卓系统是不是谷歌的亲生孩子呢?这个问题,就像是在问苹果是不是苹果树的宝宝一样,让人好...
安卓系统的设置程序下载,轻松掌... 你有没有发现,手机里的安卓系统设置程序真是五花八门,让人眼花缭乱?今天,就让我带你一起探索这个神秘的...
安卓系统的手机家园,打造个性化... 你有没有发现,现在手机的世界里,安卓系统的手机家园可是越来越热闹了呢!想象每天打开手机,就像走进了一...
安卓系统哪些相机可以调,支持实... 你有没有发现,手机拍照已经成为我们生活中不可或缺的一部分呢?无论是记录生活的点滴,还是捕捉美丽的瞬间...
安卓手机系统英文变中文,And... 你有没有发现,你的安卓手机上那些英文字母的系统提示,突然间变成了熟悉的中文呢?是不是觉得瞬间亲切感倍...
系统语言可以删除吗安卓,基于系... 你有没有想过,手机里的那些系统语言,是不是有时候觉得有点多余呢?比如,你是个地道的英语使用者,却总是...
安卓系统收取专利吗,揭秘科技巨... 你有没有想过,那个陪伴你每天刷手机、玩游戏、办公的安卓系统,它背后是不是也有自己的“小金库”呢?没错...
安卓屏幕怎么更新系统,轻松掌握... 亲爱的安卓手机用户们,你是不是也和我一样,时不时地想给手机来个“大变身”,让它焕然一新呢?没错,说的...
安卓系统有没有类似carpla... 你有没有想过,在安卓系统上,能不能也像苹果用户那样,轻松连接汽车音响系统呢?没错,我说的就是那个神奇...
安卓系统哪里升级包,生成与更新... 亲爱的安卓用户们,你是不是也和我一样,时不时地想给手机来个“大变身”,让它焕然一新呢?那就得提到那个...
安卓手机怎么恢复老系统,轻松恢... 手机用久了,是不是觉得系统越来越卡,功能也越来越不跟得上潮流了呢?别急,今天就来教你怎么把安卓手机恢...
安卓系统如何安装windows... 亲爱的安卓用户们,你是否曾幻想过在手机上体验Windows 7的韵味?别再羡慕那些拥有Windows...
旧的安卓系统怎么备份,轻松保存... 亲爱的安卓用户们,你是否曾经因为系统升级或者手机意外重启而担心丢失了珍贵的照片、联系人或者应用数据呢...
安卓手机系统文件被破坏,全面解... 手机突然间罢工了,是不是很崩溃?别急,今天就来聊聊安卓手机系统文件被破坏的那些事儿。相信我,掌握了这...
街头霸王四安卓系统,畅享格斗盛... 你知道吗?最近在安卓系统上,有一款游戏可是火得一塌糊涂,那就是《街头霸王四》!这款经典格斗游戏在安卓...
阿里tv安卓系统刷机,畅享智能... 你有没有发现,家里的阿里TV用久了,系统有点卡卡的呢?别急,今天就来教你怎么给它来个焕然一新的刷机大...