2021-06-20：已知一个消息流会不断地吐出整数 1~N，但不一定按照顺序依次吐出。如果上次打印的序号为i， 那么当i 1出现时，请打印 i 1 及其之后接收过的并且连续的所有数，直到1~N全部接收并打印完。请设计这种接收并打印的结构。
福大大 答案2021-06-20：
头map，尾map，单链表。
时间不够，请直接看代码。
代码用golang编写。代码如下：
代码语言：txt复制package main
import "fmt"
func main() {
// MessageBox only receive 1~N
box := NewMessageBox()
// 1....
fmt.Println("这是2来到的时候")
box.receive(2, "B") // - 2"
fmt.Println("这是1来到的时候")
box.receive(1, "A") // 1 2 -> print, trigger is 1
box.receive(4, "D") // - 4
box.receive(5, "E") // - 4 5
box.receive(7, "G") // - 4 5 - 7
box.receive(8, "H") // - 4 5 - 7 8
box.receive(6, "F") // - 4 5 6 7 8
box.receive(3, "C") // 3 4 5 6 7 8 -> print, trigger is 3
box.receive(9, "I") // 9 -> print, trigger is 9
box.receive(10, "J") // 10 -> print, trigger is 10
box.receive(12, "L") // - 12
box.receive(13, "M") // - 12 13
box.receive(11, "K") // 11 12 13 -> print, trigger is 11
}
type Node struct {
info string
next *Node
}
type MessageBox struct {
headMap map[int]*Node
tailMap map[int]*Node
waitPoint int
}
func NewMessageBox() *MessageBox {
ans := &MessageBox{}
ans.headMap = make(map[int]*Node)
ans.tailMap = make(map[int]*Node)
ans.waitPoint = 1
return ans
}
// 消息的编号，info消息的内容, 消息一定从1开始
func (this *MessageBox) receive(num int, info string) {
if num < 1 {
return
}
cur := &Node{info: info}
// num~num
this.headMap[num] = cur
this.tailMap[num] = cur
// 建立了num~num这个连续区间的头和尾
// 查询有没有某个连续区间以num-1结尾
if _, ok := this.tailMap[num-1]; ok {
this.tailMap[num-1].next = cur
delete(this.tailMap, num-1)
delete(this.headMap, num)
}
// 查询有没有某个连续区间以num 1开头的
if _, ok := this.headMap[num 1]; ok {
cur.next = this.headMap[num 1]
delete(this.tailMap, num)
delete(this.headMap, num 1)
}
if num == this.waitPoint {
this.print2()
}
}
func (this *MessageBox) print2() {
node := this.headMap[this.waitPoint]
delete(this.headMap, this.waitPoint)
for node != nil {
fmt.Print(node.info " ")
node = node.next
this.waitPoint
}
delete(this.tailMap, this.waitPoint-1)
fmt.Println()
}执行结果如下：
图片左神java代码
