【计算机类职业资格】(Java)程序员面试-16及答案解析.doc

1、(Java)程序员面试-16 及答案解析(总分：100.00，做题时间：90 分钟)一、论述题(总题数：29，分数：100.00)1.如何找出数组中重复元素最多的数 （分数：3.50）_2.如何求数组中两两相加等于 20 的组合种数 （分数：3.50）_3.如何把一个数组循环右移 k 位 （分数：3.50）_4.如何找出数组中第 k 个最小的数 （分数：3.50）_5.如何找出数组中只出现一次的数字 （分数：3.50）_6.如何找出数组中唯一的重复元素 （分数：3.50）_7.如何用递归方法求一个整数数组的最大元素 （分数：3.50）_8.如何求数对之差的最大值 （分数：3.50）_9.如何求

2、绝对值最小的数 （分数：3.50）_10.如何求数组中两个元素的最小距离 （分数：3.50）_11.如何求指定数字在数组中第一次出现的位置 （分数：3.50）_12.如何对数组的两个子有序段进行合并 （分数：3.50）_13.如何计算两个有序整型数组的交集 （分数：3.50）_14.如何判断一个数组中数值是否连续相邻 （分数：3.50）_15.如何求解数组中反序对的个数 （分数：3.50）_16.如何求解最小三元组距离 （分数：3.50）_17.如何实现字符串的反转 （分数：3.50）_18.如何判断两个字符串是否由相同的字符组成 （分数：3.50）_19.如何删除字符串中重复的字符 （分数：

3、3.50）_20.如何统计一行字符中有多少个单同 （分数：3.50）_21.如何按要求打印数组的排列情况 （分数：3.50）_22.如何输出字符串的所有组合 （分数：3.50）_23.二叉树基本概念 （分数：3.50）_24.如何实现二叉排序树 （分数：3.50）_25.如何层序遍历二叉树 （分数：3.50）_26.已知先序遍历和中序遍历，如何求后序遍历 （分数：3.50）_27.如何求二叉树中结点的最大距离 （分数：3.00）_28.如何消除嵌套的括号 （分数：3.00）_29.如何不使用比较运算就可以求出两个数的最大值与最小值 （分数：3.00）_(Java)程序员面试-16 答案解析(总

4、分：100.00，做题时间：90 分钟)一、论述题(总题数：29，分数：100.00)1.如何找出数组中重复元素最多的数 （分数：3.50）_正确答案：()解析：问题描述：对于数组1，1，2，2，4，4，4，4，5，5，6，6，6，元素 1 出现的次数为 2 次，元素 2 出现的次数为 2 次，元素 4 出现的次数为 4 次，元素 5 出现的次数为 2 次，元素 6 出现的次数为 3 次，找出数组中出现重复次数最多的数。 上述问题中，程序的输出应该为元素 4。 可以采取如下两种方法来计算数组中重复次数最多的数。 方法一：空间换时间。可以定义一个数组 int countMAX，并将其数组元素都初

5、始化为 0，然后执行for(int i=0; i100; i+)countAi+操作，在 count 数组中找最大的数，即为重复次数最多的数。这是一种典型的空间换时间的算法。一般情况下，除非内存空间足够大，一般不采用这种方法。 方法二：使用 Map 映射表。通过引入 Map 映射表(Map 提供一对一的数据处理能力，其中第一个为关键字，每个关键字只能在 Map 中出现一次，第二个称为该关键字的值)来记录每一个元素出现的次数，然后判断次数大小，进而找出重复次数最多的元素。示例如下： import java.util.*; public class Test public static int f

6、indMostFrequentInArray(inta) int result=0; int size=a.length; if(size=0) return Integer.MAX_VALUE; /记录每个元素出现的次数 MapInteger, Integerm=new HashMapInteger, Integer(); for(int i=0; isize; i+) if(m.containsKey(ai) m.put(ai, m.get(ai)+1); else m.put(ai, 1); /找出出现次数最多的元素 int most=0; Iterator iter=m.entrySe

7、t().iterator(); while(iter.hasNext() Map.Entry entry=(Map.Entry)iter.next(); int key=(Integer)entry.getKey(); int val=(Integer)entry.getValue(); if(valmost) result=key; most=val; return result; public static void main(Stnngargs) int array=1, 5, 4, 3, 4, 4, 5, 4, 5, 5, 6, 6, 6, 6, 6; int maxFrequence

8、Num=findMostFrequentInArray(array); System.out.println(maxFrequenceNum); 程序运行结果为： 62.如何求数组中两两相加等于 20 的组合种数 （分数：3.50）_正确答案：()解析：问题描述：给定一个数组1，7，17，2，6，3，14，这个数组中满足条件的有两对组合17+3=20 和 6+14=20。 方法一：“蛮力”法 最容易想到的方法就是采用两重循环遍历数组来判断两个数的和是否为 20。实现代码如下： public class Test public static void findSum(inta, int sum)

9、 int len=a.length; for(int i=0; ilen; i+) for(int j=i; jlen; j+) if(ai+aj=sum) System.out.println(ai+“, “+aj); public static void main(Stringargs) int array=1, 7, 17, 2, 6, 3, 14; findSum(array, 20); 程序运行结果为： 17, 3 6, 14 由于采用了双重循环，因此这个算法的时间复杂度为 O(n2)。 方法二：排序法 先对数组元素进行排序，可以选用堆排序或快速排序，此时算法的时间复杂度为 O(nl

10、ogn)，然后对排序后的数组分别从前到后和从后到前遍历，假设从前往后遍历的下标为 begin，从后往前遍历的下标为end，那么当满足 arrbegin+arrend20 时，如果存在两个数的和为 20，那么这两个数一定在begin+1，end之间；当满足 arrbegin+arrend20 时，如果存在两个数的和为 20，那么这两个数一定在begin，end+1之间。这个过程的时间复杂度为 O(n)，因此整个算法的时间复杂度为 O(nlogn)。实现代码如下： import java.util.Arrays; public class Test public static void findS

11、um(inta, int sum) Arrays.sort(a); int begin=0; int end=a.length-1; while(beginend) if(abegin+aendsum) begin+; else if(abegin+aendsum) end-; else System.out.println(abegin+“, “+aend); begin+; end-; public static void main(Stringargs) int array=1, 7, 17, 2, 6, 3, 14; findSum(array, 20); 程序运行结果为： 3, 17

12、 6, 14 这个算法的时间复杂度主要由排序算法的时间复杂度来决定。因此，选择时间复杂度较低的排序算法能显著提高该算法的效率。3.如何把一个数组循环右移 k 位 （分数：3.50）_正确答案：()解析：假设要把数组序列 12345678 右移 2 位变为 78123456，比较移位前后数组序列的形式，不难看出，其中有两段序列的顺序是不变的，即 78 和 123456，可以把这两段看作两个整体，右移 k 位就是把数组的两部分交换一下。鉴于此，可以设计这样一种算法，步骤如下(以数组序列 12345678 为例)： 1)逆序数组子序列 123456，数组序列的形式变为 65432178。 2)逆序数

13、组子序列 78，数组序列的形式变为 65432187。 3)全部逆序，数组序列的形式变为 78123456。 程序代码如下： public class Test public static void reverse(int a, int b, int e) for(; be; b+, e-) int temp=ae; ae=ab; ab=temp; public static void shift_k(int a, int k) int n=a.length; k=k%n;/为了防止 k 比 n 大，右移 k 位跟右移 k%n 位的结果是一样的 reverse(a, n-k, n-1); re

14、verse(a, 0, n-k-1); reverse(a, 0, n-1); public staric void main(Stringargs) int array=1, 2, 3, 4, 5, 6, 7, 8; shift_k(array, 2); for(int i=0; iarray.length; i+) System.out.print(arrayi+“); 程序运行结果如下： 7 8 1 2 3 4 5 6 从上例中可以看出，该算法只进行了 3 次逆序操作，因此时间复杂度为 O(n)。4.如何找出数组中第 k 个最小的数 （分数：3.50）_正确答案：()解析：问题描述：给定

15、一个无序的数组，从一个数组中找出第 k 个最小的数，例如，对于给定数组序列1，5，2，6，8，0，6，其中第 4 小的数为 5。 方法一：排序法 最容易想到的方法就是对数组进行排序，排序后的数组中第 k-1 个位置上的数字即为数组的第 k 个最小的数(原因是数组下标从 0 开始计数)，这种方法最好的时间复杂度为 O(nlogn)。 方法二：“剪枝”法 采用快速排序的思想来实现。主要思路如下：选一个数 tmp=an-1作为枢纽，把比它小的数都放在它的左边，比它大的数都放在它的右边，然后判断 tmp 的位置，如果它的位置为 k-1，那么它就是第 k 个最小的数；如果它的位置小于 k-1，那么说明第

16、 k 个小的元素一定在数组的右半部分，采用递归的方法在数组的右半部分继续查找；否则第 k 个小的元素在数组的左半部分，采用递归的方法在左半部分数组中继续查找。示例如下： public class Test public static int quikSort(int array, int low, int high, int k) int i, j; int tmp; if(lowhigh) return Integer.MIN_VALUE; i=low+1; j=high; tmp=arrayi; while(ij) while(ij if(ij) arrayi+=arrayj; while

17、(ij if(ij) arrayj-=arrayi; arrayi=tmp; if(i+1=k) return tmp; else if(i+1k) return quikSort(array, low, i-1, k); else return quikSort(array, i+1, high, k); public static int getKMin(int array, int k) if(array=null) return Integer.MIN_VALUE; if(array.lengthk) return Integer.MIN_VALUE; return quikSort(

18、array, 0, array.length-1, k); public static void main(Stringargs) int a=1, 5, 2, 6, 8, 0, 6; int kMin=getKMin(a, 4); System.out.println(kMin); 程序运行结果为： 5 表面上看起来这种方法还是在对数组进行排序，但是它比排序法的效率高，主要原因是当在数组右半部分递归查找时，完全不需要关注左半部分数组的顺序，因此省略了对左半部分数组的排序。因此，这种方法可以被看作一种“剪枝”方法，不断缩小问题的规模，直到找到第 k 个小的元素。5.如何找出数组中只出现一次的数

19、字 （分数：3.50）_正确答案：()解析：问题描述：一个整型数组里除了一个数字之外，其他数字都出现了两次。找出这个只出现 1 次的数字。要求时间复杂度是 O(n)，空间复杂度是 O(1)。 如果本题对时间复杂度没有要求，最容易想到的方法就是先对这个整型数组排序，然后从第一个数字开始遍历，比较相邻的两个数，从而找出这个只出现 1 次的数字，这种方法的时间复杂度最快为 O(nlogn)。 由于时间复杂度与空间复杂度的限制，该方法不可取，因此需要一种更高效的方式。题目强调只有一个数字出现 1 次，其他数字出现了两次，首先想到的是异或运算，根据异或运算的定义可知，任何一个数字异或它自己都等于 0，所

20、以，如果从头到尾依次异或数组中的每一个数字，那些出现两次的数字全部在异或中会被抵消掉，最终的结果刚好是这个只出现 1 次的数字。示例如下： public class Test public static int findNotDouble(int a) int n=a.length; int resuh=a0; int i; for(i=1; in; +j) result=ai; return result; public static void main(Stringargs) int array=1, 2, 3, 2, 4, 3, 5, 4, 1; int num=findNotDoubl

21、e(array); System.out.println(num); 程序运行结果为： 5 引申：如果题目改为数组 A 中，一个整型数组里除了一个数字之外，其他数字都出现了 3 次，那么如何找出这个数? 上述异或运算的方法只适用于其他数字出现的次数为偶数的情况，如果其他数字出现的次数为奇数，上述介绍的方法则不再适用。如果数组中的所有数都出现 n 次，那么这个数组中的所有数对应的二进制数中，各个位上的 1 出现的个数均可以被 n 整除。以 n=3 为例，假如数组中有如下元素：1，1，1，2，2，2，它们对应的二进制表示为 01，01，01，10，10，10。显然，这个数组中的所有数字对应的二进制

22、数中第0 位有 3 个 1，第 1 位有 3 个 1。对于本题而言，假设出现一次的这个数为 a，那么去掉 a 后其他所有数字对应的二进制数的每个位置出现 1 的个数为 3 的倍数。因此可以对数组中的所有数字对应的二进制数中各个位置上 1 的个数对 3 取余数，就可以得到出现 1 次的这个数的二进制表示，从而可以找出这个数。示例如下： public class Test public static int findOnee(int a, int appearTimes) int n=a.length; intbitCount=new int32; /计算数组中所有数组对应的二进制数各个位置上出现

23、 1 的次数 for(int i=0; in; i+) for(int j=0; j32; j+) bitCountj+=(ai j) /若某位上的结果不能被整除，则肯定目标数字在这一位上 int appearOne=0; for(int i=0; i32; i+) if(bitCounti%appearTimes!=0) appearOne+=(1 i); return appearOne; public static void nlain(Stringargs) int array=1, 2, 1, 2, 4, 2, 4, 4, 1, 3; int num=findOnce(array,

24、3); System.out.println(num); 程序运行结果为： 3 此外，这种方法不仅适用于求解其他数字出现个数为奇数的情况，也适用于求解出现次数为偶数的情况，具有更好的通用性。6.如何找出数组中唯一的重复元素 （分数：3.50）_正确答案：()解析：问题描述：数组 aN，1N-1 这 N-1 个数存放在 aN中，其中某个数重复 1 次。写一个函数，找出被重复的数字。要求每个数组元素只能访问 1 次，并且不用辅助存储空间。 由于题目要求每个数组元素只能访问 1 次，且不用辅助存储空间，因此可以从原理上入手，采用数学求和法，因为只有一个数字重复 1 次，而又是连续的，根据累加和原理，

25、对数组的所有项求和，然后减去1N-1 的和，即为所求的重复数。示例如下： public class Test public static int xor_findDup(inta) int n=a.length; int tmp1=0; int tmp2=0; for(int i=0; in-1; +i) tmp1+=(i+1); tmp2+=ai; tmp2+=an-1; int result=tmp2-tmp1; return result; public static void main(Stringargs) int a=1, 2, 1, 3, 4; int missingNum=xo

26、r_findDup(a); System.out.println(missingNum); 程序运行结果为： 1 如果题目没有要求每个数组元素只能访问 1 次，且不允许使用辅助存储空间，还可以用异或法和位图法来求解。 (1)异或法 根据异或法的计算方式，每两个相异的数执行异或运算之后，结果为 1；每两个相同的数执行异或运算之后，结果为 0，所以，数组 aN中的 N 个数异或结果与 1N-1 异或的结果再做异或运算，得到的值即为所求。 设重复数为 A，其余 N-2 个数异或结果为 B，N 个数异或结果为 AAB，1N-1 异或结果为 AB，由于异或满足交换律和结合律，且 XX=0，0X=X，则有

27、(AB)(AAB)=ABB=A。示例如下： public class Test public static int xor_findDup(inta) int n=a.length; int i; int result=0; for(i=0; in; i+) result=ai; for(i=1; in; i+) result=i; return result; public static void main(Stringargs) int a=1, 2, 1, 3, 4; int missingNum=xor_findDup(a); System.out.println(missingNum

28、); 程序运行结果为： 1 (2)空间换时间法 申请长度为 N-1 的整型数组 flag 并初始化为 0，然后从头开始遍历数组 a，取每个数组元素 ai的值，将其对应的数组 flag 中的元素赋值为 1，如果已经置过 1，那么该数就是重复的数。示例如下： public class Test public static int findInteger(inta) int n=a.length; booleanarrayflag=new booleann; int i=1; int result=Integer.MAX_VALUE; while(in) arrayflagi=false; i+;

29、for(i=0; in; i+) if(arrayflagai=false) arrayflagai=true; else result=ai; return result; public staric void main(Stringargs) int a=1, 2, 1, 3, 4; int missingNum=findInteger(a); System.out.println(missingNum); 程序运行结果为： 1 这种方法的空间复杂度比较大，需要申请长度为 N 的整数数组。当然也可以通过使用位图的方法来降低空间复杂度，即不是用一个整型数字来表示元素是否出现过(0 表示未出现

30、，1 表示出现过)，而是使用 1bit来表示，因此需要申请数组的长度为 N/32 取上整。 此题可以进行一个变形：取值为1，n-1含 n 个元素的整数数组，至少存在一个重复数，即可能存在多个重复数，O(n)时间内找出其中任意一个重复数，例如，array=1，2，2，4，5，4，则 2 和 4 均是重复元素。 方案一：位图法。使用大小为 n 的位图，记录每个元素是否已经出现过，一旦遇到一个已经出现过的元素，则直接将之输出。该方法的时间复杂度是 O(n)，空间复杂度为 O(n)。 方案二：数组排序法。先对数组进行计数排序，然后顺序扫描整个数组，一旦遇到一个已出现的元素，则直接将之输出。该方法的时间

31、复杂度为 O(n)，空间复杂度为 O(n)。 以上提出的两种方案都需要额外的存储空间，能否不使用额外存储空间呢?答案是可以。于是想到了方案三：取反法。取反：去的基本思路如下：如果遍历到数组中的元素为 i，那么把 ai的值取反，如果 i 在数组中出现两次，那么 ai会经过两次取反操作，ai的值跟原始的值相等，且为正数；如果 i 出现了1 次，那么 ai的值为原始值的相反数，且为负数，可以根据这个原理来实现。实现方法如下：将数组元素值作为索引，对于元素 arryi，如果 arrayarrayi大于 0，那么设置 arrayarrayi=-arrayarrayi；如果 arrayarrayi小于 0

32、，那么设置 array-arrayi=-array-arrayi，最后从数组第二个元素开始遍历数组，如果 arrayi0，那么这个数就是重复的。由于在进行遍历后对数组中的数据进行了修改，因此需要对数据进行还原(对数组中的负数取反)。示例如下： public class Test public static int xor_findDup(inta) int n=a.length; int result=Integer.MAX_VALUE; for(int i=0; in; i+) if(ai0) aai=-aai; else a-ai=-a-ai; for(int i=1; in; i+) i

33、f(ai0) result=i; else ai=-ai; return result; public static void main(Stringargs) int a=4, 2, 1, 3, 4; int missingNum=xor_findDup(a); System.out.println(missingNum); 方法四是一种非常“诡异”的算法，就是采用类似于单链表是否存在环的问题。“判断单链表是否存在环”是一个非常经典的问题，同时单链表可以采用数组实现，此时每个元素值作为 next 指针指向下一个元素。本题可以转化为“已知一个单链表中存在环，找出环的入口点”这种想法。具体思路如

34、下：将 arrayi看作第 i 个元素的索引，即 arrayiarrayarrayiarrayarrayarrayiarrayarrayarrayarrayi，最终形成一个单链表，由于数组 a 中存在重复元素，因此一定存在一个环，且环的入口元素即为重复元素。 该题的关键在于，数组 array 的长度是 n，而元素的范围是1，n-1，所以 array0不会指向自己，进而不会陷入错误的自循环。如果元素的范围中包含 0，那么该题不可直接采用该方法。示例如下： public class Test1 public static int findInteger(int a) int x, y; x=y=0

35、; do x=aax; /x 一次走两步 y=ay; /y 一次走一步 while(x!=y); /找到环中的一个点 x=0; do x=ax; y=ay; while(x!=y); /找到入口点 return x; public static void main(Stringargs) int a=1, 2, 1, 3, 4; int missingNum=findInteger(a); System.out.println(missingNum); 程序运行结果为： 17.如何用递归方法求一个整数数组的最大元素 （分数：3.50）_正确答案：()解析：对于本题而言，最容易实现的方法为对数组

36、进行遍历，定义一个变量 max 为数组的第一个元素，然后从第二个元素开始遍历，在遍历过程中，每个元素都与 max 的值进行比较，若该元素的值比 max 的值大，则把该元素的值赋给 max。当遍历完数组后，最大值也就求出来了。而使用递归方法求解的主要思路为：递归的求解“数组第一个元素”与“数组中其他元素组成的子数组的最大值”的最大值。示例如下： public class Test private int max(int a, int b) return ab?a:b; p public int maxnum(int a, int begin) int length=a.length-begin; it(length=1) return abegin; else return max(abegin, maxnum(a, begin+1); public static void main(Stringargs) Test t=new Test(); intnum=0, 16, 2, 3, 4, 5, 10, 7, 8, 9; System.out.println(t.maxnum(num, 0); 程序运行结果为： 168.如何求数对之差的最大值 （分数：3.50）_正确答案：()解析：问题描述：数组中的一个数字