论述题1. 题目描述:
如何用两个栈模拟队列操作?
题目要求用两个栈来模拟队列,假设使用栈A与栈B模拟队列Q,A为插入栈,B为弹出栈,以实现队列Q。
再假设A和B都为空,可以认为栈A提供入队列的功能,栈B提供出队列的功能。
要入队列,入栈A即可,而出队列则需要分两种情况考虑:
(1)如果栈B不为空,则直接弹出栈B的数据。
(2)如果栈B为空,则依次弹出栈A的数据,放入栈B中,再弹出栈B的数据。
实现代码如下:
package main
import(
."github.com/isdamir/gotype" //引入定义的数据结构
"fmt"
)
typeStackQueuestruct{
aStack*SliceStack
bStack*SliceStack
}
func(p*StackQueue)Push(data int){
p.aStack.Push(data)
}
func(p*StackQueue)Pop()int{
if p.bStack.IsEmpty(){
for !p.aStack.IsEmpty(){
p.bStack.Push(p.aStack.Pop())
}
}
return p.bStack.Pop().(int)
}
func main(){
stack:=&StackQueue{aStack:&SliceStack{}, bstack&SliceStack{}}
stack.Push(1)
stack.Push(2)
fmt.Println("队列首元素为:", stack.Pop())
fmt.Println("队列首元素为:", stack.Pop())
}
程序的运行结果为
队列首元素为:1
队列首元素为:2
算法性能分析:
这种方法入队操作的时间复杂度为O(1),出队列操作的时间复杂度则依赖于入队与出队执行的频率。总体来讲,出队列操作的时间复杂度为O(1),当然会有个别操作需要耗费更多的时间(因为需要从两个栈之间移动数据)。
[考点] 如何用两个栈模拟队列操作
2. 题目描述:
请设计一个排队系统,能够让每个进入队伍的用户都能看到自己在队列中所处的位置和变化,队伍可能随时有人加入和退出;当有人退出影响到用户的位置排名时需要及时反馈到用户。
本题不仅要实现队列常见的入队列与出队列的功能,而且还需要实现队列中任意一个元素都可以随时出队列,且出队列后需要更新队列用户位置的变化。实现代码如下:
package main
import(
."github.com/isdamir/gotype" //引入定义的数据结构
"fmt"
)
//用于定义对象
typeUserstruct{
id int
name string
seq int
}
typeLoginQueuestruct{
queue*SliceQueue
}
//进入队列尾部
func(p*LoginQueue)EnQueue(u*User){
p.queue.EnQueue(u)
u.seq=p.queue.Size()
}
//出队列
func(p*LoginQueue)DeQueue(){
p.queue.DeQueue()
p.UpdateSeq()
}
//队列中的人随机离开
func(p*LoginQueue)DeQueueUser(u*User){
p.queue.Remove(u)
p.UpdateSeq()
}
func(p*LoginQueue)UpdateSeq(){
i:=1
for_, v:=range p.queue.List(){
u:=v.(*User)
u.seq=i
i++
}
}
func(p*LoginQueue)PrintQueue(){
for_, v:=range p.queue.List(){
fmt.Println(v.(*User))
}
}
func main(){
u1:=&User{id:1, name:"user1"}
u2:=&User{id:2, name:"user2"}
u3:=&User{id:3, name:"user3"}
u4:=&User{id:4, name:"user4"}
loginQueue:=&LoginQueue{queue:NewSliceQueue()}
loginQueue.EnQueue(u1)
loginQueue.EnQueue(u2)
loginQueue.EnQueue(u3)
loginQueue.EnQueue(u4)
loginQueue.DeQueue() //队首元素u1出队列
loginQueue.DeQueueUser(u3) //队列中间的元素u3出队列
loginQueue.PrintQueue()
}
程序的运行结果为
id:2 name:user2 seq:1
id:4 name:user4 seq:2
[考点] 如何设计一个排序系统
3. 题目描述:
LRU是Least Recently Used的缩写,它的意思是“最近最少使用”,LRU缓存就是使用这种原理实现,简单地说就是缓存一定量的数据,当超过设定的阈值时就把一些过期的数据删除掉。常用于页面置换算法,是为虚拟页式存储管理中常用的算法。下面介绍如何实现LRU缓存方案。
我们可以使用两个数据结构实现一个LRU缓存。
(1)使用双向链表实现的队列,队列的最大的容量为缓存的大小。在使用的过程中,把最近使用的页面移动到队列首,最近没有使用的页面将被放在队列尾的位置。
(2)使用一个哈希表,把页号作为键,把缓存在队列中的结点的地址作为值。
当引用一个页面时,所需的页面在内存中,我们需要把这个页对应的结点移动到队列的前面。如果所需的页面不在内存中,我们将它存储在内存中。简单地说,就是将一个新结点添加到队列的前面,并在哈希表中更新相应的结点地址。如果队列是满的,那么就从队列尾部移除一个结点,并将新结点添加到队列的前面。实现代码如下:
package main
//Queue和Set都直接实现,Set实现了线程安全,Queue不是安全的线程
import(
."github.com/isdamir/gotype" //引入定义的数据结构
"fmt"
)
typeLRUstruct{
cacheSize int
queue *SliceQueue
hashSet *Set
}
//判断缓存队列是否已满
func(p*LRU)IsQueueFull()bool{
return p.queue.Size()==p.cacheSize
}
//把页号为pageNum的页也缓存到队列中,同时也添加到Hash表中
func(p*LRU)EnQueue(pageNum int){
//如果队列满了,需要删除队尾的缓存的页
if p.IsQueueFull(){
p.hashSet.Remove(p.queue.PopBack())
}
p.queue.EnQueueFirst(pageNurn)
//把新缓存的结点同时添加到hash表中
p.hashSet.Add(pageNum)
}
//当访问某一个page的时候会调用这个函数,对于访问的page有两种情况:
//1.如果page在缓存队列中,直接把这个结点移动到队首
//2.如果page不在缓存队列中,把这个page缓存到队首
func(p*LRU)AccessPage(pageNum int){
//page不在缓存队列中,把它缓存到队首
if !p.hashSet.Contains(pageNurn){
p.EnQueue(pageNum)
}elseif pageNum!=p.queue.GetFront(){ //page已经在缓存队列中了,移动到队首
p.queue.Remove(pageNum)
p.queue.EnQueueFirst(pageNum)
}
}
func(p*LRU)PrintQueue(){
for !p.queue.IsEmpty(){
fmt.Print(p.queue.DeQueue(), "")
}
fmt.Println()
}
func main(){
//假设缓存大小为3
lru:=&LRU{cacheSize:3, queue:NewSliceQueue(), hashSet:NewSet()}
lru.AccessPage(1)
lru.AccessPage(2)
lru.AccessPage(5)
lru.AccessPage(1)
lru.AccessPage(6)
lru.AccessPage(7)
//通过上面的访问序列后,缓存的信息为
lru.PrintQueue()
}
程序运行结果为:
7 6 1
[考点] 如何实现LRU缓存方案
4. 题目描述:
给定一趟旅途旅程中所有的车票信息,根据这个车票信息找出这趟旅程的路线。例如:给定下面的车票:(“西安”到“成都”),(“北京”到“上海”),(“大连”到“西安”),(“上海”到“大连”)。那么可以得到旅程路线为:北京->上海,上海->大连,大连->西安,西安->成都。假定给定的车票不会有环,也就是说有一个城市只作为终点而不会作为起点。
对于这种题目,一般而言可以使用拓扑排序进行解答。根据车票信息构建一个图,然后找出这张图的拓扑排序序列,这个序列就是旅程的路线。但这种方法的效率不高,它的时间复杂度为O(n)。这里重点介绍另外一种更加简单的方法:hash法。主要的思路为根据车票信息构建一个map,然后从这个map中找到整个旅程的起点,接着就可以从起点出发依次找到下一站,进而知道终点。具体的实现思路为:
(1)根据车票的出发地与目的地构建map。
Tickets={(“西安”到“成都”),(“北京”到“上海”),(“大连”到“西安”),(“上海”到“大连”)}
(2)构建Tickets的逆向map如下(将旅程的起始点反向):
ReverseTickets={(“成都”到“西安”),(“上海”到“北京”),(“西安”到“大连”),(“大连”到“上海”)}
(3)遍历Tickets,对于遍历到的key值,判断这个值是否在ReverseTickets中的key中存在,如果不存在,那么说明遍历到的Tickets中的key值就是旅途的起点。例如:“北京”在ReverseTickets的key中不存在,因此“北京”就是旅途的起点。实现代码如下:
package main
import(
"fmt"
)
func PrintResult(input map[string]string){
//用来存储把input的键与值调换后的信息
reverseInput:=map[string]string{}
fork, v:=range input{
reverseInput[v]=k
}
//找到起点
start:=""
fork,_:=range input{
if_, ok:=reverseInput[k]; lok{
start=k
break
}
}
if start==""{
fmt.Println("输入不合理")
}else{
//从起点出发按照顺序遍历路径
to:=input[start]
fmt.Print(start, "->", to)
to=input[to]
for to!=""{
fmt.Print(",",start,"->",to)
start=to
to=input[to]
}
fmt.Println()
}
}
func main(){
input:=map[string]string{"西安":"成都", "北京":"上海", "大连":"西安", "上海:"大连", }
PrintResult(input)
}
程序的运行结果为
北京->上海,上海->大连,大连->西安,西安->成都
算法性能分析:
这种方法的时间复杂度为O(n),空间复杂度也为O(n)。
[考点] 如何从给定的车票中找出旅程路线
5. 题目描述:
给定一个数组,找出数组中是否有两个数对(a,b)和(c,d),使得a+b=c+d,其中,a、b、c和d是不同的元素。如果有多个答案,打印任意一个即可。例如给定数组:{3,4,7,10,20,9,8},可以找到两个数对(3,8)和(4,7),使得3+8=4+7。
最简单的方法就是使用四重遍历,对所有可能的数对判断是否满足题目要求,如果满足则打印出来,但是这种方法的时间复杂度为O(n4),很显然不满足要求。下面介绍另外一种方法——hash法,算法的主要思路为:以数对为单位进行遍历,在遍历过程中,把数对和数对的值存储在哈希表中(键为数对的和,值为数对),当遍历到一个键值对,如果它的和在哈希表中已经存在,那么就找到了满足条件的键值对。下面使用Map为例给出实现代码:
package main
import(
"fmt "
)
typePairstmct{
first int
second int
}
func FindPairs(arr[]int)bool{
//键为数对的和,值为数对
sumPair:=map[int]*Pait{}
n:=len(arr)
//遍历数组中所有可能的数对
fori:=0; i<n; i++{
forj:=i+1; j<n; j++{
//如果这个数对的和在map中没有,则放入map中
sum:=arr[i]+arr[j]
if_, ok:=sumPair[sum]; !ok{
sumPair[sum]=&Pair{i, j}
}else{//map中已经存在与sum相同的数对了,找出来并打印出来
//找出已经遍历过的并存储在map中和为sum的数对
p:=sumPair[sum]
fmt.Printf("(%v, %v), (%v, %v)”, arr[p.first], arr[p.second], arr[i], arr[j])
fmt.Println()
return true
}
}
}
returnfalse
}
func main(){
arr:=[]int{3, 4, 7, 10, 20, 9, 8}
FindPairs(arr)
}
程序的运行结果为
(3, 8), (4, 7)
算法性能分析:
这种方法的时间复杂度为O(n2)。因为使用了双重循环,而Map的插入与查找操作实际的时间复杂度为O(1)。
[考点] 如何从数组中找出满足a+b=c+d的两个数对