我的网站被黑了,空白word个人简历模板下载,免费全自动网页制作系统,thinkphp只能做网站上一讲#xff0c;我给大家简单介绍了一下数据结构#xff0c;以及数据结构与算法之间的关系#xff0c;照理来说#xff0c;接下来我就应该要给大家详细介绍线性结构和非线性结构了#xff0c;但是在此之前#xff0c;我决定还是先带着大家看几个实际编程中遇到的问题我给大家简单介绍了一下数据结构以及数据结构与算法之间的关系照理来说接下来我就应该要给大家详细介绍线性结构和非线性结构了但是在此之前我决定还是先带着大家看几个实际编程中遇到的问题看完之后咱们再说。
第一个问题一个有关单链表的面试题
如下所示有这样一段Java代码我想这段Java代码大家应该都能看得懂吧无非就是使用字符串类的replaceAll方法将指定字符串中的Java子串全部替换成了李阿昀~So EasyreplaceAll方法大家应该都见过吧它就是用来做字符串替换的。
public static void main(String[] args) {String str Java, Java, hello, world!;String newStr str.replaceAll(Java, 李阿昀~); // 算法System.out.println(newStr newStr);
}那么我现在就要问大家了replaceAll方法的提供者在进行字符串替换时它到底是怎么做的呢想都不用想里面必定会有一个算法来做支撑就是而且这个算法你还要能看得懂否则坏事势必就会频发你想啊我们去开发一个程序如果你连别人底层的代码都看不懂那么你自己去优化程序不就是成无稽之谈了嘛
总之replaceAll方法内部有一个算法而且它是专门来研究字符串是如何进行替换的。
接下来我们不妨来看一个有关单链表的面试题。 试写出用单链表表示的字符串类及字符串结点类的定义并依次实现它的构造函数以及计算串长度、串赋值、判断两串相等、求子串、两串连接、求子串在串中位置等7个成员函数。 注意以上题目中有个函数的概念而它其实就是我们Java里面的方法。
想必大家在大学里面学数据结构时老师一定给你们布置过很多的练习题吧而这其中不乏就有关于链表的练习题而且初看还具有一定难度例如以上那道有关单链表的面试题你应该遇到过这样的练习题吧要是没遇到过那我想你的数据结构一定没学好因为学数据结构你不大量的练习你怎么学得好啊
还是说回来上面那道有关单链表的面试题其实这道面试题要求很明确就是用单链表来实现字符串类的相关功能而单链表正是数据结构中的一种如果你没有学过单链表这种数据结构那么这道面试题很显然你就完成不了。总之这道面试题必须建立在大家对单链表了解的基础上才能完成得了。
第二个问题一个五子棋程序
接下来我们来看一个比较经典的、同学们也玩过的游戏即五子棋程序。 从上图中能看到一个五子棋程序最基本的要求有 判断游戏的输赢不管是黑子赢也好还是蓝子赢也好。 相信大家都知道五子棋游戏输赢的规则吧很简单就是看哪一方先把5颗子下得粘成一串谁先就谁赢。于是你是不是得要写个算法来判断游戏输赢啊 存盘退出。 继续上局。 悔棋。 就是这一步我不满意我要悔一步棋。
大家想一下如果这个五子棋程序让你来实现那么你会怎么去做呢要不我先来说说我的分析吧
首先我们需要把五子棋盘映射成一个二维数组这样当别人每下一个子的时候便会有一个元素来记录所下的子到底是一颗黑子还是一颗蓝子了然后将二维数组写入磁盘文件这样我们就可完成存档退出的功能了接着从磁盘读取文件读取文件过后重新将其恢复成原先的二维数组当把这个二维数组再次恢复成我们棋盘的形式时我们也就完成了续上局的功能。
可想而知如果你没有学过二维数组这种数据结构那么你怎么可能会写出这样一个五子棋程序呢必然是写不来的对吧
而且要想能写出性能优秀的五子棋程序你还得考虑一个问题什么问题呢就是压缩问题。你看啊在上面我们那个棋盘里其实我们只放了5个棋子但是整个棋盘却很大故这必然会导致所映射成的二维数组里面将记录很多没有意义的数据即默认值0也即白白浪费掉了那些存储空间。于是大家可能就会想了能不能对二维数组进行压缩啊就只让它记录有意义的数据其实这是可以的因为二维数组里面有一种数组就可以实现压缩和解压的效果它便是稀疏数组。
有了稀疏数组这种数据结构之后五子棋程序中的存档退出、续上局的功能就得像下面这样去实现了即
存档退出首先我们需要把五子棋盘映射成一个二维数组这样当别人每下一个子的时候便会有一个元素来记录所下的子到底是一颗黑子还是一颗蓝子了然后将二维数组转成稀疏数组即压缩接着再写入磁盘文件这样我们就完成了存档退出的功能。续上局首先从磁盘读取文件注意这时读取出来的可是一个稀疏数组哟然后将读取出来的稀疏数组转成原先的二维数组即解压当把这个二维数组再次恢复成我们棋盘的形式时我们也就完成了续上局的功能。
大家试想一下如果你没有学过稀疏数组这种数据结构那么你怎么可能会写出这样一个五子棋程序呢必然是写不来的对吧就算能写你最多也就只能做到将五子棋盘映射成一个二维数组然后再写入磁盘文件这一步了但你要是学过稀疏数组那情况可就大不同了你是可以对程序进行优化的说得直白点就是可以使用较少的数据来保存棋盘。
嘻嘻数组这种数据结构的重要性是不是就这样被凸显出来了啊
第三个问题约瑟夫Josephu问题丢手帕问题
接下来我们再来看一个非常经典的案例即约瑟夫问题当然它也被叫作丢手帕问题。
我依稀还记得当年我大学刚毕业找工作时还做过这样一个面试题回头一看那已经是2014年6月份的事情了那时候我大学刚毕业还很年轻而今离毕业都快9年了真是岁月如梭啊都说时间是把杀猪刀可我怎么依旧还是这么的帅气呢哈哈哈有点恬不知耻了主要是我还没秃头啊
思绪还是回到我大学刚毕业找工作那会啊我记得当时遇到的那道面试题即约瑟夫问题是被要求要在Unix环境下用C语言写代码来解决的而且我还记得我有用到环形链表因为那个时候人们都知道约瑟夫问题得用环形链表来解决。
下面我就来给大家简单讲讲这个约瑟夫问题吧
约瑟夫问题很简单它是这样描述的设编号为12···n的n个人围坐一圈约定编号为k1kn的人从1开始报数数到m的那个人出列他的下一位又从1开始报数数到m的那个人又出列依次类推直到所有人出列为止此时便能由此产生一个出队编号的序列了请问这个出队编号的序列是什么 经过我上面的介绍现在大家该知道非常之经典的约瑟夫问题到底是一个什么问题了吧知道之后接下来我们就要分析约瑟夫问题该怎么去解决了。
这里我就给大家直说吧我们可以用一个不带头结点的循环链表来处理约瑟夫问题即先构成一个有n个结点的单循环链表单循环链表也叫单向环形链表然后由k结点起从1开始计数计到m时对应结点从链表中删除接着再从被删除结点的下一个结点又从1开始计数直到最后一个结点从链表中删除算法即结束。
注意单向环形链表是我们后面要讲的一个重点所以大家到时候可一定要认真学哟不然的话你怎么使用它来解决约瑟夫问题啊你还想不想知道最终的出队编号序列了
总之如果你有学过单向环形链表这种数据结构那么恭喜你你就能使用这种数据结构来解决约瑟夫问题了要知道使用单向环形链表这种数据结构来解决约瑟夫问题可是非常形象的哟如果你没有学过这种数据结构那么很可惜你就只能退而求其次使用数组来解决了说实话这样做还是有些困难的。
其他常见算法问题
。。。
