Kotlin程序员面试算法宝典【1.5】

2.4 如何根据入栈序列判断可能的出栈序列

【出自 TX 面试题】

难度系数：★★★☆☆ 被考察系数：★★★★★

题目描述：

输入两个整数序列，其中一个序列表示栈的 push（入）顺序，判断另一个序列有没有可能是对应的 pop（出）顺序。

分析与解答：

假如输入的 push 序列是 1、 2、 3、 4、 5，那么 3、 2、 5、 4、 1 就有可能是一个 pop 序列，但 5、 3、 4、 1、 2 就不可能是它的一个 pop 序列。

主要思路是使用一个栈来模拟入栈顺序，具体步骤如下：

（ 1）把 push 序列依次入栈，直到栈顶元素等于 pop 序列的第一个元素，然后栈顶元素出栈， pop 序列移动到第二个元素。

（ 2）如果栈顶继续等于 pop 序列现在的元素，则继续出栈并 pop 后移；否则对 push 序列继续入栈。

（ 3）如果 push 序列已经全部入栈，但是 pop 序列未全部遍历，而且栈顶元素不等于当前pop 元素，那么这个序列不是一个可能的出栈序列。如果栈为空，而且 pop 序列也全部被遍历过，则说明这是一个可能的 pop 序列。下图给出一个合理的 pop 序列的判断过程。

在上图中， （ 1）～（ 3）三步，由于栈顶元素不等于 pop 序列第一个元素 3，因此， 1，2，3依次入栈，当 3 入栈后，栈顶元素等于 pop 序列的第一个元素 3，因此，第（ 4）步执行 3 出栈，接下来指向第二个 pop 序列 2，且栈顶元素等于 pop 序列的当前元素，因此，第（ 5）步执行 2 出栈；接着由于栈顶元素 4 不等于当前 pop 序列 5，因此，接下来（ 6）和（ 7）两步分别执行 4 和 5 入栈；接着由于栈顶元素 5 等于 pop 序列的当前值，因此，第（ 8）步执行 5 出栈，接下来（ 9）和（ 10）两步栈顶元素都等于当前 pop 序列的元素，因此，都执行出栈操作。最后由于栈为空，同时 pop 序列都完成了遍历，因此， {3，2，5，4，1}是一个合理的出栈序列。

实现代码如下：

import java.util.Stack fun isPopSerial（push： String？， pop： String？）： Boolean { if （push == null || pop == null） return false val pushLen = push.length val popLen = pop.length if （pushLen ！= popLen） return false var pushIndex = 0 var popIndex = 0 val stack = Stack<Char>（） while （pushIndex < pushLen） { //把 push 序列依次入栈，直到栈顶元素等于 pop 序列的第一个元素 stack.push（push[pushIndex]） pushIndex++ //栈顶元素出栈， pop 序列移动到下一个元素 while （！stack.empty（） && stack.peek（） == pop[popIndex]） { stack.pop（） popIndex++ } } //栈为空，且 pop 序列中元素都被遍历过 return stack.empty（） && popIndex == popLen } fun main（args： Array<String>） { val push = "12345" val pop = "32541" if （isPopSerial（push， pop）） println（"${pop}是${push}的一个 pop 序列"） else println（"${pop}不是${push}的一个 pop 序列"） }

程序的运行结果如下： 32541 是 12345 的一个 pop 序列

算法性能分析：

这种方法在处理一个合理的 pop 序列的时候需要操作的次数最多，即把 push 序列进行一次压栈和出栈操作，操作次数为 2N，因此，时间复杂度为 O（N），此外，这种方法使用了额外的栈空间，因此，空间复杂度为 O（N）。

2.5 如何用 O（1）的时间复杂度求栈中最小元素

【出自 XM 面试题】

由于栈具有后进先出的特点，因此， push 和 pop 只需要对栈顶元素进行操作。如果使用上述的实现方式，只能访问到栈顶的元素，无法得到栈中最小的元素。当然，可以用另外一个变量来记录栈底的位置，通过遍历栈中所有的元素找出最小值，但是这种方法的时间复杂度为 O（N），那么如何才能用 O（1）的时间复杂度求出栈中最小的元素呢？

在算法设计中，经常会采用空间换取时间的方式来提高时间复杂度，也就是说采用额外的存储空间来降低操作的时间复杂度。具体而言，在实现的时候使用两个栈结构，一个栈用来存储数据，另外一个栈用来存储栈的最小元素。实现思路如下：如果当前入栈的元素比原来栈中的最小值还小，则把这个值压入保存最小元素的栈中；在出栈的时候，如果当前出栈的元素恰好为当前栈中的最小值，保存最小值的栈顶元素也出栈，使得当前最小值变为当前最小值入栈之前的那个最小值。为了简单起见，可以在栈中保存 int 类型。

实现代码如下：

import java.util.Stack class MyStack { /* 用来存储栈中元素 */ private val elemStack = Stack<Int>（） /* 栈顶永远存储当前 elemStack 中最小的值 */ private val minStack = Stack<Int>（） fun push（data： Int） { elemStack.push（data） // 更新保存最小元素的栈 if （minStack.empty（）） minStack.push（data） else { if （data <minStack.peek（）） minStack.push（data） } } fun pop（）： Int { val topData = elemStack.peek（） elemStack.pop（） if （topData == min（）） minStack.pop（） return topData } fun min（）： Int { return if （minStack.empty（）） Integer.MAX_VALUE else minStack.peek（） } } fun main（args： Array<String>） { val stack = MyStack（） stack.push（5） println（"栈中最小值为： ${stack.min（）}"） stack.push（6） println（"栈中最小值为： ${stack.min（）}"） stack.push（2） println（"栈中最小值为： ${stack.min（）}"） stack.pop（） println（"栈中最小值为： ${stack.min（）}"） }

程序的运行结果如下： 栈中最小值为： 5 栈中最小值为： 5 栈中最小值为： 2 栈中最小值为： 5

算法性能分析：

这种方法申请了额外的一个栈空间来保存栈中最小的元素，从而达到了用 O（1）的时间复杂度求栈中最小元素的目的，但是付出的代价是空间复杂度为 O（N）。

2.6 如何用两个栈模拟队列操作

【出自 JD 面试题】

题目要求用两个栈来模拟队列，假设使用栈 A 与栈 B 模拟队列 Q， A 为插入栈， B 为弹出栈，以实现队列 Q。

再假设 A 和 B 都为空，可以认为栈 A 提供入队列的功能，栈 B 提供出队列的功能。要入队列，入栈 A 即可，而出队列则需要分两种情况考虑：

（ 1）如果栈 B 不为空，则直接弹出栈 B 的数据。

（ 2）如果栈 B 为空，则依次弹出栈 A 的数据，放入栈 B 中，再弹出栈 B 的数据。

实现代码如下：

import java.util.Stack class MyStack<T> { private val a = Stack<T>（） //用来存储栈中元素 private val b = Stack<T>（） //用来存储当前栈中最小的元素 fun push（data： T） { a.push（data） } fun pop（）： T { if （b.empty（）） { while （！a.empty（）） { b.push（a.peek（）） a.pop（） } } val first = b.peek（） b.pop（） return first } } fun main（args： Array<String>） { val stack = MyStack<Int>（） stack.push（1） stack.push（2） println（"队列首元素为： ${stack.pop（）}"） println（"队列首元素为： ${stack.pop（）}"） }

程序的运行结果为 队列首元素为： 1 队列首元素为： 2

算法性能分析：

这种方法入队操作的时间复杂度为 O（1），出队列操作的时间复杂度则依赖于入队与出队执行的频率。总体来讲，出队列操作的时间复杂度为 O（1），当然会有个别操作需要耗费更多的时间（因为需要从两个栈之间移动数据）。

2.7 如何设计一个排序系统

【出自 TX 笔试题】

请设计一个排队系统，能够让每个进入队伍的用户都能看到自己在队列中所处的位置和变化，队伍可能随时有人加入和退出；当有人退出影响到用户的位置排名时需要及时反馈到用户。

分析与解答：

本题不仅要实现队列常见的入队列与出队列的功能，而且还需要实现队列中任意一个元素都可以随时出队列，且出队列后需要更新队列用户位置的变化。实现代码如下：

import java.util.LinkedList /** * @param id 唯一标识一个用户 */ data class User（val id： Int， var name： String？， var seq： Int = 0） class MyQueue { private val q = LinkedList<User>（） fun enQueue（u： User）//进入队列尾部 { u.seq = q.size + 1 q.add（u） } //队头出队列 fun deQueue（） { q.poll（） updateSeq（） } //队列中的人随机离开 fun deQueue（u： User） { q.remove（u） updateSeq（） } //出队列后更新队列中每个人的序列 fun updateSeq（） { var i = 1 for （u in q） u.seq = i++ } //打印队列的信息 fun printList（） { for （u in q） println（u） } } fun main（args： Array<String>） { val u1 = User（1， "user1"） val u2 = User（2， "user2"） val u3 = User（3， "user3"） val u4 = User（4， "user4"） val queue = MyQueue（） queue.enQueue（u1） queue.enQueue（u2） queue.enQueue（u3） queue.enQueue（u4） queue.deQueue（） //队首元素 u1 出队列 queue.deQueue（u3） //队列中间的元素 u3 出队列 queue.printList（） }

程序的运行结果如下： User（id=2， name=user2， seq=1） User（id=4， name=user4， seq=2）

2.8 如何实现 LRU 缓存方案

【出自 MT 面试题】

难度系数：★★★★☆ 被考察系数：★★★★☆

题目描述

LRU 是 Least Recently Used 的缩写，它的意思是“最近最少使用”， LRU 缓存就是使用这种原理实现，简单地说就是缓存一定量的数据，当超过设定的阈值时就把一些过期的数据删除掉。 常用于页面置换算法， 是虚拟页式存储管理中常用的算法。 如何实现 LRU 缓存方案？

分析与解答：

可以使用两个数据结构实现一个 LRU 缓存。

（ 1）使用双向链表实现的队列，队列的最大容量为缓存的大小。在使用过程中，把最近使用的页面移动到队列头，最近没有使用的页面将被放在队列尾的位置。

（ 2）使用一个哈希表，把页号作为键，把缓存在队列中的结点的地址作为值。

当引用一个页面时，所需的页面在内存中，需要把这个页对应的结点移动到队列的前面。如果所需的页面不在内存中，我们将它存储在内存中。简单地说，就是将一个新结点添加到队列的前面，并在哈希表中更新相应的结点地址。如果队列是满的，那么就从队列尾部移除一个结点，并将新结点添加到队列的前面。实现代码如下：

import java.util.* class LRU（private val cacheSize： Int） { private val queue = ArrayDeque<Int>（） private val hashSet = hashSetOf<Int>（） /* 判断缓存队列是否已满 */ private val isQueueFull： Boolean get（） = queue.size == cacheSize /* 把页号为 pageNum 的页缓存到队列中，同时也添加到 Hash 表中 */ private fun enqueue（pageNum： Int） { /* 如果队列满了，需要删除队尾的缓存的页 */ if （isQueueFull） { hashSet.remove（queue.last） queue.pollLast（） } queue.addFirst（pageNum） /* 把新缓存的结点同时添加到 hash 表中 */ hashSet.add（pageNum） } /* * 当访问某一个 page 的时候会调用这个函数，对于访问的 page 有两种情况： * 1. 如果 page 在缓存队列中，直接把这个结点移动到队首。 * 2. 如果 page 不在缓存队列中，把这个 page 缓存到队首。 */ fun accessPage（pageNum： Int） { /* page 不在缓存队列中，把它缓存到队首 */ if （！hashSet.contains（pageNum）） enqueue（pageNum） else if （pageNum ！= queue.first） { queue.remove（pageNum） queue.addFirst（pageNum） }/* page 已经在缓存队列中了，移动到队首 */ } fun printQueue（） { while （！queue.isEmpty（）） { print（"${queue.pop（）} "） } } } fun main（args： Array<String>） { /* 假设缓存大小为 3 */ val lru = LRU（3） /* 访问 page */ lru.accessPage（1） lru.accessPage（2） lru.accessPage（5） lru.accessPage（1） lru.accessPage（6） lru.accessPage（7） /* 通过上面的访问序列后，缓存的信息为 */ lru.printQueue（） }

程序运行结果为 7 6 1