2021-06-20:已知一个消息流会不断地吐出整数 1~N,但不一定按照顺序依次吐出。如果上次打印的序号为i, 那么当i+1出现时,请打印 i+1 及其之后接收过的并且连续的所有数,直到1~N全部接

2021-06-20:已知一个消息流会不断地吐出整数 1~N,但不一定按照顺序依次吐出。如果上次打印的序号为i, 那么当i+1出现时,请打印 i+1 及其之后接收过的并且连续的所有数,直到1~N全部接收并打印完。请设计这种接收并打印的结构。

福大大 答案2021-06-20:

头map,尾map,单链表。
时间不够,请直接看代码。

代码用golang编写。代码如下:

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()
}

执行结果如下:
2021-06-20:已知一个消息流会不断地吐出整数 1~N,但不一定按照顺序依次吐出。如果上次打印的序号为i, 那么当i+1出现时,请打印 i+1 及其之后接收过的并且连续的所有数,直到1~N全部接


左神java代码

上一篇:Gitlab\Git总结


下一篇:nginx 配置http,https,ip