Java 算法与数据结构
2021-04-22 11:33:14 1 举报AI智能生成
Java 算法与数据结构
作者其他创作
大纲/内容
前景提要(经典面试题)
1),字符串匹配问题: 有一个字符串 str1="尚硅谷 尚硅谷你尚硅谷 尚硅谷你尚硅谷你好" 和一个字符串str2="尚硅谷你尚硅谷你"
现在要判断str1 是否包含 str2 ,如果存在就返回第一次出现的位置,如果不存在就返回-1
要求用最快的速度来完成匹配
你的思路是什么?
2), 汉诺游戏,请完成汉诺塔游戏的代码
1 将A塔的所有圆盘移动到c盘 并规定小圆盘不能放在大圆盘上
2 三根柱子之间一次只能移动一个圆盘
你的思路是什么
3), 绝境8皇后
你的思路是什么
4), 马踏棋盘
你的思路是什么
数据结构和算法的重要性
1 算法是程序的灵魂,优化的程序可以在海量数据计算时,依然保持高速计算
2 一般来讲,程序使用了内存计算框架(比如Spark)和缓存技术(比如 Redis等) 来优化程序,在深入思考一下,这些计算框架和缓存技术它的核心功能是哪个部分呢?
3 拿实际工作经历来说,在Unix 下开发服务器程序,功能是要支持上千万人同时在线,在上线前,做内测,一切ok 上线后,服务器就支撑不下去了,公司的CTO对代码进行优化,再次上线,坚如磐石,你能感受到程序是由灵魂的,就是算法
4 目前程序员面试的门槛越来越高,很多一线IT公司,都有数据结构和算法面试题
5 如果你不想永远都是代码工人,那就花时间研究一下数据结构和算法
数据结构和算法的关系
数据结构(data structure )是一门研究组织数据方式的学科,有了编程语言也就有了数据结构,学好数据结构可以编写出更加漂亮,更高效率的代码
要学好数据结构就要多多考虑如何将生活中遇到的问题,用程序代码去实现解决
程序= 数据结构+算法
数据结构是算法的基础,换言之,想要学好算法,需要把数据结构学到位
实际编程遇到的一些问题
1 字符串替换问题
试写出 单链表 表示的字符串类以及字符串结点类的定义
并以此实现它的构造函数,以及计算串长度,串赋值,判断两串相等
求子串,两串连接,求子串在串中位置等7个成员函数
小结: 需要使用到单链表
2 五子棋程序
1 如何判断游戏输赢,并可以完成存盘退出和继续上局的功能
小结
棋盘->二维数组 (稀疏数组) -> 写入文件 [存档功能]
读取文件 -> (稀疏数组) 二维数组 ->棋盘 [恢复上局]
3 约瑟夫(Josephu) 问题(丢手帕问题)
提示: 用一个不带头的循环链表来处理 丢手帕问题
问题: 先构成一个有n 个节点的单循环链表 (单向环形链表) ,然后由 k 节点起从1开始计数,计到m时,对应节点从链表中删除,然后再从被删除节点的下一个元素 又从1开始计数,直到最后一个节点从链表中删除算法结束
其它常见算法问题
1 修路问题 => 最小生成树(加权值)[数据结构] +普利姆算法
2 最短路径问题 => 图 + 弗洛伊德算法
3 汉诺塔游戏 -> 分治算法
4 八皇后游戏 -> 回溯算法
数据结构
线性结构
线性结构作为最常用的数据结构,其特点是元素之间存在一对一的线性关系
线性结构有两种不同的存储方式,即顺序存储结构和链式存储结构,顺序存储的线性表称之为 顺序表,顺序表中的元素是连续的(内存地址是连续的)
链式存储的线性表称之为链表,链表中的存储元素不一定是连续的,元素节点中存放数据元素以及相邻元素的地址信息
线性结构最常见的有 数组,队列,链表和栈
非线性结构
二维数组, 多维数组, 广义表, 树结构,图结构
稀疏数组 (sparsearray)
原始的二维数组 -> 变为稀疏数组(sparse array)
基本介绍
当一个数组大部分元素为0,或者同一个值的数组时,可以使用稀疏数组(sparsearray) 来保存该数组
分析问题?
因为该二维数组的很多默认值都是0,因此记录了很多没有意思的数组,所以要使用 稀疏数组(sparse array)进行缩小
处理方法
1 记录数组一共有几行几列,有多少个不同的值
2 把具有不同值的元素的行列及值记录在一个小规模的数组中,从而缩小程序的规模
整体思路分析
二维数组转为稀疏数组
1 遍历整个二维数组得到有效数据个数为 sum
2 根据 sum 就可以创建稀疏数组 sparseArray=[sum+1][3]
3 将二维数组的数组放入稀疏数组中(其中第一行显示的是 行 列 值,第二行开始放入的数据)
稀疏数组转为二维数组
1 拿到稀疏数组第一行(行 列 值) 创建出一个二维数组
2 遍历稀疏数组从第二行开始,赋值给原来的二维数组
代码实现
队列
队列-Queue
数组模拟队列( 队列本身是有序列表,若使用数组的结构来存储队列的数据,则队列数组如上图所示,其中 maxSize是该队列的最大容量, )
简介
队列 是一个有序列表,可以用数组 或 链表来实现
遵循先进先出的原则,即,先存入队列的数据, 要先取出,后存入的要后取出
思路分析
当我们将数据存入队列时,假如执行 addQueue 方法
1 将尾指针向后移动 1 位, rear +1, 当 front = rear[为空]
2 若尾指针 rear 小于 maxSize-1 ,则可以将数据写入Queue 队列中,否则将无法写入数据, rear == maxSize-1 队列已经满了
数组模拟队列的代码实现
环形队列
分析思路
front 做一个调整: 指向第一个元素,也就是 queue[front]=队列第一个元素,fornt 默认值为0
rear 做一个调整: 指向队列最后一个元素的后一个位置,因为要腾出一个位置,做约定, rear 默认值为0
如果判断队列是否满了 (rear+1)%maxSize == front
如何判断当前队列是否为空,rear==front
如何判断队列中存在数据的个数 (rear+maxSize-front)%maxSize
我们就可以在原来的队列上修改得到,一个环形队列
代码
链表--LinkedList
链表是有序的列表,但是它在内存中的存储如上
小结
链表是以链式的方式来存储,每个节点必须包含 data域(存储数据) next域(指向下一个节点)
链表的各个节点不一定是连续存放的
链表分为带头节点的链表 和 没有头节点的链表,根据实际需求来确定
单链表
单链表逻辑示意图
应用实例
使用带 header 头的单向链表-水浒排行榜管理
1 完成对英雄人物的增删改查
2 第一种方法在添加英雄时,直接添加到链表尾部
3 第二种方式在添加英雄时,根据排名将英雄插入到指定位置(如果有这个排名插入失败,给出提示)
链表按顺序添加 v1.0
链表按顺序添加 修改 删除 v2.0
缺点
1 单向链表,查找的方向只能是一个方向,而双向链表可以向前或者向后查找
2 单向链表不能自我删除,需要靠辅助节点,而双向链表,则可以自我删除,所以前面我们单链表删除时节点,总是需要找到temp 节点,temp 节点时前一个节点来进行删除
单链表面试题
1 求单链表有效节点的个数--遍历整个链表
2 查找单链表中的倒数第k个节点--新浪面试题
3 单链表的反转--腾讯面试题
解决思路
1 新建一个reversalHeader 头节点
2 遍历 原来链表 每次取出链表尾部为null 的节点 的当前节点赋值到 reversalHeader节点
3 把原来链表的头下一个节点设置为 reversalHeader 的next节点
4 从尾到头打印单链表 要求 1-反向遍历 2-stack 栈
解决思路
1 先将单链表进行反转,然后在循环反转后的链表 ,这样做会破坏原来的单链表的结构 不可取
2 利用栈这个数据结构,将各个节点压入栈中,然后利用栈的先进后出的特点就实现了 逆序打印的效果
5 合并两个有序的单链表,合并之后链表依然有序
思路分析
1 ·创建一个新链表,将原始的表节点连到新链表
2 遍历两个链表，通过比较大小,将原始链表节点连到新链表上
双向链表
思路分析
遍历 : 和单链表一样从前向后遍历,或者从后向前遍历
添加 : 添加到双向链表的尾部 temp 是尾节点
删除 : 可以实现节点的自我删除 , temp是需要删除的节点
修改 :和单链表修改思路相同
代码实现
双向链表第二种添加方式--按照编号顺序,按照单链表的顺序添加
约瑟夫问题--环形链表
示意图(1,2,3,4) 假设n=4, k=1,m=2 出队列顺序为 2->4->3->1
单向环形链表的构建思路
创建 : 1),先创建一个新的节点,用first指针指向该节点,并形成环状 2), 后面当我们每次添加一个新节点的时候,就把该节点添加已有的环形链表中即可
循环 : 1),先创建一个类临时节点指向 first 头节点,然后遍历下次当临时节点的next节点==first 时,循环结束
代码实现
约瑟夫问题--出圈的思路分析
报数前: 先让first 和 tempNode 移动k-1次
1 创建一个辅助指针tempNode ,事先指向环形链表的最后一个节点
2 当开始报数的时候 first 和 tempNode 都同时移动 (m-1)次
3 这是就可以将 first 指向的小孩出圈
4 这是小孩已经出圈 ,就会被垃圾回收机制回收
约瑟夫问题解决代码
栈--stack
请输入一个表达式, 7*2*2-5+1+5+3+3 点击计算
图解
基本介绍
栈是一个先进后出的的有序集合
栈 是限制限性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表,允许插入和删除的一端,为变化的一端,称之为 栈顶(top),另一端为固定的一端,称之为 栈底(botton)
根据栈的定义可知, 最后先放入栈中元素在栈底, 最后放入的元素在栈顶,而删除元素刚好相反,最后放入的先删除,最先放入的最后删除
栈的应用场景
1 子程序,在调往子程序前,会先将下个指令的地址存储在堆栈中,直到子程序执行完后再将地址取出,以回到原来的程序中
2 处理递归调用: 和子程序的调用类似,只是除了存储下一个指令的地址外,也将表达式的参数,区域变量等数据存入堆栈中
3 表达式的转换中[中缀表达式转后缀表达式] 与求值
4 图形的深度优化(depth-first)搜索法
5 二叉树的遍历
实现栈的思路分析
1 创建一个数组stack,用数组来模拟栈
2 定义一个top变量(默认值为-1), push 数据的时候 top++;
3 取数据的时候 int val=stack[top]; top--; return val;
用数组模拟栈(stack)代码实现
用链表模拟栈代码实现
使用栈 完成计算一个表达式结果思路
1 通过index 值来遍历扫描表达式
2 创建一个 numStak栈 和 markStack栈,如果index扫描的是一个数字 直接入符号张,如果index 扫描是一个符号 如果发现 markStack 为空 直接入符号栈
3 如果发现符号栈里面有符号,就进行比较 如果当前index 指向的符号优先级 小于 等于符号栈中的优先级,就需要从数字栈中弹出2个数字,从符号栈中弹出一个符号进行运算,将得到的结果如 数字栈,然后将index 的符号如入符号栈,如果当前的操作符优先级大与符号栈用的优先级,直接入符号栈
4 当表达式扫描完毕,就顺序从数栈和符号栈取数和符号进行计算,
5 最后在数字栈得到一个数字就是表达式结果
栈计算表达式代码
前缀表达式--波兰表达式
前缀表达式又称为波兰式,前缀表达式的运算符位于操作数之前
前缀表达式的计算机求值
从 右至左扫描表达式,遇到数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符进行相应的计算(栈顶元素和次顶元素),并将结果入栈,重复上述过程指导表达式的最左端,最后运算得出的值就是表达式的结果
例如 (3+4)*5-6 对应的前缀表达式就是 - * + 3 4 5 6(数字从左向右 符号从右向左) 针对前缀表达式求值步骤如下
1 从右向左扫描,将 6 5 4 3 压入栈中
2 遇到 +运算符,因此弹出3 与 4 ,计算 3+4的值,然后将结果7压入栈中
3 接下来是 * 运算符号,因此 弹出 7 与 5 然后将结果35压入栈中
4 最后是 -运算符号,因此弹出 35 与 6 得到运算符号的结果 29
中缀表达式
中缀表达式就是我们最常见的运算表达式,如 (3+4)*5-6
中缀表达式的求值是我们人最熟悉的,但是对计算机来说却不好操作(前面我们讲的案例能看到这个问题) 因此,在计算结果时,往往会将中缀表达式转为后缀表达式
后缀表达式--逆波兰表达式
(3+4)*5-6 对应的后缀表达式为 3 4 + 5 * 6 -
后缀表达式又称为逆波兰表达式,与前缀表达式相似,只是运算符位于操作数之后
后缀表达式的计算机求值
从左向右扫描表达式,遇到数字,将数字压入栈中,遇到运算符,弹出两个数,用运算符对它们进行相应的计算,并将结果压入堆栈中,重复上述过程,最后运算得出运算结果
例如 (3+4)*5-6 对应的后缀表达式为 3 4 + 5 * 6 -,针对后缀表达式运算流程如下
1 从左到右扫描,将数字3 与 4压入栈中
2 遇到 + 运算符,弹出 3 与 4 得到运算结果,将7压入栈中
3 将 5压入栈中
4 接下来拿到 * 运算符号 ,弹出 7 与 5 将结果 35压入栈中
5 将数字 6 压入栈中
6 拿到运算符号 - 将栈底的数字35 与栈顶的 6进行运算的到 29 注意(不能写反) ,拿到运算结果
完成一个逆波兰表达式--后缀表达式代码
1 输入一个后缀表达式,使用栈 计算其结果
2 支持小括号和多位整数, 因为我们这里主要讲的是数据结构,因此计算器进行简化,只支持对整数进行计算
中缀表达式转换为后缀表达式
可以看到,后缀表达式适合计算式进行运算,但是人却不太容易写出来,尤其是表达式很长的情况下,因此在开发过程中,我们需要将 中缀表达式转为后缀表达式
转换步骤如下
1 初始化2个栈,运算符栈 s1 和 存储中间结果栈的s2
2 从左到右扫描中缀表达式
3 遇到操作数是 将其压入 s2
4 遇到运算符,比较其与 s1 栈顶运算符的优先级
1 如果s1 为空,或栈顶运算符为左括号( 则直接将此运算符入栈
2 否则 若优先级比栈顶运算符的高,也将其直接压入符号栈 s1
3 否则, 将s1 栈顶的运算符弹出并压入到s2中,再次转入到 (4.1) 与 s1 中新的栈顶运算符相对比
5 遇到括号时
如果是左括号 ( 则直接压入s1
如果遇到的是 右括号 ) ,则依次弹出s1 栈顶的运算符号,并压入 s2 ,知道遇到右括号为止,此时将这一对括号丢弃(从符号栈弹出一个)
6 重复步骤 2-5,知道表达式的最右边
7 将s1中剩余的运算符依次弹出并压入s2(循环判断符号栈 只要不为空就像数字栈插入)
8 依次弹出 s2中的元素并输出,结果的逆序即为 中缀表达式对应的后缀表达式
递归 -- recursion
概念 : 递归就是方法自己调用自己,每次调用时传入不同的变量,递归有助于编程者解决复杂的问题,同时可以让代码变得简洁
递归案例
打印问题
阶乘问题
递归用于解决什么问题?
1 各种数学问题, 如八皇后问题,汉罗塔,阶乘问题,迷宫问题,球和篮子的问题
2 各种算法中也能用到递归,比如快排,归并排序,二分查找,分治算法等
3 将用栈解决问题->递归代码比较简洁
递归需要遵守的重要规则
1 执行一个方法时,就创建一个新的受保护的独立空间(栈)
2 方法的局部变量是独立的,不会相互影响(如果方法执行过程使用的是引用类型变量--数组,就会共享该引用类型变量)
3 递归必须向退出递归的条件逼近,否则就是无限递归,死龟了(stackOverflowError)
4 当一个方法执行完毕,或者遇到了 return 就会返回,遵守谁调用,就将结果返回给谁,同时方法执行完毕或者返回时,该方法也就执行完毕
迷宫问题
1 小球得到的路径,和程序员设置的找路策略有关即 : 找路的上下左右的顺序相关
2 再得到小球路径时,可以先使用 (下右上左) 再改成(上右下左) 看看路径是不是有电话
3 测试回溯现象
4 如何求出最短路径?
小球找路代码实现
八皇后问题
思路分析
1 第一个皇后先放在第一行第一列
2 第二个皇后放在第二行第一列,然后判断是否ok,如果不ok 继续放在第二列,第三列,依次把所有的列都放完,找到一个合适的位置
3 继续放置第三个皇后,还是第一列,第二列......知道第8个皇后也能放在一个不冲突的位置,算是找到了一个正确的解
4 当得到一个正确解时,回溯到上一个栈即第一个皇后,放在第一列的所有正确解,全部得到
5 然后回头继续第一个皇后放在第二列,后面继续执行1,2,3,4 步骤
说明 : 理论上应该创建一个二维数组来表示棋盘,但是实际上可以通过算法,用一个一维数组即可解决 arr[8]={0,4,7,5,2,6,1,3} //对应下标表示第几行,及第几个皇后,arr[i]=val; val 表示第i+1个皇后,放在了 i+1行的第val+1列
排序算法 --Sort Algorithm
常见的排序算法分类
简介
排序也称排序算法,排序是将一组数据,依照指定的顺序进行排序的过程
1 内部排序(内存): 指将需要处理的所有数据都加载到内部存储器中进行排序
2 外部排序法: 数据量过大,无法全部加载到内存中,需要借助外部存储进行
算法的时间复杂度--衡量一个算法执行时间的2种方式
事后统计的方式
事前估算的方法
0 条评论
下一页
