- 前言
- 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):
- 更新队列第一个和最后一个节点容易出错,要再三确认;
- 队列常用于广度优先搜索或缓存的实现;
- 例如,在广度优先搜索中,可以使用队列来存储需要被处理的节点。每处理一个结点,就把其相邻节点加入队列尾部。这样可以按照发现顺序处理节点;
-
需要注意的共同点:
- 要理清下标的栈大小的区别;
- 涉及栈和队列的题目往往需要编写好几个方法,要理清楚前后逻辑;
详细见以下文章:
Java | 个人总结的Java常用API手册汇总
- 有些时候我们需要访问栈底或者队列底的数据,往往需要对数据次序进行反转 *** 作;
- 我们可以每次都进行两次反转,因为要保证回到原来的样子,这样会产生大量重复 *** 作;
- 另一种做法是我们先对栈或队列进行反转,需要访问栈顶或队列顶元素时才翻转回来;
- 第二种方法需要注意翻转的时机;
- 下面《4. 化栈为队》和《5. 栈排序》都用到类似的思想;
1. 三合一 [easy] 1.1 考虑点
- 注意看提示0<=stackNum<=2,说明三个栈在数组中排列是123123123;
- 可以试着跟面试官谈谈扩展问题,如:
- 当运行栈块空间大小灵活可变时,要进行d性分割,该怎么实现;
- 可以将数组设计成环形,最后一个栈可能从数组尾处开始,环绕到数组起始处;
- 方法实现起来比较复杂,可以试着提供伪代码或其中部分代码;
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%;
- 定义三个指针,分别指向三个队列在数组的索引;
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 记录每个栈「待插入」的下标;
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;
class MinStack { Stackstack; Stack minStack; public MinStack() { Stack stack = new Stack<>(); Stack 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 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 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)的时间复杂度;
class MinStack { DequexStack; Deque minStack; public MinStack() { xStack = new linkedList (); minStack = new linkedList (); 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是往最后一个栈中放数据,而不是从前遍历找到空位;
- 注意讨论当传入cap=0时的情况;
- 可以跟面试官讨论push的两种情况:
- 第一种是:往最后一个栈中放数据(下诉解法);
- 第二种是:从前遍历找到空位(需要推出栈n+1的栈底元素到栈n,循环往复到最后一个栈);
- 前者优点是能很大程度上改善时间复杂度,后者适用一些要求所有栈(除最后一个)都填满的场景;
class StackOfPlates { int cap; List> list; public StackOfPlates(int cap) { List > list = new ArrayList<>(); this.cap = cap; this.list = list; } public void push(int val) { if( cap == 0 ){ return; } Stack stack; if( list.isEmpty() ){ stack = new Stack (); list.add(stack); } else { stack = list.get(list.size() - 1); if( stack.size() >= cap ){ stack = new Stack (); list.add(stack); } } if( stack.size() < cap ){ stack.add(val); } } public int pop() { if( cap == 0 ){ return -1; } if( list.isEmpty() ){ return -1; } Stack 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 stack = list.get(index); int result = stack.pop(); if(stack.isEmpty()){ list.remove( index ); } return result; } }
- 执行时间:60.44%;内存消耗:43.48%;
class StackOfPlates { private linkedList> 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
- 执行时间:96.23%;内存消耗:60.59%;
- 使用二维的链表存储,每次当前栈满了就新增;
4. 化栈为队 [easy] 4.1 考虑点4.2 解法 4.2.1 双栈法
- 下诉第一种解法会存在大量重复 *** 作,可以使用第二种延迟移动的方法,在有必要时才反转次序;
class MyQueue { Stackstack; Stack cache; public MyQueue() { Stack stack = new Stack<>(); Stack cache = new Stack<>(); this.stack = stack; this.cache = cache; } public void push(int x) { stack.add(x); } 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; } 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; } public boolean empty() { return stack.isEmpty(); } } 4.2.2 延迟移动法(优)
- 执行时间:81.59%;内存消耗:53.96%;
class MyQueue { DequeinStack; Deque outStack; public MyQueue() { inStack = new linkedList (); outStack = new linkedList (); } 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 { Stackstack; Stack cache; public SortedStack() { Stack stack = new Stack<>(); Stack 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.2.2 根据插入值分离栈法(优)
- 执行时间:5.04%;内存消耗:70.80%;
- 这里的单栈指每次 *** 作后数据都存储在一个栈,另一个栈只做辅助作用,可以用其他数据结构代替;
class SortedStack { //原始栈 Dequestack = new linkedList<>(); //辅助栈 Deque 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 考虑点6.2 解法 6.2.1 单链表法
- 可以问问面试官允许使用多少个链表(或其他数据结构);
- 这个问题有多种解法,如果使用一个队列,对dequeueAny() *** 作简单,而dequeueCat()和dequeueDog()则需要遍历整个队列,降低执行效率;(对应解法一)
- 另一种解法是猫狗各自创建一个队列,放进包装类里,包装类有个时间戳属性,用来标记进入时间,在执行dequeueAny() *** 作时只需要查看两个队列的的首部,比较时间戳,返回较老那位;(对应解法二)
class AnimalShelf { Listlist; public AnimalShelf() { List 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}; } } 6.2.2 双队列法(优)
- 执行时间:17.07%;内存消耗:97.72%;
class AnimalShelf { linkedListqueueCat; linkedList 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分别取对应的队首;
最后新人制作,如有错误,欢迎指出,感激不尽! 欢迎关注公众号,会分享一些更日常的东西! 如需转载,请标注出处! 欢迎分享,转载请注明来源:内存溢出
评论列表(0条)