Java面試題集（136-150）

摘要：這一部分主要是資料結構和算法相關的面試題目，雖然隻有15道題目，但是包含的資訊量還是很大的，很多題目背後的解題思路和算法是非常值得玩味的。

136、給出下面的二叉樹先序、中序、後序周遊的序列？

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

補充：二叉樹也稱為二分樹，它是樹形結構的一種，其特點是每個結點至多有二棵子樹，并且二叉樹的子樹有左右之分，其次序不能任意颠倒。二叉樹的周遊序列按照通路根節點的順序分為先序（先通路根節點，接下來先序通路左子樹，再先序通路右子樹）、中序（先中序通路左子樹，然後通路根節點，最後中序通路右子樹）和後序（先後序通路左子樹，再後序通路右子樹，最後通路根節點）。如果知道一棵二叉樹的先序和中序序列或者中序和後序序列，那麼也可以還原出該二叉樹。

例如，已知二叉樹的先序序列為：xefdzmhqsk，中序序列為：fezdmxqhks，那麼還原出該二叉樹應該如下圖所示：

137、你知道的排序算法都哪些？用Java寫一個排序系統。

答：穩定的排序算法有：插入排序、選擇排序、冒泡排序、雞尾酒排序、歸并排序、二叉樹排序、基數排序等；不穩定排序算法包括：希爾排序、堆排序、快速排序等。

下面是關于排序算法的一個清單：

下面按照政策模式給出一個排序系統，實作了冒泡、歸并和快速排序。

Sorter.java

[java] 

​​view plain​​​

 ​​​copy​​

1. package com.jackfrued.util;
2. import java.util.Comparator;
3. /**
4. * 排序器接口(政策模式: 将算法封裝到具有共同接口的獨立的類中使得它們可以互相替換)
5. * @author駱昊
6. *
7. */
8. public interface Sorter {
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

[java] 

​​view plain​​​

 ​​​copy​​

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

MergeSorter.java

[java] 

​​view plain​​​

 ​​​copy​​

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 class MergeSorter implements Sorter {
13. @Override
14. public <T extends Comparable<T>> void sort(T[] list) {
15. new Comparable[list.length];
16. 0, list.length- 1);
17. }
18. private <T extends Comparable<T>> void mSort(T[] list, T[] temp, int low, int high) {
19. if(low == high) {
20. return ;
21. }
22. else {
23. int mid = low + ((high -low) >> 1);
24. mSort(list,temp, low, mid);
25. 1, high);
26. 1, high);
27. }
28. }
29. private <T extends Comparable<T>> void merge(T[] list, T[] temp, int left, int right, int last) {
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. new Comparable[list.length];
54. 0, list.length- 1, comp);
55. }
56. private <T> void mSort(T[] list, T[] temp, int low, int high, 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. 1, high, comp);
64. 1, high, comp);
65. }
66. }
67. private <T> void merge(T[] list, T[]temp, int left, int right, int last, 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

[java] 

​​view plain​​​

 ​​​copy​​

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 class QuickSorter implements Sorter {
13. @Override
14. public <T extends Comparable<T>> void sort(T[] list) {
15. 0, list.length- 1);
16. }
17. @Override
18. public <T> void sort(T[] list, Comparator<T> comp) {
19. 0, list.length- 1, comp);
20. }
21. private <T extends Comparable<T>> void quickSort(T[] list, int first, int last) {
22. if (last > first) {
23. int pivotIndex = partition(list, first, last);
24. 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. 1, comp);
32. quickSort(list, pivotIndex, last, comp);
33. }
34. }
35. private <T extends Comparable<T>> int partition(T[] list, int first, int last) {
36. T pivot = 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. T temp = 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. T pivot = 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. T temp = 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、寫一個二分查找（折半搜尋）的算法。

答：折半搜尋，也稱二分查找算法、二分搜尋，是一種在有序數組中查找某一特定元素的​​搜尋算法​​。搜素過程從數組的中間元素開始，如果中間元素正好是要查找的元素，則搜素過程結束；如果某一特定元素大于或者小于中間元素，則在數組大于或小于中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。如果在某一步驟數組為空，則代表找不到。這種搜尋算法每一次比較都使搜尋範圍縮小一半。

[java] 

​​view plain​​​

 ​​​copy​​

1. package com.jackfrued.util;
2. import java.util.Comparator;
3. public class MyUtil {
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. 1;
15. }
16. else if (cmp > 0) {
17. 1;
18. }
19. else {
20. return mid;
21. }
22. }
23. return -1;
24. }
25. private static <T extends Comparable<T>> int binarySearch(T[] x, int low, int high, 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,l ow, 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、統計一篇英文文章中單詞個數。

答：

[java] 

​​view plain​​​

 ​​​copy​​

1. import java.io.FileReader;
2. public class WordCounting {
3. public static void main(String[] args) {
4. try(FileReader fr = new FileReader("a.txt")) {
5. int counter = 0;
6. boolean state = false;
7. int currentChar;
8. while((currentChar= fr.read()) != -1) {
9. if(currentChar== ' ' || currentChar == '\n'
10. '\t' || currentChar == '\r') {
11. false;
12. }
13. else if(!state) {
14. 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、輸入年月日，計算該日期是這一年的第幾天。

答：

[java] 

​​view plain​​​

 ​​​copy​​

1. import java.util.Scanner;
2. public class DayCounting {
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. Scanner sc = newScanner(System.in);
9. "請輸入年月日(1980 11 28): ");
10. int year = sc.nextInt();
11. int month = sc.nextInt();
12. int date = sc.nextInt();
13. int[] daysOfMonth = data[(year % 4 == 0 && year % 100 != 0 || year % 400 == 0)?1 : 0];
14. int sum = 0;
15. for(int i = 0; i < month -1; i++) {
16. sum += daysOfMonth[i];
17. }
18. sum += date;
19. System.out.println(sum);
20. sc.close();
21. }
22. }

141、約瑟夫環：15個基督教徒和15個非教徒在海上遇險，必須将其中一半的人投入海中，其餘的人才能幸免于難，于是30個人圍成一圈，從某一個人開始從1報數，報到9的人就扔進大海，他後面的人繼續從1開始報數，重複上面的規則，直到剩下15個人為止。結果由于上帝的保佑，15個基督教徒最後都幸免于難，問原來這些人是怎麼排列的，哪些位置是基督教徒，哪些位置是非教徒。

答：

[java] 

​​view plain​​​

 ​​​copy​​

1. public class Josephu {
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. 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. 0;
17. false;
18. }
19. }
20. index++;
21. if(index >= persons.length) {
22. 0;
23. }
24. }
25. for(boolean p : persons) {
26. if(p) {
27. "基");
28. }
29. else {
30. "非");
31. }
32. }
33. }
34. }

142、回文素數：所謂回文數就是順着讀和倒着讀一樣的數(例如：11，121，1991…)，回文素數就是既是回文數又是素數(隻能被1和自身整除的數)的數。程式設計找出11～9999之間的回文素數。

答：

[java] 

​​view plain​​​

 ​​​copy​​

1. public class PalindromicPrimeNumber {
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. 10 + temp % 10;
22. 10;
23. }
24. return sum == n;
25. }
26. }

143、全排列：給出五個數字12345的所有排列。

答：

[java] 

​​view plain​​​

 ​​​copy​​

1. public class FullPermutation {
2. public static void perm(int[] list) {
3. 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. 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

可以使用動态規劃的思想求解：

[java] 

​​view plain​​​

 ​​​copy​​

1. public class MaxSum {
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. 1] = start[n - 1] = array[n - 1];
10. for(int i = n - 2; i >= 0;i--) {
11. 1]);
12. 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. // 8
21. // 9
22. //-2
23. }
24. }

145、用遞歸實作字元串倒轉

答：

[java] 

​​view plain​​​

 ​​​copy​​

1. public class StringReverse {
2. public static String reverse(String originStr) {
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. "hello"));
10. }
11. }

146、輸入一個正整數，将其分解為素數的乘積。

答：

[java] 

​​view plain​​​

 ​​​copy​​

1. public class DecomposeInteger {
2. private static List<Integer> list = newArrayList<Integer>();
3. public static void main(String[] args) {
4. "請輸入一個數: ");
5. Scanner sc = newScanner(System.in);
6. int n = sc.nextInt();
7. decomposeNumber(n);
8. " = ");
9. for(int i = 0; i < list.size() - 1; i++) {
10. " * ");
11. }
12. 1));
13. }
14. public static void decomposeNumber(int n) {
15. if(isPrime(n)) {
16. list.add(n);
17. 1);
18. }
19. else {
20. 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. 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級台階有多少種走法。

答：可以通過遞歸求解。

[java] 

​​view plain​​​

 ​​​copy​​

1. public class GoSteps {
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. public static void main(String[] args) {
14. 5));   // 13
15. }
16. }

148、寫一個算法判斷一個英文單詞的所有字母是否全都不同（不區分大小寫）。

答：

[java] 

​​view plain​​​

 ​​​copy​​

1. public class AllNotTheSame {
2. public static boolean judge(String str) {
3. String temp = 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. "hello"));
16. "smile"));
17. }
18. }

149、有一個已經排好序的整數數組，其中存在重複元素，請将重複元素删除掉，例如，A= [1, 1, 2, 2, 3]，處理之後的數組應當為A= [1, 2, 3]。

答：

[java] 

​​view plain​​​

 ​​​copy​​

1. import java.util.Arrays;
2. public class RemoveDuplication {
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. 0, b, 0, b.length);
15. return b;
16. }
17. public static void main(String[] args) {
18. int[] a = {1, 1, 2, 2, 3};
19. a = removeDuplicates(a);
20. System.out.println(Arrays.toString(a));
21. }
22. }

150、給一個數組，其中有一個重複元素占半數以上，找出這個元素。

答：

[java] 

​​view plain​​​

 ​​​copy​​

1. public class FindMost {
2. public static <T> T find(T[] x){
3. null;
4. for(int i = 0, nTimes = 0; i< x.length;i++) {
5. if(nTimes == 0) {
6. temp= x[i];
7. 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. "hello","kiss","hello","hello","maybe"};
22. System.out.println(find(strs));
23. }
24. }