前言：不管是遠端的視訊面試，還是現場的面試，都有可能會有手撕代碼的環節，這也是很多童鞋包括我(雖然還沒遇到過..)都很頭疼的東西，可能是因為 IDE 自動提示功能用慣了或是其他一些原因，總之讓我手寫代碼就是感覺很奇怪..但是我想的話，這應該側重考察的是一些細節或者是習慣方面的一些東西，是以還是防患于未然吧，把一些可能手撕的代碼給準備準備，分享分享，希望可以得到各位的指正，然後能有一些讨論，由于我字太醜就不上傳自己默寫的代碼了，但還是希望各位潦草寫一遍加深一下印象吧，以上；
Part 1.生産者-消費者問題
這絕對是屬于重點了，不管是考察對于該重要模型的了解還是考察代碼能力，這都是一道很好的考題，是以很有必要的，我們先來回顧一下什麼是生産者-消費者問題；
問題簡單回顧
生産者消費者問題（英語：Producer-consumer problem），也稱有限緩沖問題（英語：Bounded-buffer problem），是一個多線程同步問題的經典案例。該問題描述了共享固定大小緩沖區的兩個線程——即所謂的“生産者”和“消費者”——在實際運作時會發生的問題。生産者的主要作用是生成一定量的資料放到緩沖區中，然後重複此過程。與此同時，消費者也在緩沖區消耗這些資料。該問題的關鍵就是要保證生産者不會在緩沖區滿時加入資料，消費者也不會在緩沖區中空時消耗資料。(摘自維基百科：生産者消費者問題)
- 注意： 生産者-消費者模式中的記憶體緩存區的主要功能是資料在多線程間的共享，此外，通過該緩沖區，可以緩解生産者和消費者的性能差；
幾種實作方式
上面說到該問題的關鍵是：如何保證生産者不會在緩沖區滿時加入資料，消費者也不會在緩沖區空時消耗資料；解決思路可以簡單概括為：
- 生産者持續生産，直到緩沖區滿，滿時阻塞；緩沖區不滿後，繼續生産；
- 消費者持續消費，直到緩沖區空，空時阻塞；緩沖區不空後，繼續消費；
- 生産者和消費者都可以有多個；
那麼在 Java 語言中，能達到上述要求的，自然而然的就會有如下的幾種寫法，但是問題的核心都是能夠讓消費者和生産者在各自滿足條件需要阻塞時能夠起到正确的作用：
-
wait()
notify()
-
await()
signal()
-
BlockingQueue
-
PipedInputStream
PipedOutputStream
手寫代碼，我們着重掌握上面對應的第一種和第三種寫法就足夠了；
wait()/notify()方式實作
在手寫代碼之前，我們需要現在 IDE 上實作一遍，了解其中的過程并且找到一些重點/細節，我們先來代碼走一遍，然後我把我了解的重點給圈兒出來：
生産者代碼
public class Producer implements Runnable {
private volatile boolean isRunning = true;
private final Vector sharedQueue; // 記憶體緩沖區
private final int SIZE; // 緩沖區大小
private static AtomicInteger count = new AtomicInteger(); // 總數，原子操作
private static final int SLEEPTIME = 1000;
public Producer(Vector sharedQueue, int SIZE) {
this.sharedQueue = sharedQueue;
this.SIZE = SIZE;
}
@Override
public void run() {
int data;
Random r = new Random();
System.out.println("start producer id = " + Thread.currentThread().getId());
try {
while (isRunning) {
// 模拟延遲
Thread.sleep(r.nextInt(SLEEPTIME));
// 當隊列滿時阻塞等待
while (sharedQueue.size() == SIZE) {
synchronized (sharedQueue) {
System.out.println("Queue is full, producer " + Thread.currentThread().getId()
+ " is waiting, size：" + sharedQueue.size());
sharedQueue.wait();
}
}
// 隊列不滿時持續創造新元素
synchronized (sharedQueue) {
data = count.incrementAndGet(); // 構造任務資料
sharedQueue.add(data);
System.out.println("producer create data:" + data + ", size：" + sharedQueue.size());
sharedQueue.notifyAll();
}
}
} catch (InterruptedException e) {
e.printStackTrace();
Thread.currentThread().interrupted();
}
}
public void stop() {
isRunning = false;
}
}
有了上面的提到的解決思路，應該很容易實作，但是這裡主要提一下一些細節和重點：
- 創造資料：生産者-消費者解決的問題就是資料在多線程間的共享，是以我們首要關心的問題就應該是資料，我們這裡采用的是使用一個
AtomicInteger
incrementAndGet()
static
- 記憶體緩沖區：要保證在多線程環境下記憶體緩沖區的安全，是以我們考慮使用簡單的
Vector
final
SIZE
final
- 模拟延遲：這裡主要模拟的是一個網絡延遲，我們首先定義了一個
SLEEPTIME
static final
Random()
nextInt()
- 停止方法：首先需要知道在
Thread
stop()
isRunning
stop()
volatile
- 錯誤處理：當捕獲到錯誤時，我們應該使用
Thread
interrupted()
- 消息提示：我們主要是要在控制台輸出該生産者的資訊，包括目前隊列的狀态，大小，目前線程的生産者資訊等，注意的是資訊格式的統一(後面的消費者同樣的)；
消費者代碼
public class Consumer implements Runnable {
private final Vector sharedQueue; // 記憶體緩沖區
private final int SIZE; // 緩沖區大小
private static final int SLEEPTIME = 1000;
public Consumer(Vector sharedQueue, int SIZE) {
this.sharedQueue = sharedQueue;
this.SIZE = SIZE;
}
@Override
public void run() {
Random r = new Random();
System.out.println("start consumer id = " + Thread.currentThread().getId());
try {
while (true) {
// 模拟延遲
Thread.sleep(r.nextInt(SLEEPTIME));
// 當隊列空時阻塞等待
while (sharedQueue.isEmpty()) {
synchronized (sharedQueue) {
System.out.println("Queue is empty, consumer " + Thread.currentThread().getId()
+ " is waiting, size：" + sharedQueue.size());
sharedQueue.wait();
}
}
// 隊列不空時持續消費元素
synchronized (sharedQueue) {
System.out.println("consumer consume data：" + sharedQueue.remove(0) + ", size：" + sharedQueue.size());
sharedQueue.notifyAll();
}
}
} catch (InterruptedException e) {
e.printStackTrace();
Thread.currentThread().interrupt();
}
}
}
跟生産者相同的，你需要注意記憶體緩沖區/ 模拟延遲/ 錯誤處理/ 消息提示這些方面的細節問題，總體來說消費者就是持續不斷的消費，也比較容易實作；
主線程代碼
有了我們的消費者和生産者代碼，我們需要來驗證一下它們的正确性，照常理來說我們直接建立一些消費者和生産者的線程讓它們執行就可以了啊，但是為了“加分”考慮呢，我們還是使用線程池吧..也不是特别複雜：
public static void main(String args[]) throws InterruptedException {
// 1.建構記憶體緩沖區
Vector sharedQueue = new Vector();
int size = 4;
// 2.建立線程池和線程
ExecutorService service = Executors.newCachedThreadPool();
Producer prodThread1 = new Producer(sharedQueue, size);
Producer prodThread2 = new Producer(sharedQueue, size);
Producer prodThread3 = new Producer(sharedQueue, size);
Consumer consThread1 = new Consumer(sharedQueue, size);
Consumer consThread2 = new Consumer(sharedQueue, size);
Consumer consThread3 = new Consumer(sharedQueue, size);
service.execute(prodThread1);
service.execute(prodThread2);
service.execute(prodThread3);
service.execute(consThread1);
service.execute(consThread2);
service.execute(consThread3);
// 3.睡一會兒然後嘗試停止生産者
Thread.sleep(10 * 1000);
prodThread1.stop();
prodThread2.stop();
prodThread3.stop();
// 4.再睡一會兒關閉線程池
Thread.sleep(3000);
service.shutdown();
}
大家可以自行去看看運作的結果，是沒有問題的，不會出現多生産或者多消費之類的多線程問題，運作一段時間等生産者都停止之後，我們可以觀察到控制台三個消費者都在等待資料的情況：
Queue is empty, consumer 17 is waiting, size：0
Queue is empty, consumer 15 is waiting, size：0
Queue is empty, consumer 16 is waiting, size：0
BlockingQueue阻塞隊列方式實作
該方式對比起上面一種方式實作起來要簡單一些，因為不需要手動的去通知其他線程了，生産者直接往隊列中放資料直到隊列滿，消費者直接從隊列中擷取資料直到隊列空，BlockingQueue會自動幫我們完成阻塞這個動作，還是先來看看代碼
public class Producer implements Runnable {
private volatile boolean isRunning = true;
private BlockingQueue<Integer> queue; // 記憶體緩沖區
private static AtomicInteger count = new AtomicInteger(); // 總數，原子操作
private static final int SLEEPTIME = 1000;
public Producer(BlockingQueue<Integer> queue) {
this.queue = queue;
}
@Override
public void run() {
int data;
Random r = new Random();
System.out.println("start producer id = " + Thread.currentThread().getId());
try {
while (isRunning) {
// 模拟延遲
Thread.sleep(r.nextInt(SLEEPTIME));
// 往阻塞隊列中添加資料
data = count.incrementAndGet(); // 構造任務資料
System.out.println("producer " + Thread.currentThread().getId() + " create data：" + data
+ ", size：" + queue.size());
if (!queue.offer(data, 2, TimeUnit.SECONDS)) {
System.err.println("failed to put data：" + data);
}
}
} catch (InterruptedException e) {
e.printStackTrace();
Thread.currentThread().interrupted();
}
}
public void stop() {
isRunning = false;
}
}
跟上面一種方式沒有很大的差别，倒是代碼更加簡單通透，不過需要注意的是對阻塞隊列添加失敗的錯誤處理；
public class Consumer implements Runnable {
private BlockingQueue<Integer> queue; // 記憶體緩沖區
private static final int SLEEPTIME = 1000;
public Consumer(BlockingQueue<Integer> queue) {
this.queue = queue;
}
@Override
public void run() {
int data;
Random r = new Random();
System.out.println("start consumer id = " + Thread.currentThread().getId());
try {
while (true) {
// 模拟延遲
Thread.sleep(r.nextInt(SLEEPTIME));
// 從阻塞隊列中擷取資料
if (!queue.isEmpty()) {
data = queue.take();
System.out.println("consumer " + Thread.currentThread().getId() + " consume data：" + data
+ ", size：" + queue.size());
} else {
System.out.println("Queue is empty, consumer " + Thread.currentThread().getId()
+ " is waiting, size：" + queue.size());
}
}
} catch (InterruptedException e) {
e.printStackTrace();
Thread.currentThread().interrupt();
}
}
}
public static void main(String args[]) throws InterruptedException {
// 1.建構記憶體緩沖區
BlockingQueue<Integer> queue = new LinkedBlockingDeque<>();
// 2.建立線程池和線程
ExecutorService service = Executors.newCachedThreadPool();
Producer prodThread1 = new Producer(queue);
Producer prodThread2 = new Producer(queue);
Producer prodThread3 = new Producer(queue);
Consumer consThread1 = new Consumer(queue);
Consumer consThread2 = new Consumer(queue);
Consumer consThread3 = new Consumer(queue);
service.execute(prodThread1);
service.execute(prodThread2);
service.execute(prodThread3);
service.execute(consThread1);
service.execute(consThread2);
service.execute(consThread3);
// 3.睡一會兒然後嘗試停止生産者
Thread.sleep(10 * 1000);
prodThread1.stop();
prodThread2.stop();
prodThread3.stop();
// 4.再睡一會兒關閉線程池
Thread.sleep(3000);
service.shutdown();
}
因為隊列中添加和删除的操作比較頻繁，是以這裡使用
LinkedBlockingQueue
來作為阻塞隊列，是以這裡除了記憶體緩沖區有所不同以外，其他的都差不多...當然你也可以指定一個隊列的大小；
總結以及改進
生産者-消費者模式很好地對生産者線程和消費者線程進行解耦，優化了系統整體的結構，同時由于緩沖區的作用，允許生産者線程和消費者線程存在執行上的性能差異，從一定程度上緩解了性能瓶頸對系統性能的影響；上面兩種寫法都是非常正常的寫法，隻能說能起碼能在及格的基礎上加個那麼點兒分數，如果想要得高分可以去搜尋搜搜 Disruptor 來實作一個無鎖的生産者-消費者模型....這裡就不提及了..
改進：上面的線程輸出可能會有點兒不友好（不直覺），因為我們這裡是直接使用的線程的 ID 來作為輸出，我們也可以給線程弄一個名字來作為輸出，以上；
Part 2.排序算法
排序算法當然也算是重點考察的對象之一了，畢竟基礎且偏算法，當然我們有必要去了解常見的排序算法以及它們采取了怎樣的思想又是如何實作的還有複雜度的問題，但是這裡的話，主要就提及兩種考的比較常見的排序算法：冒泡和快排，以及分别對它們進行的一些優化；
冒泡排序
冒泡應該是比較基礎的一種算法，我們以從小到大排序為例，它的基礎思想是：從第一個數開始直到數組倒數第二個數，每一輪都去比較數組中剩下的數，如果後面的資料更小則兩數交換，這樣一輪一輪的比較交換下來，最大的那個數也就“沉到”了數組的最後，最小的“冒”到了數組的最前面，這樣就完成了排序工作；
基礎算法代碼（未優化）
很簡單，直接上代碼：
/**
* 冒泡排序
*
* @param nums 待排序的數組
*/
public void bubbleSort(int[] nums) {
// 正确性判斷
if (null == nums || nums.length <= 1) {
return;
}
// 從小到大排序
for (int i = 0; i < nums.length - 1; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] > nums[j]) {
nums[i] = nums[i] + nums[j];
nums[j] = nums[i] - nums[j];
nums[i] = nums[i] - nums[j];
}
}
}
}
這裡需要注意：加上正确性判斷；（讨論：其實我看大多數地方都是沒有這個的，不知道有沒有加上的必要...求讨論）
另外光寫完實作冒泡排序的算法是不算完的，還要養成良好的習慣去寫測試單元用例，而且盡可能要考慮到多的點，例如這裡的負數、多個相同的數之類的特殊情況，我就大概寫一個吧，也歡迎指正：
@Test
public void bubbleSortTester() {
// 測試用例1：驗證負數是否滿足要求
int[] nums = {1, 4, 2, -2, 5, 11, -7, 0};
bubbleSort(nums);
// 輸出測試結果
for (int i = 0; i < nums.length; i++) {
System.out.print(nums[i] + ", ");
}
System.out.println();
// 測試用例2：驗證多個相同的數是否滿足要求
nums = new int[]{1, 1, 5, 7, 7, 3, 1};
bubbleSort(nums);
// 輸出測試結果
for (int i = 0; i < nums.length; i++) {
System.out.print(nums[i] + ", ");
}
}
冒泡排序優化
想象一個這樣的場景：如果該數組基本有序，或者在數組的後半段基本有序，上面的算法就會浪費許多的時間開銷，是以我們不再使用雙重嵌套去比較每兩個元素的值，而隻是不斷比較數組每前後兩個數值，讓大的那個數不斷“冒”到數組的最後，然後縮小尾邊界的範圍，并且增加一個标志位，表示這一趟是否發生了交換，如果沒有那麼證明該數組已經有序則完成了排序了：
/**
* 改進的冒泡排序
*
* @param nums 待排序的數組
*/
public void bubbleSort2(int[] nums) {
// 正确性判斷
if (null == nums || nums.length <= 1) {
return;
}
// 使用一個數來記錄尾邊界
int length = nums.length;
boolean flag = true;// 發生了交換就為true, 沒發生就為false，第一次判斷時必須标志位true。
while (flag) {
flag = false;// 每次開始排序前，都設定flag為未排序過
for (int i = 1; i < length; i++) {
if (nums[i - 1] > nums[i]) {// 前面的數字大于後面的數字就交換
int temp;
temp = nums[i - 1];
nums[i - 1] = nums[i];
nums[i] = temp;
// 表示交換過資料;
flag = true;
}
}
length--; // 減小一次排序的尾邊界
}
}
同樣的記得寫單元測試函數；
冒泡排序進一步優化
順着這個思路，我們進一步想象一個場景：現在有一個包含 1000 個數的數組，僅有前面 100 個數無序，後面的 900 個數都比前面的 100 個數更大并且已經排好序，那麼上面優化的方法又會造成一定的時間浪費，是以我們進一步增加一個變量記錄最後發生交換的元素的位置，也就是排序的尾邊界了：
/**
* 冒泡算法最優解
*
* @param nums 待排序的數組
*/
public static void bubbleSort3(int[] nums) {
int j, k;
int flag = nums.length;// flag來記錄最後交換的位置，也就是排序的尾邊界
while (flag > 0) {// 排序未結束标志
k = flag;// k 來記錄周遊的尾邊界
flag = 0;
for (j = 1; j < k; j++) {
if (nums[j - 1] > nums[j]) {// 前面的數字大于後面的數字就交換
// 交換a[j-1]和a[j]
int temp;
temp = nums[j - 1];
nums[j - 1] = nums[j];
nums[j] = temp;
// 表示交換過資料;
flag = j;// 記錄最新的尾邊界.
}
}
}
}
這應該是最優的冒泡排序了，同時也别忘記了最後要寫測試單元用例代碼；
快速排序
快排也是一種很經典的算法，它使用了一種分治的思想，基本思想是：通過一趟排序将待排序的數組分成兩個部分，其中一部分記錄的是比關鍵字更小的，另一部分是比關鍵字更大的，然後再分别對着兩部分繼續進行排序，直到整個序列有序；
基礎實作
非常經典的代碼，直接上吧：
public static void quickSort(int[] arr) {
qsort(arr, 0, arr.length - 1);
}
private static void qsort(int[] arr, int low, int high) {
if (low < high) {
int pivot = partition(arr, low, high); // 将數組分為兩部分
qsort(arr, low, pivot - 1); // 遞歸排序左子數組
qsort(arr, pivot + 1, high); // 遞歸排序右子數組
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[low]; // 樞軸記錄
while (low < high) {
while (low < high && arr[high] >= pivot) --high;
arr[low] = arr[high]; // 交換比樞軸小的記錄到左端
while (low < high && arr[low] <= pivot) ++low;
arr[high] = arr[low]; // 交換比樞軸小的記錄到右端
}
// 掃描完成，樞軸到位
arr[low] = pivot;
// 傳回的是樞軸的位置
return low;
}
當然，在手撕的時候需要注意函數上的 Java Doc 格式的注釋，這裡省略掉是為了節省篇幅，另外别忘了測試單元用例代碼；
上面的代碼也很容易了解，其實就是一個“填坑”的過程，第一個“坑”挖在每次排序的第一個位置
arr[low]
，從序列後面往前找第一個比
pivot
小的數來把這個“坑”填上，這時候的“坑”就變成了目前的
arr[high]
，然後再從序列前面往後用第一個比
pivot
大的數把剛才的“坑”填上，如此往複，始終有一個“坑”需要我們填上，直到最後一個“坑”出現，這個“坑”使用一開始的
pivot
填上就可以了，而這個“坑”的位置也就是
pivot
該填上的正确位置，我們再把這個位置傳回，就可以把目前序列分成兩個部分再依次這樣操作最終就達到排序的目的了，不得不說這樣的思想挺神奇的；
算法優化
上面這個快速排序算法可以說是最基本的快速排序，因為它并沒有考慮任何輸入資料。但是，我們很容易發現這個算法的缺陷：這就是在我們輸入資料基本有序甚至完全有序的時候，這算法退化為冒泡排序，不再是O(n㏒n)，而是O(n^2)了。
究其根源，在于我們的代碼實作中，每次隻從數組第一個開始取。如果我們采用“三者取中”，即 arr[low], arr[high], arr[(low+high)/2] 三者的中值作為樞軸記錄，則可以大大提高快速排序在最壞情況下的性能。但是，我們仍然無法将它在數組有序情形下的性能提高到O(n)。還有一些方法可以不同程度地提高快速排序在最壞情況下的時間性能。
此外，快速排序需要一個遞歸棧，通常情況下這個棧不會很深，為log(n)級别。但是，如果每次劃分的兩個數組長度嚴重失衡，則為最壞情況，棧的深度将增加到O(n)。此時，由棧空間帶來的空間複雜度不可忽略。如果加上額外變量的開銷，這裡甚至可能達到恐怖的O(n^2)空間複雜度。是以，快速排序的最差空間複雜度不是一個定值，甚至可能不在一個級别。
為了解決這個問題，我們可以在每次劃分後比較兩端的長度，并先對短的序列進行排序（目的是先結束這些棧以釋放空間），可以将最大深度降回到O(㏒n)級别。
關于優化的話，了解一個大概的思路就可以了，那在這裡稍微總結一下：
- ①三數取中作為樞軸記錄；
- ②當待排序序列的長度分割到一定大小之後，使用插入排序；
- ③在一次分割結束後，可以把與
pivot
pivot
- ④優化遞歸操作；
參考文章：http://blog.51cto.com/flyingcat2013/1281614
想要了解的更多的童鞋可以戳這裡：https://blog.csdn.net/insistGoGo/article/details/7785038
Part 3.二叉樹相關算法
二叉樹也是一個容易提及的概念和寫算法的問題，特别是它的幾種遞歸周遊和非遞歸周遊，都是基礎且常考的點，那在這裡就稍微整理整理吧...
二叉樹的幾種遞歸周遊
前序、中序、後序周遊都是非常基礎且容易的周遊方法，重點還是在後面的中序和後續的非遞歸周遊上，當然還有層序周遊，是以這裡不多說，直接給代碼；
前序周遊遞歸實作
public void preOrderTraverse1(TreeNode root) {
if (root != null) {
System.out.print(root.val + " ");
preOrderTraverse1(root.left);
preOrderTraverse1(root.right);
}
}
中序周遊遞歸實作
public void inOrderTraverse1(TreeNode root) {
if (root != null) {
preOrderTraverse1(root.left);
System.out.print(root.val + " ");
preOrderTraverse1(root.right);
}
}
後序周遊遞歸實作
public void postOrderTraverse1(TreeNode root) {
if (root != null) {
preOrderTraverse1(root.left);
preOrderTraverse1(root.right);
System.out.print(root.val + " ");
}
}
前面三種周遊，也就是輸出結點資料的位置不同而已，是以很容易，但是如果手寫，建議問清楚面試官要求，是在周遊時直接輸出還是需要函數傳回一個List集合，然後注意寫測試用例代碼！
二叉樹的幾種非遞歸周遊
★★層序周遊★★
層序周遊我們隻需要增加使用一個隊列即可，看代碼很容易了解：
public void levelTraverse(TreeNode root) {
if (root == null) {
return;
}
LinkedList<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
System.out.print(node.val + " ");
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
前序周遊非遞歸實作
public void preOrderTraverse2(TreeNode root) {
if (root == null) {
return;
}
LinkedList<TreeNode> stack = new LinkedList<>();
TreeNode pNode = root;
while (pNode != null || !stack.isEmpty()) {
if (pNode != null) {
System.out.print(pNode.val + " ");
stack.push(pNode);
pNode = pNode.left;
} else { //pNode == null && !stack.isEmpty()
TreeNode node = stack.pop();
pNode = node.right;
}
}
}
★★中序周遊非遞歸實作★★
/**
* 非遞歸中序周遊二叉樹
*
* @param root 二叉樹根節點
* @return 中序周遊結果集
*/
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
ArrayDeque<TreeNode> stack = new ArrayDeque<>();
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.addFirst(root);
root = root.left;
}
root = stack.removeFirst();
list.add(root.val);
root = root.right;
}
return list;
}
★★後續周遊非遞歸實作★★
/**
* 二叉樹的後序周遊
*
* @param root 二叉樹根節點
* @return 後序周遊結果集
*/
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode pre = null;
while (!stack.isEmpty() || root != null) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.peek();
// i ：判斷如果右子樹不為空且不為
if (root.right != null && root.right != pre) {
root = root.right;
} else {
root = stack.pop();
list.add(root.val);
pre = root;
root = null;
}
}
return list;
}
如果比較難以了解的話，可以自己嘗試着跟跟 Debug 然後看看過程；
二叉樹相關其他算法題
另外的話還有一些比較常見的關于樹的算法，在文章的末尾，這裡就不再贅述了：
連結：https://www.jianshu.com/p/4ef1f50d45b5
Part 4.其他重要算法
除了上面 3 Part 比較重要的點之外，還有一些其他的算法也是經常考到的，下面我們來說；
1.反轉連結清單
這是一道很經典的題，不僅考你對連結清單的了解，而且還有一些細節（例如正确性判斷/ 測試用例）需要你從代碼層面去展現，下面我們給出兩段代碼，讀者可以自行去比較，我隻是提供一個思路；
思路一：使用一個 Node 不斷連結
這是最經典的算法，也是需要我們牢牢掌握的方法，最重要的還是了解
while()
循環中的過程：
public ListNode reverseList(ListNode head) {
// 正确性判斷
if (null == head || null == head.next) {
return head;
}
ListNode pre = null;
while (null != head) {
ListNode temp = head;
head = head.next;
temp.next = pre;
pre = temp;
}
return pre;
}
思路二：反轉元素值然後重新賦給 Node
這是一個很簡單的思路，比上個思路要多周遊一遍連結清單，但是好處是簡單，思路清晰，實作起來容易，emm，像這一類問題我覺得另一個比較重要的就是舉一反三的能力吧，在這裡我隻提供兩個思路，其實還有很多種實作方法，當然也别忘了細節的東西~
public ListNode reverseList(ListNode head) {
// 1.正确性判斷
if (null == head || null == head.next) {
return head;
}
// 2.周遊連結清單head并将結果儲存在List集合中
List<ListNode> list = new LinkedList();
ListNode tempNode = head;
while (null != tempNode) {
list.insert(tempNode.val);
tempNode = tempNode.next;
} // end while：周遊完了連結清單并将結果儲存在了List集合中
// 3.反轉集合，并将值依次複制給連結清單
Collections.reverse(list);
tempNode = head;
while (null != tempNode) {
tempNode.val = list.remove(0);
tempNode = tempNode.next;
}
return head;
}
2.合并兩個有序連結清單
問題描述：将兩個有序連結清單合并為一個新的有序連結清單并傳回。新連結清單是通過拼接給定的兩個連結清單的所有節點組成的；
同樣的經典算法，需要掌握：
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
ListNode head = null;
if (l1.val < l2.val) {
head = l1;
head.next = mergeTwoLists(l1.next, l2);
} else {
head = l2;
head.next = mergeTwoLists(l1, l2.next);
}
return head;
}
這道題也是 LeetCode 上的一道題，我當時的做法是下面這樣的，雖然看起來代碼量多了不少而且看起來蠢蠢的..但是經過 LeetCode 測試，甚至比上面的實作要快上那麼 2ms，特别提醒：下面的代碼隻是用作一個思路的參考，着重掌握上面的代碼 ：
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// 定義一個虛拟頭結點友善周遊
ListNode dummyHead = new ListNode(-1);
dummyHead.next = l1;
ListNode pre = dummyHead;
// 周遊l1連結清單
int len1 = 0;
while (null != pre.next) {
len1++;
pre = pre.next;
}
int[] nums1 = new int[len1];
// 儲存l1連結清單的資料
pre = dummyHead;
for (int i = 0; i < len1; i++) {
nums1[i] = pre.next.val;
pre = pre.next;
}
// 周遊l2連結清單
int len2 = 0;
dummyHead.next = l2;
pre = dummyHead;
while (null != pre.next) {
len2++;
pre = pre.next;
}
int[] nums2 = new int[len2];
// 儲存l2連結清單的資料
pre = dummyHead;
for (int i = 0; i < len2; i++) {
nums2[i] = pre.next.val;
pre = pre.next;
}
int[] nums = new int[len1 + len2];
// 将兩個連結清單的資料整合并排序
System.arraycopy(nums1, 0, nums, 0, len1);
System.arraycopy(nums2, 0, nums, len1, len2);
Arrays.sort(nums);
// 拼接一個連結清單
ListNode dummy = new ListNode(-1);
pre = dummy;
for (int i = 0; i < nums.length; i++) {
ListNode node = new ListNode(nums[i]);
pre.next = node;
pre = pre.next;
}
return dummy.next;
}
3.兩個連結清單的第一個公共結點
題目描述：找出兩個連結清單的第一個公共結點；
/**
* 求兩個連結清單中第一個公共結點
*
* @param pHead1 連結清單1頭結點
* @param pHead2 連結清單2頭結點
* @return 連結清單第一個公共結點
*/
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
// 1.正确性判斷
if (null == pHead1 || null == pHead2) {
return null;
}
// 2.周遊連結清單1把所有結點儲存在清單中中
Vector<ListNode> nodeList1 = new Vector<>();
while (null != pHead1) {
nodeList1.add(pHead1);
pHead1 = pHead1.next;
// 判斷是否成環，成環則退出循環
if (nodeList1.contains(pHead1)) {
break;
}
} // end while：連結清單1中的所有結點都存入了nodeList1中
// 3.周遊連結清單2比較清單中的資料
Vector<ListNode> nodeList2 = new Vector<>();
while (null != pHead2) {
// 先判斷nodeList1中是否存在相同結點，存在則傳回
if (nodeList1.contains(pHead2)) {
return pHead2;
}
// 如果不存在則繼續周遊，并判斷是否成環
nodeList2.add(pHead2);
pHead2 = pHead2.next;
if (nodeList2.contains(pHead2)) {
break;
}
} // end while：周遊完了連結清單2并将所有結點儲存在了nodeList2中
// 如果周遊完連結清單2則傳回null
return null;
}
需要注意的細節是：①正确性判斷；②判斷連結清單是否自己成環；③注釋；④注意要自己寫測試用例啊...
另外還有一些類似的題目像是：①連結清單入環結點；②連結清單倒數第k個結點；之類的都是需要掌握的...
4.二分查找算法
二分查找也是一類比較常考的題目，其實代碼也比較容易了解，直接上吧，再再再提醒一下：注意正确性判斷還有測試用例...
普通實作
/**
* 二分查找普通實作。
*
* @param srcArray 有序數組
* @param key 查找元素
* @return 不存在傳回-1
*/
public static int binSearch(int srcArray[], int key) {
int mid;
int start = 0;
int end = srcArray.length - 1;
while (start <= end) {
mid = (end - start) / 2 + start;
if (key < srcArray[mid]) {
end = mid - 1;
} else if (key > srcArray[mid]) {
start = mid + 1;
} else {
return mid;
}
}
return -1;
}
遞歸實作
/**
* 二分查找遞歸實作。
*
* @param srcArray 有序數組
* @param start 數組低位址下标
* @param end 數組高位址下标
* @param key 查找元素
* @return 查找元素不存在傳回-1
*/
public static int binSearch(int srcArray[], int start, int end, int key) {
int mid = (end - start) / 2 + start;
if (srcArray[mid] == key) {
return mid;
}
if (start >= end) {
return -1;
} else if (key > srcArray[mid]) {
return binSearch(srcArray, mid + 1, end, key);
} else if (key < srcArray[mid]) {
return binSearch(srcArray, start, mid - 1, key);
}
return -1;
}
5.斐波那契數列
這也是一道很經典的題，通常是要要求 N 值的範圍的，正常寫法應該很簡單，是以需要掌握的是優化之後的算法：
public int Fibonacci(int n) {
// 正确性判斷
if (0 == n || 1 == n) {
return n;
}
int nums1 = 0, nums2 = 1;
int res = 0;
for (int i = 2; i <= n; i++) {
res = nums1 + nums2;
nums1 = nums2;
nums2 = res;
}
return res;
}
還是注意正确性判斷然後寫測試用例...
手撕代碼總結
如果用手寫代碼的話，确實是個挺麻煩的事兒，首先需要對代碼有相當的熟悉程度，然後其次的話考察的都是一些細節的東西，例如：
- 編碼規範：包括一些命名的規範/ 注釋的規範等等；
- 縮進：這個我自己倒是挺在意的..關于這個可以去參考參考阿裡出的那個規範手冊；
- 注釋：如果命名規範做得好的話其實是可以達到代碼即注釋的，但是仍然有一些需要标注的地方例如函數頭之類的，最好還是做好注釋；
- 代碼的完整性：我覺得這個包括對于錯誤的處理/ 正确性判斷這樣一類的東西；
- 測試用例：每個函數都需要一定的測試來保證其正确性，是以這個還是挺有必要的，特别是一些邊界情況，null 值判斷之類的；
- 想好再下筆：這一點其實也蠻重要的，不管是在紙上還是在我們平時的程式設計中，思路永遠都是更重要的；
說來說去還是關于代碼的事，我覺得還是理清思路最重要，是以我們需要在一遍一遍熟悉代碼的過程中，熟知這些代碼的思路，隻有搞清楚這些代碼背後的原理了，我們才能正确且快速的寫出我們心中想要的代碼，而不是簡單的去背誦，這樣是沒有很大效果的，以上...
歡迎轉載，轉載請注明出處！
簡書ID：@我沒有三顆心髒
github：wmyskxz
歡迎關注公衆微信号：wmyskxz_javaweb
分享自己的Java Web學習之路以及各種Java學習資料
想要交流的朋友也可以加qq群：3382693
![2019——JAVA面試題大全（一）基礎篇一、Java 基礎[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)