目录
前言
本系列笔记主要记录笔者刷《程序员面试金典》算法的一些想法与经验总结，按专题分类，主要由两部分构成：经验值点和经典题目。其中重点放在经典题目上；
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 = 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 = 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 = 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分别取对应的队首；
最后
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
