目錄
- 前言
- 0. *經驗總結
- 0.1 程式員面試金典 P82
- 0.2 Java常用資料結構API
- 0.3 關于延遲移動
- 1. 三合一 [easy]
- 1.1 考慮點
- 1.2 解法
- 1.2.1 三指標法
- 1.2.2 二維陣列法（優）
- 1.2.3 一維陣列法
- 2. 堆疊的最小值 [easy]
- 2.1 考慮點
- 2.2 解法
- 2.2.1 回圈遍歷法
- 2.2.2 主輔堆疊法（優）
- 3. 堆盤子 [medium]
- 3.1 考慮點
- 3.2 解法
- 3.2.1 單鏈表尋堆疊法
- 3.2.2 二維鏈表法（優）
- 4. 化堆疊為隊 [easy]
- 4.1 考慮點
- 4.2 解法
- 4.2.1 雙堆疊法
- 4.2.2 延遲移動法（優）
- 5. 堆疊排序 [medium]
- 5.1 考慮點
- 5.2 解法
- 5.2.1 單堆疊法
- 5.2.2 根據插入值分離堆疊法（優）
- 6. 動物收容所 [easy]
- 6.1 考慮點
- 6.2 解法
- 6.2.1 單鏈表法
- 6.2.2 雙佇列法（優）
- 最后
前言
本系列筆記主要記錄筆者刷《程式員面試金典》演算法的一些想法與經驗總結，按專題分類，主要由兩部分構成：經驗值點和經典題目，其中重點放在經典題目上；
0. *經驗總結
0.1 程式員面試金典 P82
-
堆疊 - 后進先出（LIFO）：
- 堆疊無法在常數時間復雜度內訪問第i個元素，但因為堆疊不需要在添加和洗掉時移動元素，可以在常數時間復雜度內完成此操作；
- 對于遞回演算法：有時需要把臨時變數加入到堆疊中，在回溯時洗掉；
-
佇列 - 先進先出（FIFO）：
- 更新佇列第一個和最后一個節點容易出錯，要再三確認；
- 佇列常用于廣度優先搜索或快取的實作；
- 例如，在廣度優先搜索中，可以使用佇列來存盤需要被處理的節點，每處理一個結點，就把其相鄰節點加入佇列尾部，這樣可以按照發現順序處理節點；
-
需要注意的共同點：
- 要理清下標的堆疊大小的區別；
- 涉及堆疊和佇列的題目往往需要撰寫好幾個方法，要理清楚前后邏輯；
0.2 Java常用資料結構API
詳細見以下文章：
Java | 個人總結的Java常用API手冊匯總
0.3 關于延遲移動
- 有些時候我們需要訪問堆疊底或者佇列底的資料，往往需要對資料次序進行反轉操作；
- 我們可以每次都進行兩次反轉，因為要保證回到原來的樣子，這樣會產生大量重復操作；
- 另一種做法是我們先對堆疊或佇列進行反轉，需要訪問堆疊頂或佇列頂元素時才翻轉回來；
- 第二種方法需要注意翻轉的時機；
- 下面《4. 化堆疊為隊》和《5. 堆疊排序》都用到類似的思想；
1. 三合一 [easy]
1.1 考慮點
- 注意看提示
0<=stackNum<=2，說明三個堆疊在陣列中排列是123123123； - 可以試著跟面試官談談擴展問題，如：
- 當運行堆疊塊空間大小靈活可變時，要進行彈性分割，該怎么實作；
- 可以將陣列設計成環形，最后一個堆疊可能從陣列尾處開始，環繞到陣列起始處；
- 方法實作起來比較復雜，可以試著提供偽代碼或其中部分代碼；
1.2 解法
1.2.1 三指標法
class TripleInOne {
int[] stack;
int stackSize;
int t0;
int t1;
int t2;
public TripleInOne(int stackSize) {
stack = new int[stackSize*3];
int t0 = -3;
int t1 = -2;
int t2 = -1;
this.stackSize = stackSize;
this.t0 = t0;
this.t1 = t1;
this.t2 = t2;
}
public void push(int stackNum, int value) {
if( stackNum == 0 ){
this.t0 = pushVal( t0, value );
} else if( stackNum == 1 ){
this.t1 = pushVal( t1, value);
} else if( stackNum == 2){
this.t2 = pushVal( t2, value);
}
}
public int pushVal( int top, int value ){
if( top + 3 < stackSize*3 ){
top += 3;
stack[top] = value;
}
return top;
}
public int pop(int stackNum) {
int val = peek(stackNum);
if( val != -1 ){
if( stackNum == 0 ){
stack[t0] = -1;
t0 -= 3;
} else if( stackNum == 1 ){
stack[t1] = -1;
t1 -= 3;
} else if( stackNum == 2){
stack[t2] = -1;
t2 -= 3;
}
return val;
}
return -1;
}
public int peek(int stackNum) {
if( stackNum == 0 && t0 >= 0 ){
return stack[t0];
} else if( stackNum == 1 && t1 >= 1){
return stack[t1];
} else if( stackNum == 2 && t2 >= 2){
return stack[t2];
}
return -1;
}
public boolean isEmpty(int stackNum) {
int value = https://www.cnblogs.com/dlhjw/p/peek(stackNum);
if( value == -1){
return true;
}
return false;
}
}
- 執行時間：34.80%；記憶體消耗：44.07%；
- 定義三個指標，分別指向三個佇列在陣列的索引；
1.2.2 二維陣列法（優）
class TripleInOne {
int N = 3;
// 3 * n 的陣列，每一行代表一個堆疊
int[][] data;
// 記錄每個堆疊「待插入」位置
int[] locations;
public TripleInOne(int stackSize) {
data = https://www.cnblogs.com/dlhjw/p/new int[N][stackSize];
locations = new int[N];
}
public void push(int stackNum, int value) {
int[] stk = data[stackNum];
int loc = locations[stackNum];
if (loc < stk.length) {
stk[loc] = value;
locations[stackNum]++;
}
}
public int pop(int stackNum) {
int[] stk = data[stackNum];
int loc = locations[stackNum];
if (loc > 0) {
int val = stk[loc - 1];
locations[stackNum]--;
return val;
} else {
return -1;
}
}
public int peek(int stackNum) {
int[] stk = data[stackNum];
int loc = locations[stackNum];
if (loc > 0) {
return stk[loc - 1];
} else {
return -1;
}
}
public boolean isEmpty(int stackNum) {
return locations[stackNum] == 0;
}
}
- 執行時間：97.06%；記憶體消耗：69.49%；
- 時間復雜度：所有的操作均為 O(1)，
- 空間復雜度：O(k*n)，k 為我們需要實作的堆疊的個數，n 為堆疊的容量；
- 建立一個二維陣列 datadata ；二維陣列的每一行代表一個堆疊，同時使用一個locationslocations 記錄每個堆疊「待插入」的下標；
1.2.3 一維陣列法
class TripleInOne {
int N = 3;
int[] data;
int[] locations;
int size;
public TripleInOne(int stackSize) {
size = stackSize;
data = https://www.cnblogs.com/dlhjw/p/new int[size * N];
locations = new int[N];
for (int i = 0; i < N; i++) {
locations[i] = i * size;
}
}
public void push(int stackNum, int value) {
int idx = locations[stackNum];
if (idx < (stackNum + 1) * size) {
data[idx] = value;
locations[stackNum]++;
}
}
public int pop(int stackNum) {
int idx = locations[stackNum];
if (idx > stackNum * size) {
locations[stackNum]--;
return data[idx - 1];
} else {
return -1;
}
}
public int peek(int stackNum) {
int idx = locations[stackNum];
if (idx > stackNum * size) {
return data[idx - 1];
} else {
return -1;
}
}
public boolean isEmpty(int stackNum) {
return locations[stackNum] == stackNum * size;
}
}
- 執行時間：97.06%；記憶體消耗：44.07%；
2. 堆疊的最小值 [easy]
2.1 考慮點
- 把加入一個元素看成一種狀態，每種狀態都有對應最小值，這樣得到解法2；
2.2 解法
2.2.1 回圈遍歷法
class MinStack {
Stack<Integer> stack;
Stack<Integer> minStack;
/** initialize your data structure here. */
public MinStack() {
Stack<Integer> stack = new Stack<>();
Stack<Integer> minStack = new Stack<>();
this.stack = stack;
this.minStack = minStack;
}
public void push(int x) {
stack.add(x);
if( minStack.isEmpty() ){
minStack.add(x);
return;
}
Stack<Integer> cache = new Stack<>();
boolean isMatter = false;
while( !isMatter ){
if( !minStack.isEmpty() && minStack.peek() < x ){
cache.add( minStack.pop() );
} else {
minStack.add(x);
isMatter = true;
}
}
while( !cache.isEmpty() ){
minStack.add(cache.pop());
}
}
public void pop() {
if( stack.isEmpty() ){
return;
}
int topNum = stack.pop();
Stack<Integer> cache = new Stack<>();
boolean isMatter = false;
while( !isMatter ){
if( minStack.peek() == topNum ){
minStack.pop();
isMatter = true;
} else {
cache.add(minStack.pop());
}
}
while( !cache.isEmpty() ){
minStack.add(cache.pop());
}
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
- 執行時間：5.02%；記憶體消耗：5.18%；
- 不推薦用此方法，不滿足O(1)的時間復雜度；
2.2.2 主輔堆疊法（優）
class MinStack {
Deque<Integer> xStack;
Deque<Integer> minStack;
public MinStack() {
xStack = new LinkedList<Integer>();
minStack = new LinkedList<Integer>();
minStack.push(Integer.MAX_VALUE);
}
public void push(int x) {
xStack.push(x);
minStack.push(Math.min(minStack.peek(), x));
}
public void pop() {
xStack.pop();
minStack.pop();
}
public int top() {
return xStack.peek();
}
public int getMin() {
return minStack.peek();
}
}
- 執行時間：91.63%；記憶體消耗：58.64%；
- 創建兩個堆疊，一個堆疊是主堆疊 stackstack，另一個是輔助堆疊 minStackminStack，用于存放對應主堆疊不同時期的最小值；
、
3. 堆盤子 [medium]
- push是往最后一個堆疊中放資料，而不是從前遍歷找到空位；
3.1 考慮點
- 注意討論當傳入cap=0時的情況；
- 可以跟面試官討論push的兩種情況：
- 第一種是：往最后一個堆疊中放資料（下訴解法）；
- 第二種是：從前遍歷找到空位（需要推出堆疊n+1的堆疊底元素到堆疊n，回圈往復到最后一個堆疊）；
- 前者優點是能很大程度上改善時間復雜度，后者適用一些要求所有堆疊（除最后一個）都填滿的場景；
3.2 解法
3.2.1 單鏈表尋堆疊法
class StackOfPlates {
int cap;
List<Stack<Integer>> list;
public StackOfPlates(int cap) {
List<Stack<Integer>> list = new ArrayList<>();
this.cap = cap;
this.list = list;
}
public void push(int val) {
if( cap == 0 ){
return;
}
Stack<Integer> stack;
if( list.isEmpty() ){
stack = new Stack<Integer>();
list.add(stack);
} else {
stack = list.get(list.size() - 1);
if( stack.size() >= cap ){
stack = new Stack<Integer>();
list.add(stack);
}
}
if( stack.size() < cap ){
stack.add(val);
}
}
public int pop() {
if( cap == 0 ){
return -1;
}
if( list.isEmpty() ){
return -1;
}
Stack<Integer> stack = list.get(list.size() - 1);
int result = stack.pop();
if(stack.isEmpty()){
list.remove( list.size() - 1 );
}
return result;
}
public int popAt(int index) {
if( cap == 0 ){
return -1;
}
if( index > list.size()-1 || index < 0 || list.isEmpty() ){
return -1;
}
Stack<Integer> stack = list.get(index);
int result = stack.pop();
if(stack.isEmpty()){
list.remove( index );
}
return result;
}
}
- 執行時間：60.44%；記憶體消耗：43.48%；
3.2.2 二維鏈表法（優）
class StackOfPlates {
private LinkedList<LinkedList<Integer>> setOfStacks;
private int cap;
public StackOfPlates(int cap) {
this.setOfStacks = new LinkedList<>();
this.cap = cap;
}
private boolean setIsEmpty() {
return setOfStacks.isEmpty();
}
private boolean lastStackIsFUll() {
if (setIsEmpty()) {
return true;
}
return setOfStacks.getLast().size()>=cap;
}
private boolean lastStackIsEmpty() {
return setOfStacks.getLast().isEmpty();
}
public void push(int val) {
if (cap <= 0) {
return;
}
if (setIsEmpty() || lastStackIsFUll()) {
setOfStacks.addLast(new LinkedList<>());
}
setOfStacks.getLast().addLast(val);
}
public int pop() {
int val = -1;
if (setIsEmpty()) {
return val;
}
val = setOfStacks.getLast().removeLast();
if (lastStackIsEmpty()) {
setOfStacks.removeLast();
}
return val;
}
public int popAt(int index) {
int val = -1;
if (setIsEmpty() ||setOfStacks.size()-1<index ) {
return val;
}
val = setOfStacks.get(index).removeLast();
if (setOfStacks.get(index).isEmpty()) {
setOfStacks.remove(index);
}
return val;
}
}
- 執行時間：96.23%；記憶體消耗：60.59%；
- 使用二維的鏈表存盤，每次當前堆疊滿了就新增；
4. 化堆疊為隊 [easy]
4.1 考慮點
- 下訴第一種解法會存在大量重復操作，可以使用第二種延遲移動的方法，在有必要時才反轉次序；
4.2 解法
4.2.1 雙堆疊法
class MyQueue {
Stack<Integer> stack;
Stack<Integer> cache;
/** Initialize your data structure here. */
public MyQueue() {
Stack<Integer> stack = new Stack<>();
Stack<Integer> cache = new Stack<>();
this.stack = stack;
this.cache = cache;
}
/** Push element x to the back of queue. */
public void push(int x) {
stack.add(x);
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
if(stack.isEmpty()){
return -1;
}
while( !stack.isEmpty() ){
cache.add(stack.pop());
}
int result = cache.pop();
while( !cache.isEmpty() ){
stack.add(cache.pop());
}
return result;
}
/** Get the front element. */
public int peek() {
if(stack.isEmpty()){
return -1;
}
while( !stack.isEmpty() ){
cache.add(stack.pop());
}
int result = cache.peek();
while( !cache.isEmpty() ){
stack.add(cache.pop());
}
return result;
}
/** Returns whether the queue is empty. */
public boolean empty() {
return stack.isEmpty();
}
}
- 執行時間：81.59%；記憶體消耗：53.96%；
4.2.2 延遲移動法（優）
class MyQueue {
Deque<Integer> inStack;
Deque<Integer> outStack;
public MyQueue() {
inStack = new LinkedList<Integer>();
outStack = new LinkedList<Integer>();
}
public void push(int x) {
inStack.push(x);
}
public int pop() {
if (outStack.isEmpty()) {
in2out();
}
return outStack.pop();
}
public int peek() {
if (outStack.isEmpty()) {
in2out();
}
return outStack.peek();
}
public boolean empty() {
return inStack.isEmpty() && outStack.isEmpty();
}
private void in2out() {
while (!inStack.isEmpty()) {
outStack.push(inStack.pop());
}
}
}
- 執行時間：100.00%；記憶體消耗：35.19%；
- 只有進行pop()和peek()操作，并且輸出堆疊為空時才需要翻轉次序；
- 當有必要反轉次序時才移動元素，用戶進行連續pop()操作時不需要反轉次序；
5. 堆疊排序 [medium]
5.1 考慮點
- 需要注意細節；
- 可以考慮延遲移動；
5.2 解法
5.2.1 單堆疊法
class SortedStack {
Stack<Integer> stack;
Stack<Integer> cache;
public SortedStack() {
Stack<Integer> stack = new Stack<>();
Stack<Integer> cache = new Stack<>();
this.stack = stack;
this.cache = cache;
}
public void push(int val) {
if( stack.isEmpty() ){
stack.add(val);
return;
}
if( stack.peek() > val ){
stack.add(val);
} else {
cache.add(stack.pop());
stack.add(val);
stack.add(cache.pop());
}
}
public void pop() {
if( stack.isEmpty() ){
return;
}
stack.pop();
int val;
if( !stack.isEmpty() ){
val = stack.peek(); //忘記peek
} else {
return;
}
while(!stack.isEmpty()){
if( stack.peek() >= val ){
cache.add(stack.pop());
} else {
val = stack.peek();
}
}
boolean isEliminate = false;
while( !cache.isEmpty() ){
if( cache.peek() == val && !isEliminate ){
cache.pop();
isEliminate = true; //忘記上鎖
} else {
stack.add( cache.pop() );
}
}
stack.add(val);
}
public int peek() {
if(stack.isEmpty()){
return -1;
}
return stack.peek();
}
public boolean isEmpty() {
return stack.isEmpty();
}
}
- 執行時間：5.04%；記憶體消耗：70.80%；
- 這里的單堆疊指每次操作后資料都存盤在一個堆疊，另一個堆疊只做輔助作用，可以用其他資料結構代替；
5.2.2 根據插入值分離堆疊法（優）
class SortedStack {
//原始堆疊
Deque<Integer> stack = new LinkedList<>();
//輔助堆疊
Deque<Integer> tmp = new LinkedList<>();
public SortedStack() {
}
public void push(int val) {
int max = stack.isEmpty() ? Integer.MAX_VALUE : stack.peek();
int min = tmp.isEmpty() ? Integer.MIN_VALUE : tmp.peek();
//比較原始堆疊與輔助堆疊堆疊頂值，使其滿足 輔助堆疊 <= val <= 原始堆疊
while(true){
if(val > max){
tmp.push(stack.pop());
max = stack.isEmpty() ? Integer.MAX_VALUE : stack.peek();
} else if(val < min){
stack.push(tmp.pop());
min = tmp.isEmpty() ? Integer.MIN_VALUE : tmp.peek();
} else{
stack.push(val);
break;
}
}
}
public void pop() {
//將輔助堆疊元素push回原始堆疊
while (!tmp.isEmpty()){
stack.push(tmp.pop());
}
if (!stack.isEmpty())
stack.pop();
}
public int peek() {
//將輔助堆疊元素push回原始堆疊
while (!tmp.isEmpty()){
stack.push(tmp.pop());
}
return stack.isEmpty() ? -1 : stack.peek();
}
public boolean isEmpty() {
return stack.isEmpty() && tmp.isEmpty();
}
}
- 執行時間：99.65%；記憶體消耗：81.59%；
- push()操作后資料可以分布在兩個堆疊中，只有pop()或peek()操作時才考慮將儲存值比較小的堆疊歸位；
6. 動物收容所 [easy]
6.1 考慮點
- 可以問問面試官允許使用多少個鏈表（或其他資料結構）；
- 這個問題有多種解法，如果使用一個佇列，對
dequeueAny()操作簡單，而dequeueCat()和dequeueDog()則需要遍歷整個佇列，降低執行效率；（對應解法一） - 另一種解法是貓狗各自創建一個佇列，放進包裝類里，包裝類有個時間戳屬性，用來標記進入時間，在執行
dequeueAny()操作時只需要查看兩個佇列的的首部，比較時間戳，回傳較老那位；（對應解法二）
6.2 解法
6.2.1 單鏈表法
class AnimalShelf {
List<String> list;
public AnimalShelf() {
List<String> list = new ArrayList<>();
this.list = list;
}
public void enqueue(int[] animal) {
if( animal[0] < 0 || animal[1] < 0 || animal[1] > 2){
return;
}
String animalStr = String.valueOf(animal[0]) + String.valueOf(animal[1]);
list.add(animalStr);
}
public int[] dequeueAny() {
if( list.isEmpty() ){
return new int[]{-1, -1};
}
String result = list.get(0);
list.remove(0);
int num = Integer.parseInt(result);
return new int[]{num/10, num%10};
}
public int[] dequeueDog() {
if( list.isEmpty() ){
return new int[]{-1, -1};
}
for( int i = 0; i < list.size(); i++){
int num = Integer.parseInt( list.get(i) );
if( num%10 == 1 ){
list.remove(i);
return new int[]{num/10, num%10};
}
}
return new int[]{-1, -1};
}
public int[] dequeueCat() {
if( list.isEmpty() ){
return new int[]{-1, -1};
}
for( int i = 0; i < list.size(); i++){
int num = Integer.parseInt( list.get(i) );
if( num%10 == 0 ){
list.remove(i);
return new int[]{num/10, num%10};
}
}
return new int[]{-1, -1};
}
}
- 執行時間：17.07%；記憶體消耗：97.72%；
6.2.2 雙佇列法（優）
class AnimalShelf {
LinkedList<int[]> queueCat;
LinkedList<int[]> queueDog;
public AnimalShelf() {
queueCat = new LinkedList<>();
queueDog = new LinkedList<>();
}
public void enqueue(int[] animal) {
// 判斷種類后入隊
if (animal[1] == 0) {
queueCat.addLast(animal);
} else if (animal[1] == 1) {
queueDog.addLast(animal);
}
}
public int[] dequeueAny() {
// 取出cat的隊首，判空則直接回傳
int[] headCat;
if (!queueCat.isEmpty()) {
headCat = queueCat.getFirst();
} else if (!queueDog.isEmpty()) {
return queueDog.removeFirst();
} else {
return new int[]{-1,-1};
}
// 取出dog的隊首，判空則直接回傳
int[] headDog;
if (!queueDog.isEmpty()) {
headDog = queueDog.getFirst();
} else {
return queueCat.removeFirst();
}
// 比較后回傳
if (headCat[0]<=headDog[0]) {
return queueCat.removeFirst();
} else {
return queueDog.removeFirst();
}
}
public int[] dequeueDog() {
if (!queueDog.isEmpty()) {
return queueDog.removeFirst();
} else {
return new int[]{-1,-1};
}
}
public int[] dequeueCat() {
if (!queueCat.isEmpty()) {
return queueCat.removeFirst();
} else {
return new int[]{-1,-1};
}
}
}
- 執行時間：98.86；記憶體消耗：29.43%；
- 建立兩個佇列，分別存盤貓和狗，dequeCat和dequeDog分別取對應的隊首；
最后
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/320895.html
標籤：其他
上一篇：網線水晶頭制作