Java程序员面试宝典——第15章 Java编程试题.pdf

第 15 章 Java 编程试题 299 第 15 章 Java 编程试题 算法是任何程序的灵魂，一些开发人员认为 Java 提供了丰富的 API，已经可以比较容易地完成大多数的功能，因此程序员可以不用管算法了，只要熟悉 API 的用法就好。这是错误的想法，事实上，Java 程序的执行效率大多数情况下，依然是取决于开发人员的算法。尤其对于应届毕业生，招聘单位往往不会考察应届毕业生太多实践的东西，而是要求他们具有敏捷的一个算法头脑。不仅一些传统的经典算法是 Java 笔试或面试的重点，还有一些开发模式也是 Java 面试考察的重点。本章将包含关于 Java 算法和开发模式一些常见面试题，并且分析这些题目和知识点，帮助读者梳理这些方面的知识。15.1 基础编程试题 一些简单的算法，可以通过比较少的代码表现出来。但是，通过这些代码却可以看出求职者编程的功底和习惯。本节将集中讨论有关基础的结构化编程和数据结构算法的常见面试题。面试题 160 打印出 100 以内的素数 相信大多数读者都应该见过类似的题目，它本质上就是判断一个整数是否为素数。实现可以多种多样，但是效率却不同。怎样实现才能达到高效率呢？本例在回答该问题的同时，详细地讲解高效率的判断素数的算法。【出现频率】【关键考点】结构化编程基础；编程实践能力。【考题分析】素数又称为质数，它的定义是：只能被 1 和被自己整除的整数。其中，1 不是素数，任何时候都不用考虑 1。素数的判断方法是比较明确的，就是拿比自己小的整数依次进行“除以”操作，若能除尽则表示不是素数，因此很容易就想到如下的做法：for(int i=2;inum;i+)/循环遍历 if(num%i=0)/取余 return false;/一旦除尽则直接返回 false 第 5 篇 算法和设计模式 300 return true;/若一直到最后都没返回，证明它是素数 以上的做法是可以达到目的的，也比较符合素数的定义。但是，效率就很低了，进行了很多次不必要的循环。例如，一个数字肯定不能被大于它的 1/2 的整数所整除，因此，改进一下 for 循环的条件，不必遍历那么多次，修改以后如下所示：for(int i=2;inum/2;i+)/循环 num 的二分之一次就够了 .尽管以上的做法已经比较有效率了，但是还不够。对数字敏感一点人就会知道，其实只需要小于该数字的二次根也是可以达到目的的，因为大于该数字二次根的数字也是不能整除了，所以，再改进一下 for 循环的条件，代码如下。for(int i=2;iMath.sprt(num);i+)/循环到 num 的二次根次就够了 .注意：以上的代码中还有一个小小的问题，就是每一次循环都进行一次取二次根的操 作，这是会影响效率的。所以，应该在循环之前就把二次根的值取好。【答案】该编程题的思路大致如下：（1）完成一个判断某整数是否为素数的方法。（2）循环 1100。（3）每循环一次就判断一次，返回 true 则打印。以下是该题目的编程示例：package ch15;public class Prime /主方法 public static void main(String args)/遍历 1 到 100 for(int i=1;i 100;i+)if(isPrime(i)/判断是否为素数 System.out.println(i);/打印素数 /判断一个整数是不是素数的方法 private static boolean isPrime(int num)if(num=1)/1 不是素数，直接返回 false return false;/从 2 开始到该整数的 2 次根之间遍历 long sprtNum=(long)Math.sqrt(num);/得到该数字的 2 次根 for(int i=2;i=sprtNum;i+)if(num%i=0)/判断是否能除尽 return false;/返回 false return true;/返回 true 第 15 章 Java 编程试题 301 面试题 161 打印九九乘法口诀表 相信没有人不知道九九乘法表吧，它就像一个梯子一样，一共 9 层，是学习算术乘法的基础。大多数人一想到它的实现，首先映入脑海的就是用两个 for 循环就可以了。但是，可不可以只用一个 for 循环就搞定呢？本例在回答该问题的同时，详细地讲解高效率的打印九九乘法表的算法。【出现频率】【关键考点】结构化编程基础；编程实践能力。【考题分析】九九乘法表，由 9 行组成，代表了 10 以内的整数之间的乘积结果。因此，很容易就会想到，用两个 for 循环，一个代表列，一个代表行，例如下面的代码：for(int i=1;i=9;i+)/遍历行 for(int j=1;j=i;j+)/遍历列，不能大于行的 i 值 System.out.print(j+*+i+=+i*j+);/打印，空格隔开 System.out.println();/换行 这是很自然的想法，也没什么大问题。但是，大家可以思考一下，能不能用一个 for循环来实现呢？答案是可以的。大体的思路是这样的：循环体内定义两个变量，一个控制列（i 变量），一个控制行（j 变量），i 变量每次循环都加一，但是它在换行以后又回到 1，j 变量则从 19，直到退出。那么，该思路的关键就在于如何判断是否该换行了，其实也比较简单，那就是一旦 i 变量自加 1 至它等于 j 变量以后，就应该换行了，循环代码如下：for(int i=1,j=1;j=9;i+)System.out.print(i+*+j+=+i*j+);if(i=j)/判断是否该换行 i=0;j+;/j 自加 1 System.out.println();/换行 【答案】该编程题的思路大致如下：（1）循环 19，采用两个循环变量，一个控制行，一个控制列。（2）每循环一次就打印一句，若控制列的循环变量到底了，则打印换行。以下是该题目的编程示例：package ch15;public class NineNineMulitTable /主方法 public static void main(String args)第 5 篇 算法和设计模式 302 /循环，初始化 i 和 j 为 1 for(int i=1,j=1;j 0)/循环 number 的每一位数值 temp=temp*10+num%10;/得到一位数字 num/=10;/num 减少一位 int newVal=temp;/得到转换以后的值 第 15 章 Java 编程试题 303 以上代码中，关键点在于 while()循环，它所做的就是把原来的值循环的除以 10，得到每个位置上的数字，再把每个位置的数字反过来凑成一个新的数字。这样的算法比字符串要高明得多。说明：10 以内的正整数不是回文数，没有判定的意义，因此可以不用判定 19，循环可以从 10 开始。【答案】该编程题的思路大致如下：（1）完成一个把数字按位调换顺序的方法。（2）循环 109999。（3）每循环一次就判断一次，返回 true 则打印。以下是该题目的编程示例：package ch15;public class CircleNumber /主方法 public static void main(String args)/遍历 10100000 for(int i=10;i 0)/循环 number 的每一位数值 temp=temp*10+num%10;/得到一位数字 num/=10;/num 减少一位 return temp=oldValue;/判断反值与原值是否相等 面试题 163 获得任意一个时间的下一天的时间 对日期的操作在日常开发中经常会使用到的。本题目表面上考察的是日期的判断，其实它真正想考察的是求职者对 Java 处理日期的原理是什么。如何用最简便的方式来得到任意时间的下一天呢？本例在回答该问题的同时，详细地讲解 Java 对日期格式的数据的处理方式。【出现频率】【关键考点】Java 的日期数据的存储原理 第 5 篇 算法和设计模式 304【考题分析】Java 提供了 java.util.Date 类来处理日期格式的数据，通过它可以得到它所代表的日期的年月日和时分秒信息。因此，可以很自然的想到，要得到任何一个时间的下一天的时间，为 Date 的 Day 数据加上 1 天即可。但是，如果是月底怎么办？如果是年底怎么办？再如果是闰年怎么办？如果要在加上 1 天之前，进行这些判断的话，这样的程序就会变得相当的复杂。注意：java.util.Date 没有时区的概念。因此如果需要使用时区的时候，请使用java.util.Calendar 类。其实，java.util.Date 类的底层的实现是通过一个 long 型的整型数据来保存日期的，这个值记录的是任何一个时间距 1970 年 1 月 1 日，0 日 0 分 0 秒的毫秒数。这里可以验证一下，通过执行下面一段代码可以得到一个整型数字 40。说明：笔者写作时的年份是 2010 年。long time=System.currentTimeMillis();/当前的毫秒数 System.out.println(time/1000/60/60/24/365);/得到距今多少年 以上的代码是用当前日志的毫秒数换算成年的单位，不偏不倚，正好是 40 年。因此，开发者完全可以不用管给定的时间是否是月底、年底或闰月的月底等条件，直接为它的毫秒数加上 24 小时所代表的毫秒数即可，然后再用新的 long 型的毫秒数构造一个新的 Date类型的对象，该 Date 对象就是给定时间的下一天时间。【答案】以下为本题目的参考实现：package ch15;import java.util.Date;public class NextDay /主方法 public static void main(String args)Date now=new Date();/获得当前时间 /打印下一天的时间 System.out.println(getNextDate(now);/获得下一天 public static Date getNextDate(Date d)long addTime=1;/以 1 为乘以的基数 addTime*=1;/1 天以后，如果是 30 天以后则这里是 30 addTime*=24;/1 天 24 小时 addTime*=60;/1 小时 60 分钟 addTime*=60;/1 分钟 60 秒 addTime*=1000;/1 秒钟=1000 毫秒 /用毫秒数构造新的日期 Date date=new Date(d.getTime()+addTime);return date;/返回结果 第 15 章 Java 编程试题 305 面试题 164 50 个人围成一圈数到 3 和 3 的倍数时出圈，问剩下的人是谁？在原来的位置是多少 出圈算法是一类比较典型的算法面试题，它可以很好地考察求职者的编程功底。由于它是一种循环的逻辑，因此它比起一般的基础算法题会更难一些。本例在回答该问题的同时，详细地讲解出圈算法的实现思路。【出现频率】【关键考点】结构化编程基础；编程实践能力。【考题分析】对于出圈的问题，它有一个比较大的困难点，就是它总是重复循环的，它的头就是它的尾巴，所以，出圈问题的循环语句是比较难写的。该题目的圈的元素个数是 50 个，每次数到 3 或 3 的倍数的时候，就把当前元素出圈，并且继续数数，直到再遇到 3 的倍数。这里，如果下标从 0 开始，一直到一圈完成以后，它就会接到圈的首部，这应该如何处理呢？其实，最好的办法就是使用取余的办法，就可以始终得到 3 个倍数，无论它的倍数是多少，也不管它的元素个数是多少。由于每次去掉元素以后，元素的个数会少一个，因此下一个 3 的倍数其实只需要走两步，在为其下标赋值的时候，需要减一，保持每次去掉的元素都是 3 的倍数。说明：如果使用从 0 开始的下标开始计算，那么初始化的时候应该使用-1，这样就可以模拟元素已经减少一个了。至于元素的保存，可以使用数组，也可以使用链表。数组的元素去掉以后，它的下一个元素是不会自动往前移动的，不太好使用，但是也可以使用。这里，最好是使用java.util.List 链表来表示，它既有下标，又可以很方便地获得元素的当前个数，尽管效率比数组要稍微低一些，不过已经足够了。【答案】该编程题的思路大致如下：（1）首先把数据填充到数组或链表中。（2）用一个 while 循环进行出圈，直到只剩下一个元素留下。以下是该题目的编程示例：package ch15;/包名 import java.util.LinkedList;import java.util.List;/测试类 public class Cycle public static int cycle(int total,int k)/功能方法 List dataList=new LinkedList();/创建链表对象 for(int i=0;i 1)index=(index+k)%dataList.size();/得到应该出局的下标 dataList.remove(index-);/去除元素 return(Integer)dataList.get(0).intValue();/返回它的值 /主方法 public static void main(String args)System.out.println(该数字原来的位置是：+cycle(50,3);该题目的结果为：11。面试题 165 将某个时间以固定格式转化成字符串 时间的表现方式有多种多样，可以只显示年、月、日，可以只显示时分秒，可以用“-”分割年月日数据，可以用冒号“：”分割时、分、秒等。那么 Java 中，应该如何来格式化日期格式呢？本例在回答该问题的同时，详细地讲解 Java 对日期格式的数据的处理方式和SimpleDateFormat 的使用方法。【出现频率】【关键考点】Java 的日期数据的存储原理；SimpleDateFormat 的使用方法。【考题分析】大家知道，日期数据用 java.util.Date 类型来表示，它默认的字符串格式一般不能满足开发需求。但是，面对纷繁乱杂的各种表示日期和时间格式的时候，如果每一个都需要开发者手动的去拼凑字符串来得到的话，是非常麻烦的。那么，JDK 中是否已经有一个比较成熟的表示日期格式的工具类呢？答案就是 java.text.SimpleDateFormat 类。SimpleDateFormat 是一个以与语言环境有关的方式来格式化和解析日期的具体类。它允许进行格式化（日期-文本）、解析（文本-日期）和规范化。它本身就代表了一种字符格式的时间数据，在创建 SimpleDateFormat 对象的时候，开发者需要提供一种格式，例如下面的代码：new SimpleDateFormat(yyyy-MM-dd HH:mm:ss);利用以上的 SimpleDateFormat 对象就可以打印出它所代表格式的时间字符串：“xxx年-xx 月-xx 日 xx 小时:xx 分钟:xx 秒”，例如下面的代码：2009-11-11 11:11:11 以上的结果为：2009 年 11 月 11 日，11 时 11 分 11 秒。那么，这些样式应该如何表示呢？它们的表示有什么特殊的规定吗？其实，SimpleDateFormat 定义了一些比较特殊的表示字符，用来为时间数据作为占位符，如以上代码中的“yyyy”、“HH”等，15.1 列出了一些常用的标示符及其含义。第 15 章 Java 编程试题 307 表 15.1 SimpleDateFormat常用匹配字符含义及使用简介 字 母 日期或时间元素 表 示 示 例 y 年 Year 09,2009 M 年份中的月 Month July,11,12 w 年份中的周 Number 27 W 月份中的周 Number 2 D 年分中的天 Number 365 d 月份中的天 Number 31 H 一天中的小时（0-23）Number 23 m 小时中的分钟 Number 59 s 分钟中的秒 Number 59 S 秒中的毫秒 Number 888 针对本题目，首先用特定的格式字符创建一个 SimpleDateFormat 对象，然后调用SimpleDateFormat 的 format()方法即可，方法的参数即为 Date 型对象，例如下面的代码：/定义字符串的格式 SimpleDateFormat sdf=new SimpleDateFormat(yyyy-MM-dd HH:mm:ss);String str=sdf.format(date);/进行格式化，并得到字符串 说明：以上示例代码的格式只是一个简单的展示，读者完全可以根据自己的需要定制不同的日期和时间样式。【答案】以下为本题目的参考实现：package ch15;import java.text.SimpleDateFormat;import java.util.Date;public class DateFormat /主方法 public static void main(String args)Date now=new Date();/得到现在的时间 System.out.println(date2FormatStr(now);/打印现在时间的字符串格式 /得到固定字符串格式的方法 public static String date2FormatStr(Date date)/定义字符串的格式 SimpleDateFormat sdf=new SimpleDateFormat(yyyy-MM-dd HH:mm:ss);String str=sdf.format(date);/进行格式化，并得到字符串 return str;/返回结果 面试题 166 用 Java 实现一个冒泡排序算法 排序是一种比较经典的算法考察题目，而冒泡排序是一种常用的易理解的排序算法，也应该算开发者需要具备的基本技能之一。本例在回答该问题的同时，详细地讲解冒泡排第 5 篇 算法和设计模式 308 序的原理和实现方式。【出现频率】【关键考点】冒泡排序算法；编程实践能力。【考题分析】冒泡（Bubble）排序的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即首先比较第 1 个和第 2 个数，将小数放前，大数放后。然后比较第 2 个数和第 3 个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。重复以上过程，仍从第一对数开始比较（因为可能由于第 2 个数和第 3 个数的交换，使得第 1 个数不再小于第 2 个数），将小数放前，大数放后，一直比较到最大数前的一对相邻数，将小数放前，大数放后，第二趟结束，在倒数第 2 个数中得到一个新的最大数。如此下去，直至最终完成排序。由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。在编程实现中，一般用二重循环实现，外循环变量设为 i，内循环变量设为 j。外循环重复 n 次，内循环依次重复 n1，n2，.，1 次。每次进行比较的两个元素都是与内循环j 有关的，它们可以分别用 aj和 aj+1标识，i 的值依次为 1，2，.，n，对于每一个 i，j的值依次为 1，2，.，ni，例如下面的代码：for(int i=0;i arrys.length;i+)for(int j=0;j arrysj+1)/判断当前数字与后面数字的大小 /把大数放后边 说明：如果是降序排列，则是把小数放在后面。【答案】以下是该题目的编程示例：package ch15;public class MaoPaoSort /主方法 public static void main(String args)int arr=3,5,7,1,8,11,9;/定义数组 maopaoSort(arr);/开始排序 /排序方法 public static void maopaoSort(int arrys)/定义临时变量 temp int temp=0;/用 j 为下标，遍历数组 for(int j=0;j arrys.length;j+)/对于每一个数组元素，从 0 到还未来排序的最大下标，总是把最大的数字放 在后面 for(int k=0;k arrysk+1)/判断当前数字与后面数字的大小 第 15 章 Java 编程试题 309 temp=arrysk;arrysk=arrysk+1;arrysk+1=temp;/用 temp 变量进行换值 maopaoPrint(arrys);/打印 /打印方法 public static void maopaoPrint(int before)for(int i=0;i before.length;i+)/遍历 System.out.print(beforei+);/打印，以空格隔开 System.out.println();/换行 面试题 167 用 Java 实现一个插入排序算法 插入排序是另外一种排序的算法，它是在已经排好序的一个序列中插入数据，并且插入以后依然是排好序的。其实，插入排序有一点像打麻将和打扑克牌，在适合的位置插入数据。本例在回答该问题的同时，详细地讲解插入排序的原理和实现方式。【出现频率】【关键考点】插入排序算法；编程实践能力。【考题分析】有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数据，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法：插入排序法。插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，该算法比较适用于少量数据的排序。插入排序算法把要排序的数组分成两部分：第一部分包含了这个数组除了最后一位的所有元素，而第二部分就只包含这一个元素。在第一部分排序后，再把最后这个元素插入到第一部分中的正确位置。说明：这里的最后一位，也可以是最前的一位。在编程实现中，一般用二重循环实现，外循环变量设为 i，内循环变量设为 j。把数组的前面一段排好序，然后把 j 依次减少，直到找到适合数组在 i 的数据，然后插入该数据，并把之后的数字往后移。【答案】以下是该题目的编程示例：package ch15;public class InsertSort /主方法 public static void main(String args)第 5 篇 算法和设计模式 310 int arr=3,5,4,1,8,11,9;/定义数组 doInsertSort2(arr);/开始排序 /排序方法 public static void doInsertSort2(int src)int len=src.length;/获取数组长度 for(int i=1;i 0;j-)/遍历 i 之前的数字 /如果前面的数字大于后面的，则把大的值赋到后边 if(srcj-1 temp)srcj=srcj-1;else /如果当前的数，不小于前面的数，那就说明不小于前面所有的数，/因为前面已经是排好了序的，所以直接通出当前一轮的比较 break;srcj=temp;/把空缺位置的数字赋值为原有的值 print(src);/打印 /打印方法 public static void print(int before)for(int i=0;i=j。（6）然后把 j 所在的数字与 pivot 交换。（7）最后把 j 以前的数组和 j 到最后的数组，再进行递归的快速排序。【答案】以下是该题目的编程示例：package ch15;public class QuickSort /主方法 public static void main(String args)int a=new int 5,9,8,4,7,3,6,2;/定义数组 print(a);/打印之前的顺序 sort(a,0,a.length-1);/排序 print(a);/打印排序后的结果 /打印方法 public static void print(int before)for(int i=0;i=high)/low 小于或等于 high，则直接返回 return;if(high-low)=1)/如果只有两个数字，则直接比较 if(a0 a1)swap(a,0,1);return;int pivot=alow;/取第一个数作为中间数 /左滑块当前的下标数，从第 2 个数字开始，从最后一个开始 int left=low+1;int right=high;/右滑块当前的下标数；while(left right)/左右循环 /从左边开始找 while(left right&left pivot)/找到一个大的数字没有 break;left+;/左下标往右边走一点 /从右边开始找 while(left low)/如果左大于右则一直循环 if(aright=pivot)/找到一个小的数字没有 break;第 5 篇 算法和设计模式 312 right-;/右下标往左走一点 if(left right)/如果还没找完，则交换数字 swap(a,right,left);swap(a,low,right);/交换中间数字 sort(a,low,right);/排序前面数组 sort(a,right+1,high);/排序后边数组 /掉位方法 private static void swap(int array,int i,int j)int temp;temp=arrayi;arrayi=arrayj;arrayj=temp;