非計算機專業如何靠自學殺進 BAT？技术頭條網

非計算機專業如何靠自學殺進 BAT？

2018-09-04 17:57:17 CSDN

作者 | channingbreeze

小史是一個應屆生，雖然學的是電子專業，但是自己業餘時間看了很多互聯網與編程方面的書，一心想進BAT。

今天他又去BAT中的一家面試了。簡單的自我介紹後，面試官給了小史一個問題。

面試現場

題目：我現在需要實現一個棧，這個棧除了可以進行普通的push、pop操作以外，還可以進行getMin的操作，getMin方法被調用後，會返回當前棧的最小值，你會怎麼做呢？你可以假設棧裡面存的都是int整數。

小史熟練地把代碼寫了出來。

import java.util.ArrayList;
import java.util.List;
/**
 * @author xiaoshi on 2018/9/1.
 */
public class MinStack {
 private List data = new ArrayList();
 private List mins = new ArrayList();
 public void push(int num) {
 data.add(num);
 if(mins.size() == 0) { 

 // 初始化mins
 mins.add(num);
 } else {
 // 輔助棧mins每次push當時最小值
 int min = getMin();
 if (num >= min) {
 mins.add(min);
 } else {
 mins.add(num);
 }
 }
 }
 public int pop() {
 // 棧空，異常，返回-1
 if(data.size() == 0) {
 return -1;
 }
 // pop時兩棧同步pop
 mins.remove(mins.size() - 1);
 return data.remove(data.size() - 1);
 }
 public int getMin() {
 // 棧空，異常，返回-1
 if(mins.size() == 0) {
 return -1;
 }
 // 返回mins棧頂元素
 return mins.get(mins.size() - 1);
 }
}

請教大神

小史回到學校，把面試的情況，和計算機學院的呂老師說了一下。

異常情況處理

呂老師：面試官已經提出了，你的異常處理有點問題，當棧內為空的時候，你返回-1，但是如果用戶push過-1，那麼你返回-1的時候，是用戶push進來的值，還是棧為空，就不得而知了。

小史咬咬牙：那就再定義一個類，裡面包括一個int的data、和一個boolean的isSuccess，正常情況下isSuccess是true，棧為空的話，isSuccess是false。這樣就能區分開了吧？

小史突然一拍大腿：對哦，我可以用一個包裝類Integer來定義返回值，如果是空，就代表棧為空就行了。它和int的區別就是它多了一個null，正好用來返回異常情況。

呂老師：嗯，越來越好，但是還是有點問題。你並沒有站在使用者的角度，考慮問題。使用你這個棧的人，在pop的時候，他並不知道可能返回null，如果他不做判斷，後面的代碼，就可能拋出空指針了。

呂老師發來一個表情。

呂老師：沒錯，最關鍵的是，你顯式拋出異常，如果使用者不捕獲，那麼編譯就會報錯，這樣就把錯誤，暴露在編譯階段，並且不需要和任何人，商量所謂的特殊返回值了。

算法優化

呂老師一眼看穿了小史的心思。

小史想了想：明白了，我可以在push的時候判斷一下，如果比最小值還大，就不加入輔助棧。pop的時候，如果不是最小值，輔助棧就不出棧。這樣一來，輔助棧就不會有大量重複元素了。

小史：push的時候進行判斷，如果數值比當前最小值大，就不動mins棧了，這樣mins棧中，不會保存大量冗餘的最小值。pop的時候同樣進行判斷，只有pop出的數，就是當前最小值的時候，才讓mins出棧。

小史：如果push一個和最小值相等的元素，還是要入mins棧。不然當這個最小值pop出去的時候。data中還會有一個最小值元素，而mins中卻已經沒有最小值元素了。

小史：mins棧中改存最小值在data數組中的索引。這樣一來，當push了與最小值相同元素的時候，就不需要動mins棧了。而pop的時候，pop出的元素的索引，如果不是mins棧頂元素，mins也不出棧。同時，獲取最小值的時候，需要拿到mins棧頂元素作為索引，再去data數組中，找到相應的數，作為最小值。

理解了算法之後，小史的代碼，寫起來也是非常快，不一會兒就寫好了：

import java.util.ArrayList;
import java.util.List;
/**
 * @author xiaoshi on 2018/9/1.
 */
public class MinStack {
 private List data = new ArrayList();
 private List mins = new ArrayList();
 public void push(int num) throws Exception {
 data.add(num);
 if(mins.size() == 0) {
 // 初始化mins
 mins.add(0);
 } else {
 // 輔助棧mins push最小值的索引
 int min = getMin();
 if (num < min) {
 mins.add(data.size() - 1);
 }
 }
 }
 public int pop() throws Exception {
 // 棧空，拋出異常
 if(data.size() == 0) {
 throw new Exception("棧為空");
 }
 // pop時先獲取索引
 int popIndex = data.size() - 1;
 // 獲取mins棧頂元素，它是最小值索引
 int minIndex = mins.get(mins.size() - 1);
 // 如果pop出去的索引就是最小值索引，mins才出棧
 if(popIndex == minIndex) {
 mins.remove(mins.size() - 1); 

 }
 return data.remove(data.size() - 1);
 }
 public int getMin() throws Exception {
 // 棧空，拋出異常
 if(data.size() == 0) {
 throw new Exception("棧為空");
 }
 // 獲取mins棧頂元素，它是最小值索引
 int minIndex = mins.get(mins.size() - 1);
 return data.get(minIndex);
 }
}