Java 算法与数据结构
2021-04-22 11:33:14 1 举报AI智能生成
登录查看完整内容
Java 算法与数据结构
作者其他创作
大纲/内容
Java 算法与数据结构
前景提要(经典面试题)
要求用最快的速度来完成匹配
你的思路是什么?
https://www.3454.com/91990p
1 将A塔的所有圆盘移动到c盘 并规定小圆盘不能放在大圆盘上
2 三根柱子之间一次只能移动一个圆盘
你的思路是什么
http://www.17yy.com/f/play/141256.html
http://www.4399.com/flash/146267.htm
数据结构和算法的重要性
1 font color=\"#c41230\
数据结构和算法的关系
数据结构(data structure )是一门font color=\"#c41230\
程序= 数据结构+算法
实际编程遇到的一些问题
1 字符串替换问题
试写出 单链表 表示的字符串类以及字符串结点类的定义
小结: 需要使用到单链表
2 五子棋程序
小结
棋盘->二维数组 (稀疏数组) -> 写入文件 [存档功能]
读取文件 -> (稀疏数组) 二维数组 ->棋盘 [恢复上局]
3 约瑟夫(Josephu) 问题(丢手帕问题)
提示: 用一个不带头的循环链表来处理 丢手帕问题
其它常见算法问题
1 修路问题 => 最小生成树(加权值)[数据结构] +普利姆算法
2 最短路径问题 => 图 + 弗洛伊德算法
3 汉诺塔游戏 -> 分治算法
4 八皇后游戏 -> 回溯算法
数据结构
线性结构
font color=\"#c41230\
链式存储的线性表称之为font color=\"#c41230\
线性结构最常见的有 font color=\"#c41230\
非线性结构
font color=\"#000000\
稀疏数组 (sparsearray)
原始的二维数组 -> 变为稀疏数组(sparse array)
基本介绍
分析问题?
处理方法
整体思路分析
二维数组转为稀疏数组
1 遍历整个二维数组得到有效数据个数为 sum
2 根据 sum 就可以创建稀疏数组 sparseArray=[sum+1][3]
稀疏数组转为二维数组
1 拿到稀疏数组第一行(行 列 值) 创建出一个二维数组
代码实现
队列
队列-Queue
简介
队列 是一个font color=\"#c41230\
遵循font color=\"#c41230\
思路分析
数组模拟队列的代码实现
环形队列
分析思路
如果判断队列是否满了 (rear+1)%maxSize == front
如何判断队列中存在数据的个数 (rear+maxSize-front)%maxSize
代码
链表--LinkedList
小结
链表是以font color=\"#c41230\
链表的各个节点不一定是连续存放的
单链表
单链表逻辑示意图
应用实例
使用带 header 头的单向链表-水浒排行榜管理
1 完成对英雄人物的增删改查
链表按顺序添加 v1.0
链表按顺序添加 修改 删除 v2.0
缺点
单链表面试题
1 求单链表有效节点的个数--遍历整个链表
2 查找单链表中的倒数第k个节点--新浪面试题
3 单链表的反转--腾讯面试题
解决思路
1 新建一个reversalHeader 头节点
2 遍历 原来链表 每次取出链表尾部为null 的节点 的当前节点赋值到 reversalHeader节点
3 把原来链表的头下一个节点设置为 reversalHeader 的next节点
4 从尾到头打印单链表 要求 1-反向遍历 2-stack 栈
双向链表
添加 : 添加到双向链表的尾部 temp 是尾节点
修改 :和单链表修改思路相同
约瑟夫问题--环形链表
单向环形链表的构建思路
约瑟夫问题--出圈的思路分析
报数前: 先让first 和 tempNode 移动k-1次
2 当开始报数的时候 first 和 tempNode 都同时移动 (m-1)次
3 这是就可以将 first 指向的小孩出圈
约瑟夫问题解决代码
栈--stack
图解
基本介绍
栈是一个先进后出的的有序集合
栈 是限制限性表中元素的插入和删除font color=\"#c41230\
栈的应用场景
3 表达式的转换中[中缀表达式转后缀表达式] 与求值
4 图形的深度优化(depth-first)搜索法
5 二叉树的遍历
实现栈的思路分析
3 取数据的时候 int val=stack[top]; top--; return val;
用数组模拟栈(stack)代码实现
用链表模拟栈代码实现
使用栈 完成计算一个表达式结果思路
1 通过index 值来遍历扫描表达式
5 最后在数字栈得到一个数字就是表达式结果
栈计算表达式代码
前缀表达式--波兰表达式
前缀表达式的计算机求值
从 font color=\"#c41230\
例如 (3+4)*5-6 对应的前缀表达式就是 - * + 3 4 5 6(数字从左向右 符号从右向左) 针对前缀表达式求值步骤如下
中缀表达式
中缀表达式就是我们font color=\"#c41230\
后缀表达式--逆波兰表达式
(3+4)*5-6 对应的后缀表达式为 3 4 + 5 * 6 -
后缀表达式的计算机求值
从font color=\"#c41230\
3 将 5压入栈中
5 将数字 6 压入栈中
完成一个逆波兰表达式--后缀表达式代码
中缀表达式转换为后缀表达式
转换步骤如下
2 从左到右扫描中缀表达式
3 遇到操作数是 将其压入 s2
5 遇到括号时
如果是左括号 ( 则直接压入s1
7 将s1中剩余的运算符依次弹出并压入s2(循环判断符号栈 只要不为空就像数字栈插入)
递归 -- recursion
递归案例
打印问题
阶乘问题
递归用于解决什么问题?
3 将用栈解决问题->递归代码比较简洁
递归需要遵守的重要规则
迷宫问题
3 测试回溯现象
4 如何求出最短路径?
小球找路代码实现
八皇后问题
1 第一个皇后先放在第一行第一列
排序算法 --Sort Algorithm
常见的排序算法分类
1 内部排序(内存): 指将需要处理的所有数据都加载到内部存储器中进行排序
算法的时间复杂度--衡量一个算法执行时间的2种方式
事后统计的方式
事前估算的方法
0 条评论
回复 删除
下一页
