Java程序员面试题集（136-150）(转)

2021-09-30 23:07:57

转；http://blog.csdn.net/jackfrued/article/details/17740651

Java程序员面试题集（136-150）

摘要：这一部分主要是数据结构和算法相关的面试题目，虽然只有15道题目，但是包含的信息量还是很大的，很多题目背后的解题思路和算法是非常值得玩味的。

136、给出下面的二叉树先序、中序、后序遍历的序列？

Java程序员面试题集（136-150）(转)

答：先序序列：ABDEGHCF；中序序列：DBGEHACF；后序序列：DGHEBFCA。

补充：二叉树也称为二分树，它是树形结构的一种，其特点是每个结点至多有二棵子树，并且二叉树的子树有左右之分，其次序不能任意颠倒。二叉树的遍历序列按照访问根节点的顺序分为先序（先访问根节点，接下来先序访问左子树，再先序访问右子树）、中序（先中序访问左子树，然后访问根节点，最后中序访问右子树）和后序（先后序访问左子树，再后序访问右子树，最后访问根节点）。如果知道一棵二叉树的先序和中序序列或者中序和后序序列，那么也可以还原出该二叉树。

例如，已知二叉树的先序序列为：xefdzmhqsk，中序序列为：fezdmxqhks，那么还原出该二叉树应该如下图所示：

Java程序员面试题集（136-150）(转)

137、你知道的排序算法都哪些？用Java写一个排序系统。

答：稳定的排序算法有：插入排序、选择排序、冒泡排序、鸡尾酒排序、归并排序、二叉树排序、基数排序等；不稳定排序算法包括：希尔排序、堆排序、快速排序等。

下面是关于排序算法的一个列表：

Java程序员面试题集（136-150）(转)

下面按照策略模式给出一个排序系统，实现了冒泡、归并和快速排序。

Sorter.java

  1. package com.jackfrued.util;
  2. import java.util.Comparator;
  3. /**
  4. * 排序器接口(策略模式: 将算法封装到具有共同接口的独立的类中使得它们可以相互替换)
  5. * @author骆昊
  6. *
  7. */
  8. public interfaceSorter {
  9. /**
  10. * 排序
  11. * @param list 待排序的数组
  12. */
  13. public <T extends Comparable<T>>void sort(T[] list);
  14. /**
  15. * 排序
  16. * @param list 待排序的数组
  17. * @param comp 比较两个对象的比较器
  18. */
  19. public <T> void sort(T[] list,Comparator<T> comp);
  20. }

BubbleSorter.java

  1. package com.jackfrued.util;
  2. import java.util.Comparator;
  3. /**
  4. * 冒泡排序
  5. * @author骆昊
  6. *
  7. */
  8. public classBubbleSorter implements Sorter {
  9. @Override
  10. public <T extends Comparable<T>>voidsort(T[] list) {
  11. boolean swapped = true;
  12. for(int i = 1; i < list.length && swapped;i++) {
  13. swapped= false;
  14. for(int j = 0; j < list.length - i; j++) {
  15. if(list[j].compareTo(list[j+ 1]) > 0 ) {
  16. Ttemp = list[j];
  17. list[j]= list[j + 1];
  18. list[j+ 1] = temp;
  19. swapped= true;
  20. }
  21. }
  22. }
  23. }
  24. @Override
  25. public <T> void sort(T[] list,Comparator<T> comp) {
  26. boolean swapped = true;
  27. for(int i = 1; i < list.length && swapped;i++) {
  28. swapped= false;
  29. for(int j = 0; j < list.length - i; j++) {
  30. if(comp.compare(list[j],list[j + 1]) > 0 ) {
  31. Ttemp = list[j];
  32. list[j]= list[j + 1];
  33. list[j+ 1] = temp;
  34. swapped= true;
  35. }
  36. }
  37. }
  38. }
  39. }

MergeSorter.java

  1. package com.jackfrued.util;
  2. import java.util.Comparator;
  3. /**
  4. * 归并排序
  5. * 归并排序是建立在归并操作上的一种有效的排序算法。
  6. * 该算法是采用分治法（divide-and-conquer）的一个非常典型的应用，
  7. * 先将待排序的序列划分成一个一个的元素，再进行两两归并，
  8. * 在归并的过程中保持归并之后的序列仍然有序。
  9. * @author骆昊
  10. *
  11. */
  12. public classMergeSorter implements Sorter {
  13. @Override
  14. public <T extends Comparable<T>>voidsort(T[] list) {
  15. T[]temp = (T[]) newComparable[list.length];
  16. mSort(list,temp, 0, list.length- 1);
  17. }
  18. private <T extends Comparable<T>>voidmSort(T[] list, T[] temp, int low, inthigh) {
  19. if(low == high) {
  20. return ;
  21. }
  22. else {
  23. int mid = low + ((high -low) >> 1);
  24. mSort(list,temp, low, mid);
  25. mSort(list,temp, mid + 1, high);
  26. merge(list,temp, low, mid + 1, high);
  27. }
  28. }
  29. private <T extends Comparable<T>>voidmerge(T[] list, T[] temp, int left, intright, intlast) {
  30. int j = 0;
  31. int lowIndex = left;
  32. int mid = right - 1;
  33. int n = last - lowIndex + 1;
  34. while (left <= mid && right <= last){
  35. if (list[left].compareTo(list[right]) < 0){
  36. temp[j++] = list[left++];
  37. } else {
  38. temp[j++] = list[right++];
  39. }
  40. }
  41. while (left <= mid) {
  42. temp[j++] = list[left++];
  43. }
  44. while (right <= last) {
  45. temp[j++] = list[right++];
  46. }
  47. for (j = 0; j < n; j++) {
  48. list[lowIndex + j] = temp[j];
  49. }
  50. }
  51. @Override
  52. public <T> void sort(T[] list,Comparator<T> comp) {
  53. T[]temp = (T[]) newComparable[list.length];
  54. mSort(list,temp, 0, list.length- 1, comp);
  55. }
  56. private <T> void mSort(T[] list, T[]temp, intlow, inthigh, Comparator<T> comp) {
  57. if(low == high) {
  58. return ;
  59. }
  60. else {
  61. int mid = low + ((high -low) >> 1);
  62. mSort(list,temp, low, mid, comp);
  63. mSort(list,temp, mid + 1, high, comp);
  64. merge(list,temp, low, mid + 1, high, comp);
  65. }
  66. }
  67. private <T> void merge(T[] list, T[]temp, intleft, intright, intlast, Comparator<T> comp) {
  68. int j = 0;
  69. int lowIndex = left;
  70. int mid = right - 1;
  71. int n = last - lowIndex + 1;
  72. while (left <= mid && right <= last){
  73. if (comp.compare(list[left], list[right]) <0) {
  74. temp[j++] = list[left++];
  75. } else {
  76. temp[j++] = list[right++];
  77. }
  78. }
  79. while (left <= mid) {
  80. temp[j++] = list[left++];
  81. }
  82. while (right <= last) {
  83. temp[j++] = list[right++];
  84. }
  85. for (j = 0; j < n; j++) {
  86. list[lowIndex + j] = temp[j];
  87. }
  88. }
  89. }

QuickSorter.java

  1. package com.jackfrued.util;
  2. import java.util.Comparator;
  3. /**
  4. * 快速排序
  5. * 快速排序是使用分治法（divide-and-conquer）依选定的枢轴
  6. * 将待排序序列划分成两个子序列，其中一个子序列的元素都小于枢轴，
  7. * 另一个子序列的元素都大于或等于枢轴，然后对子序列重复上面的方法，
  8. * 直到子序列中只有一个元素为止
  9. * @author Hao
  10. *
  11. */
  12. public classQuickSorter implements Sorter {
  13. @Override
  14. public <T extends Comparable<T>>voidsort(T[] list) {
  15. quickSort(list,0, list.length- 1);
  16. }
  17. @Override
  18. public <T> void sort(T[] list,Comparator<T> comp) {
  19. quickSort(list,0, list.length- 1, comp);
  20. }
  21. private <T extends Comparable<T>>voidquickSort(T[] list, int first, intlast) {
  22. if (last > first) {
  23. int pivotIndex =partition(list, first, last);
  24. quickSort(list,first, pivotIndex - 1);
  25. quickSort(list,pivotIndex, last);
  26. }
  27. }
  28. private <T> void quickSort(T[] list, int first, int last,Comparator<T> comp) {
  29. if (last > first) {
  30. int pivotIndex =partition(list, first, last, comp);
  31. quickSort(list,first, pivotIndex - 1, comp);
  32. quickSort(list,pivotIndex, last, comp);
  33. }
  34. }
  35. private <T extends Comparable<T>>intpartition(T[] list, int first, intlast) {
  36. Tpivot = list[first];
  37. int low = first + 1;
  38. int high = last;
  39. while (high > low) {
  40. while (low <= high&& list[low].compareTo(pivot) <= 0) {
  41. low++;
  42. }
  43. while (low <= high&& list[high].compareTo(pivot) >= 0) {
  44. high--;
  45. }
  46. if (high > low) {
  47. Ttemp = list[high];
  48. list[high]= list[low];
  49. list[low]= temp;
  50. }
  51. }
  52. while (high > first&& list[high].compareTo(pivot) >= 0) {
  53. high--;
  54. }
  55. if (pivot.compareTo(list[high])> 0) {
  56. list[first]= list[high];
  57. list[high]= pivot;
  58. return high;
  59. }
  60. else {
  61. return low;
  62. }
  63. }
  64. private <T> int partition(T[] list, int first, int last,Comparator<T> comp) {
  65. Tpivot = list[first];
  66. int low = first + 1;
  67. int high = last;
  68. while (high > low) {
  69. while (low <= high&& comp.compare(list[low], pivot) <= 0) {
  70. low++;
  71. }
  72. while (low <= high&& comp.compare(list[high], pivot) >= 0) {
  73. high--;
  74. }
  75. if (high > low) {
  76. Ttemp = list[high];
  77. list[high] = list[low];
  78. list[low]= temp;
  79. }
  80. }
  81. while (high > first&& comp.compare(list[high], pivot) >= 0) {
  82. high--;
  83. }
  84. if (comp.compare(pivot,list[high]) > 0) {
  85. list[first]= list[high];
  86. list[high]= pivot;
  87. return high;
  88. }
  89. else {
  90. return low;
  91. }
  92. }
  93. }

138、写一个二分查找（折半搜索）的算法。

答：折半搜索，也称二分查找算法、二分搜索，是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

  1. package com.jackfrued.util;
  2. import java.util.Comparator;
  3. public classMyUtil {
  4. public static <T extends Comparable<T>>int binarySearch(T[] x, T key) {
  5. return binarySearch(x,0, x.length- 1, key);
  6. }
  7. public static <T> int binarySearch(T[] x, T key, Comparator<T> comp) {
  8. int low = 0;
  9. int high = x.length - 1;
  10. while (low <= high) {
  11. int mid = (low + high) >>> 1;
  12. int cmp = comp.compare(x[mid], key);
  13. if (cmp < 0) {
  14. low= mid + 1;
  15. }
  16. else if (cmp > 0) {
  17. high= mid - 1;
  18. }
  19. else {
  20. return mid;
  21. }
  22. }
  23. return -1;
  24. }
  25. private static<T extends Comparable<T>>intbinarySearch(T[] x, int low, inthigh, T key) {
  26. if(low <= high) {
  27. int mid = low + ((high -low) >> 1);
  28. if(key.compareTo(x[mid])== 0) {
  29. return mid;
  30. }
  31. else if(key.compareTo(x[mid])< 0) {
  32. return binarySearch(x,low, mid - 1, key);
  33. }
  34. else {
  35. return binarySearch(x,mid + 1, high, key);
  36. }
  37. }
  38. return -1;
  39. }
  40. }

说明：两个版本一个用递归实现，一个用循环实现。需要注意的是计算中间位置时不应该使用(high+ low) / 2的方式，因为加法运算可能导致整数越界，这里应该使用一下三种方式之一：low+ (high – low) / 2或low + (high – low) >> 1或（low + high） >>> 1（注：>>>是逻辑右移，不带符号位的右移）

139、统计一篇英文文章中单词个数。

答：

  1. import java.io.FileReader;
  2. public class WordCounting {
  3. publicstatic void main(String[] args) {
  4. try(FileReader fr = new FileReader("a.txt")) {
  5. intcounter = 0;
  6. booleanstate = false;
  7. intcurrentChar;
  8. while((currentChar= fr.read()) != -1) {
  9. if(currentChar== ' ' || currentChar == '\n'
  10. ||currentChar == '\t' || currentChar == '\r') {
  11. state= false;
  12. }
  13. elseif(!state) {
  14. state= true;
  15. counter++;
  16. }
  17. }
  18. System.out.println(counter);
  19. }
  20. catch(Exceptione) {
  21. e.printStackTrace();
  22. }
  23. }
  24. }

补充：这个程序可能有很多种写法，这里选择的是Dennis M. Ritchie和Brian W. Kernighan老师在他们不朽的著作《The C Programming Language》中给出的代码，向两位老师致敬。下面的代码也是如此。

140、输入年月日，计算该日期是这一年的第几天。

答：

  1. import java.util.Scanner;
  2. public classDayCounting {
  3. public static void main(String[] args) {
  4. int[][] data = {
  5. {31,28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
  6. {31,29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}
  7. };
  8. Scannersc = newScanner(System.in);
  9. System.out.print("请输入年月日(1980 11 28): ");
  10. int year = sc.nextInt();
  11. int month = sc.nextInt();
  12. int date = sc.nextInt();
  13. int[] daysOfMonth =
  14. data[(year % 4 == 0 && year % 100 != 0 || year % 400 == 0)?1 : 0];
  15. int sum = 0;
  16. for(int i = 0; i < month -1; i++) {
  17. sum+= daysOfMonth[i];
  18. }
  19. sum+= date;
  20. System.out.println(sum);
  21. sc.close();
  22. }
  23. }

141、约瑟夫环：15个基督教徒和15个非教徒在海上遇险，必须将其中一半的人投入海中，其余的人才能幸免于难，于是30个人围成一圈，从某一个人开始从1报数，报到9的人就扔进大海，他后面的人继续从1开始报数，重复上面的规则，直到剩下15个人为止。结果由于上帝的保佑，15个基督教徒最后都幸免于难，问原来这些人是怎么排列的，哪些位置是基督教徒，哪些位置是非教徒。

答：

  1. public classJosephu {
  2. private static final int DEAD_NUM = 9;
  3. public static void main(String[] args) {
  4. boolean[] persons = new boolean[30];
  5. for(int i = 0; i < persons.length; i++) {
  6. persons[i]= true;
  7. }
  8. int counter = 0;
  9. int claimNumber = 0;
  10. int index = 0;
  11. while(counter < 15) {
  12. if(persons[index]) {
  13. claimNumber++;
  14. if(claimNumber == DEAD_NUM) {
  15. counter++;
  16. claimNumber= 0;
  17. persons[index]= false;
  18. }
  19. }
  20. index++;
  21. if(index >= persons.length) {
  22. index= 0;
  23. }
  24. }
  25. for(boolean p : persons) {
  26. if(p) {
  27. System.out.print("基");
  28. }
  29. else {
  30. System.out.print("非");
  31. }
  32. }
  33. }
  34. }

142、回文素数：所谓回文数就是顺着读和倒着读一样的数(例如：11，121，1991…)，回文素数就是既是回文数又是素数(只能被1和自身整除的数)的数。编程找出11～9999之间的回文素数。

答：

  1. public classPalindromicPrimeNumber {
  2. public static void main(String[] args) {
  3. for(int i = 11; i <= 9999;i++) {
  4. if(isPrime(i)&& isPalindromic(i)) {
  5. System.out.println(i);
  6. }
  7. }
  8. }
  9. public static boolean isPrime(int n) {
  10. for(int i = 2; i <= Math.sqrt(n);i++) {
  11. if(n % i == 0) {
  12. return false;
  13. }
  14. }
  15. return true;
  16. }
  17. public static boolean isPalindromic(int n) {
  18. int temp = n;
  19. int sum = 0;
  20. while(temp > 0) {
  21. sum= sum * 10 + temp % 10;
  22. temp/= 10;
  23. }
  24. return sum == n;
  25. }
  26. }

143、全排列：给出五个数字12345的所有排列。

答：

  1. public classFullPermutation {
  2. public static void perm(int[] list) {
  3. perm(list,0);
  4. }
  5. private static void perm(int[] list, int k) {
  6. if (k == list.length) {
  7. for (int i = 0; i < list.length; i++) {
  8. System.out.print(list[i]);
  9. }
  10. System.out.println();
  11. }else{
  12. for (int i = k; i < list.length; i++) {
  13. swap(list,k, i);
  14. perm(list,k + 1);
  15. swap(list,k, i);
  16. }
  17. }
  18. }
  19. private static void swap(int[] list, int pos1, int pos2) {
  20. int temp = list[pos1];
  21. list[pos1]= list[pos2];
  22. list[pos2]= temp;
  23. }
  24. public static void main(String[] args) {
  25. int[] x = {1, 2, 3, 4, 5};
  26. perm(x);
  27. }
  28. }

144、对于一个有N个整数元素的一维数组，找出它的子数组（数组中下标连续的元素组成的数组）之和的最大值。

答：下面给出几个例子（最大子数组用粗体表示）：

1) 数组：{ 1, -2, 3,5, -3, 2 }，结果是：8

2) 数组：{ 0, -2, 3, 5, -1, 2 }，结果是：9

3) 数组：{ -9, -2,-3, -5, -3 }，结果是：-2

可以使用动态规划的思想求解：

  1. public classMaxSum {
  2. private static int max(int x, int y) {
  3. return x > y? x: y;
  4. }
  5. public static int maxSum(int[] array) {
  6. int n = array.length;
  7. int[] start = new int[n];
  8. int[] all = new int[n];
  9. all[n- 1] = start[n - 1] = array[n - 1];
  10. for(int i = n - 2; i >= 0;i--) {
  11. start[i]= max(array[i], array[i] + start[i + 1]);
  12. all[i]= max(start[i], all[i + 1]);
  13. }
  14. return all[0];
  15. }
  16. public static void main(String[] args) {
  17. int[] x1 = { 1, -2, 3, 5,-3, 2 };
  18. int[] x2 = { 0, -2, 3, 5,-1, 2 };
  19. int[] x3 = { -9, -2, -3,-5, -3 };
  20. System.out.println(maxSum(x1));   // 8
  21. System.out.println(maxSum(x2));   // 9
  22. System.out.println(maxSum(x3));   //-2
  23. }
  24. }

145、用递归实现字符串倒转

答：

  1. public classStringReverse {
  2. public static String reverse(StringoriginStr) {
  3. if(originStr == null || originStr.length()== 1) {
  4. return originStr;
  5. }
  6. return reverse(originStr.substring(1))+ originStr.charAt(0);
  7. }
  8. public static void main(String[] args) {
  9. System.out.println(reverse("hello"));
  10. }
  11. }

146、输入一个正整数，将其分解为素数的乘积。

答：

  1. public classDecomposeInteger {
  2. private static List<Integer> list = newArrayList<Integer>();
  3. public static void main(String[] args) {
  4. System.out.print("请输入一个数: ");
  5. Scannersc = newScanner(System.in);
  6. int n = sc.nextInt();
  7. decomposeNumber(n);
  8. System.out.print(n + " = ");
  9. for(int i = 0; i < list.size() - 1; i++) {
  10. System.out.print(list.get(i) + " * ");
  11. }
  12. System.out.println(list.get(list.size() - 1));
  13. }
  14. public static void decomposeNumber(int n) {
  15. if(isPrime(n)) {
  16. list.add(n);
  17. list.add(1);
  18. }
  19. else {
  20. doIt(n,(int)Math.sqrt(n));
  21. }
  22. }
  23. public static void doIt(int n, int div) {
  24. if(isPrime(div)&& n % div == 0) {
  25. list.add(div);
  26. decomposeNumber(n/ div);
  27. }
  28. else {
  29. doIt(n,div - 1);
  30. }
  31. }
  32. public static boolean isPrime(int n) {
  33. for(int i = 2; i <= Math.sqrt(n);i++) {
  34. if(n % i == 0) {
  35. return false;
  36. }
  37. }
  38. return true;
  39. }
  40. }

147、一个有n级的台阶，一次可以走1级、2级或3级，问走完n级台阶有多少种走法。

答：可以通过递归求解。

  1. public classGoSteps {
  2. public static int countWays(int n) {
  3. if(n < 0) {
  4. return 0;
  5. }
  6. else if(n == 0) {
  7. return 1;
  8. }
  9. else {
  10. return countWays(n - 1) + countWays(n - 2) + countWays(n -3);
  11. }
  12. }
  13. publicstaticvoidmain(String[] args) {
  14. System.out.println(countWays(5));   // 13
  15. }
  16. }

148、写一个算法判断一个英文单词的所有字母是否全都不同（不区分大小写）。

答：

  1. public classAllNotTheSame {
  2. public static boolean judge(String str) {
  3. Stringtemp = str.toLowerCase();
  4. int[] letterCounter = new int[26];
  5. for(int i = 0; i <temp.length(); i++) {
  6. int index = temp.charAt(i)- 'a';
  7. letterCounter[index]++;
  8. if(letterCounter[index]> 1) {
  9. return false;
  10. }
  11. }
  12. return true;
  13. }
  14. public static void main(String[] args) {
  15. System.out.println(judge("hello"));
  16. System.out.print(judge("smile"));
  17. }
  18. }

149、有一个已经排好序的整数数组，其中存在重复元素，请将重复元素删除掉，例如，A= [1, 1, 2, 2, 3]，处理之后的数组应当为A= [1, 2, 3]。

答：

  1. import java.util.Arrays;
  2. public classRemoveDuplication {
  3. public static int[] removeDuplicates(int a[]) {
  4. if(a.length <= 1) {
  5. return a;
  6. }
  7. int index = 0;
  8. for(int i = 1; i < a.length; i++) {
  9. if(a[index] != a[i]) {
  10. a[++index] = a[i];
  11. }
  12. }
  13. int[] b = new int[index + 1];
  14. System.arraycopy(a, 0, b, 0, b.length);
  15. return b;
  16. }
  17. publicstaticvoidmain(String[] args) {
  18. int[] a = {1, 1, 2, 2, 3};
  19. a = removeDuplicates(a);
  20. System.out.println(Arrays.toString(a));
  21. }
  22. }

150、给一个数组，其中有一个重复元素占半数或半数以上，找出这个元素。

答：

    1. public classFindMost {
    2. public static <T> T find(T[] x){
    3. Ttemp = null;
    4. for(int i = 0, nTimes = 0; i< x.length;i++) {
    5. if(nTimes == 0) {
    6. temp= x[i];
    7. nTimes= 1;
    8. }
    9. else {
    10. if(x[i].equals(temp)) {
    11. nTimes++;
    12. }
    13. else {
    14. nTimes--;
    15. }
    16. }
    17. }
    18. return temp;
    19. }
    20. public static void main(String[] args) {
    21. String[]strs = {"hello","kiss","hello","hello","maybe"};
    22. System.out.println(find(strs));
    23. }
    24. }
上一篇：Linux top命令简解


下一篇：循序渐进的手动安装k8s笔记-3