Java 程序员面试宝典 - 第15章 Java编程试题

tianzhidao28

贡献于2012-07-29

字数:0 关键词: Java开发 试题 Java

第 15 章 Java 编程试题 ·299· 第 15 章 Java 编程试题 算法是任何程序的灵魂,一些开发人员认为 Java 提供了丰富的 API,已经可以比较容 易地完成大多数的功能,因此程序员可以不用管算法了,只要熟悉 API 的用法就好。这是 错误的想法,事实上,Java 程序的执行效率大多数情况下,依然是取决于开发人员的算法。 尤其对于应届毕业生,招聘单位往往不会考察应届毕业生太多实践的东西,而是要求他们 具有敏捷的一个算法头脑。不仅一些传统的经典算法是 Java 笔试或面试的重点,还有一些 开发模式也是 Java 面试考察的重点。本章将包含关于 Java 算法和开发模式一些常见面试 题,并且分析这些题目和知识点,帮助读者梳理这些方面的知识。 15.1 基础编程试题 一些简单的算法,可以通过比较少的代码表现出来。但是,通过这些代码却可以看出 求职者编程的功底和习惯。本节将集中讨论有关基础的结构化编程和数据结构算法的常见 面试题。 面试题 160 打印出 100 以内的素数 相信大多数读者都应该见过类似的题目,它本质上就是判断一个整数是否为素数。实 现可以多种多样,但是效率却不同。怎样实现才能达到高效率呢?本例在回答该问题的同 时,详细地讲解高效率的判断素数的算法。 【出现频率】 ★★★★ 【关键考点】  结构化编程基础;  编程实践能力。 【考题分析】 素数又称为质数,它的定义是:只能被 1 和被自己整除的整数。其中,1 不是素数, 任何时候都不用考虑 1。 素数的判断方法是比较明确的,就是拿比自己小的整数依次进行“除以”操作,若能 除尽则表示不是素数,因此很容易就想到如下的做法: for(int i=2;i 0) { //循环 number 的每一位数值 temp = temp * 10 + num % 10; //得到一位数字 num /= 10; //num 减少一位 } int newVal = temp; //得到转换以后的值 第 15 章 Java 编程试题 ·303· 以上代码中,关键点在于 while()循环,它所做的就是把原来的值循环的除以 10,得到 每个位置上的数字,再把每个位置的数字反过来凑成一个新的数字。这样的算法比字符串 要高明得多。 说明:10 以内的正整数不是回文数,没有判定的意义,因此可以不用判定 1~9,循环 可以从 10 开始。 【答案】 该编程题的思路大致如下: (1)完成一个把数字按位调换顺序的方法。 (2)循环 10~9999。 (3)每循环一次就判断一次,返回 true 则打印。 以下是该题目的编程示例: package ch15; public class CircleNumber { //主方法 public static void main(String[] args) { //遍历 10~100000 for (int i = 10; i < 10000; i++) { if (isCircleNumber(i)) { //判断当前数字是否是回文数字 System.out.println(i + "是回文数"); //打印 } } } //判断是否为回文数字方法 private static boolean isCircleNumber(int num) { int oldValue = num; //保存数值 int temp = 0; //反过来的值,初始化为 0 while (num > 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 < total; i++) //添加数据元素 dataList.add(new Integer(i + 1)); //定义下标,模拟已经去掉一个元素,因此从-1 开始 第 5 篇 算法和设计模式 ·306· int index = -1; //一直循环去除数据,直到只剩下一个元素 while (dataList.size() > 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 次,内循环依次重复 n–1,n–2,...,1 次。每次进行比较的两个元素都是与内循环 j 有关的,它们可以分别用 a[j]和 a[j+1]标识,i 的值依次为 1,2,...,n,对于每一个 i,j 的值依次为 1,2,...,n–i,例如下面的代码: for (int i = 0; i < arrys.length; i++) { for (int j = 0; j < arrys.length - i - 1; j++) { if (arrys[j] > arrys[j + 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 < arrys.length - j - 1; k++) { if (arrys[k] > arrys[k + 1]) {//判断当前数字与后面数字的大小 第 15 章 Java 编程试题 ·309· temp = arrys[k]; arrys[k] = arrys[k + 1]; arrys[k + 1] = temp; //用 temp 变量进行换值 } } } maopaoPrint(arrys); //打印 } //打印方法 public static void maopaoPrint(int[] before) { for (int i = 0; i < before.length; i++) { //遍历 System.out.print(before[i] + " "); //打印,以空格隔开 } 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 < len; i++) { //遍历数组,从 1 开始 int j; //定义变量 j int temp = src[i]; //临时存储当前的数字 for (j = i; j > 0; j--) { //遍历 i 之前的数字 //如果前面的数字大于后面的,则把大的值赋到后边 if (src[j - 1] > temp) { src[j] = src[j - 1]; } else //如果当前的数,不小于前面的数,那就说明不小于前面所有的数, //因为前面已经是排好了序的,所以直接通出当前一轮的比较 break; } src[j] = temp; //把空缺位置的数字赋值为原有的值 } print(src); //打印 } //打印方法 public static void print(int[] before) { for (int i = 0; i < before.length; i++) { //遍历 System.out.print(before[i] + " "); //打印,以空格隔开 } System.out.println(); //换行 } } 面试题 168 用 Java 实现一个快速排序算法 快速排序是排序算法中效率最高的一种,它的理解也比较困难。快速排序是利用递归 原理,把数组无限制的分成两个部分,直到所有数据都排好序为止。本例在回答该问题的 同时,详细地讲解快速排序的原理和实现方式。 【出现频率】 ★★★★ 【关键考点】  快速排序算法;  编程实践能力。 【考题分析】 快速排序是对冒泡排序的一种改进。它的基本思想是通过一趟排序将要排序的数据分 割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按 此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数 据变成有序序列。 如果要排序的数组是 A[0]„„ A[N–1],首先任意选取一个数据(通常选用第一个数据) 作为中间数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这 个过程称为一趟快速排序。一趟快速排序的算法如下所示。 第 15 章 Java 编程试题 ·311· (1)设置两个变量 i、j,排序开始的时候:i=1,j=N-1。 (2)以第一个数组元素作为中间数据,赋值给 pivot,即 pivot=A[0]。 (3)从 j 开始向前搜索,即由后开始向前搜索(j--),找到第一个小于 X 的值。 (4)从 i 开始向后搜索,即由前开始向后搜索(i++),找到第一个大于 X 的值,并与 上一步找到的数字交换。 (5)重复第 3、4 步,直到 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 < before.length; i++) { // 遍历 System.out.print(before[i] + " "); // 打印,以空格隔开 } System.out.println(); // 换行 } // 排序方法 static void sort(int[] a, int low, int high) { if (low >= high) //low 小于或等于 high,则直接返回 return; if ((high - low) == 1) { //如果只有两个数字,则直接比较 if (a[0] > a[1]) swap(a, 0, 1); return; } int pivot = a[low]; // 取第一个数作为中间数 // 左滑块当前的下标数,从第 2 个数字开始,从最后一个开始 int left = low + 1; int right = high; // 右滑块当前的下标数; while (left < right) { //左右循环 //从左边开始找 while (left < right && left <= high) { //如果左小于右则一直循环 if (a[left] > pivot) //找到一个大的数字没有 break; left++; //左下标往右边走一点 } // 从右边开始找 while (left <= right && right > low) { //如果左大于右则一直循环 if (a[right] <= 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 = array[i]; array[i] = array[j]; array[j] = temp; } }

下载文档,方便阅读与编辑

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 8 金币 [ 分享文档获得金币 ] 3 人已下载

下载文档

相关文档