ARTS(11)

1 Algorithm

既然要求在$O(1)$时间完成，所有的查询工作必须要求由 map 完成，还包含了增删的操作，所以必须采用 double link 存储相关数据。

type Element struct {
    key   string
    count int
    prev  *Element
    next  *Element
}

type Group struct {
    head *Element
    tail *Element
    prev *Group
    next *Group
}

func NewGroup() *Group {
    g := &Group{
        head: ∈{},
        tail: ∈{},
    }
    g.head.next = g.tail
    g.tail.prev = g.head
    return g
}

func (g *Group) Front() *Element {
    return g.head.next
}

func (g *Group) Back() *Element {
    return g.tail.prev
}

func (g *Group) Empty() bool {
    return g.head.next == g.tail && g.tail.prev == g.head
}

func (g *Group) Remove(e *Element) {
    prev, next := e.prev, e.next
    prev.next = next
    next.prev = prev
}

func (g *Group) Push(e *Element){
    e.prev = g.tail.prev
    e.prev.next = e
    e.next = g.tail
    g.tail.prev = e
}

func (g *Group) Count() int {
    if g.Empty() {
        return -1
    }
    return g.Front().count
}

func (g *Group) ConnectBack(gg *Group) {
    gg.next = g.next
    gg.next.prev = gg
    gg.prev = g
    g.next = gg
}

func (g *Group) ConnectForward(gg *Group) {
    gg.prev = g.prev
    gg.prev.next = gg
    gg.next = g
    g.prev = gg
}

func (g *Group) Destroy() {
    g.head = nil
    g.tail = nil
    g = nil
}

type List struct {
    head *Group
    tail *Group
}

func NewList() *List {
    l := &List{
        head: NewGroup(),
        tail: NewGroup(),
    }
    l.head.next = l.tail
    l.tail.prev = l.head
    return l
}

func (l *List) Front() *Group {
    return l.head.next
}

func (l *List) Back() *Group {
    return l.tail.prev
}

func (l *List) Remove(g *Group) {
    prev, next := g.prev, g.next
    prev.next = next
    next.prev = prev
}

func (l *List) IsLast(g *Group) bool {
    return g.next == l.tail
}

func (l *List) IsFirst(g *Group) bool {
    return g.prev == l.head
}

func (l *List) Empty() bool {
    return l.head.next == l.tail && l.tail.prev == l.head
}

func (l *List) PushFront(g *Group) {
    l.head.ConnectBack(g)
}

func (l *List) PushBack(g *Group) {
    l.tail.ConnectForward(g)
}


type AllOne struct {
    l            *List
    elementTable map[string]*Element
    groupTable   map[string]*Group
}

/** Initialize your data structure here. */
func Constructor() AllOne {
    return AllOne{
        l:            NewList(),
        elementTable: make(map[string]*Element, 0),
        groupTable:   make(map[string]*Group, 0),
    }
}

func (this *AllOne) Empty() bool {
    return this.l.Empty()
}

func (this *AllOne) Inc(key string) {
    if e, ok := this.elementTable[key]; ok {
        e.count++
        // hit key
        g := this.groupTable[key]
        g.Remove(e)
        nextGroup := g.next
        if nextGroup.Count() != e.count {
            nextGroup = NewGroup()
            g.ConnectBack(nextGroup)
        }
        this.groupTable[key] = nextGroup
        nextGroup.Push(e)
        if g.Empty() {
            this.l.Remove(g)
            g.Destroy()
        }
    } else {
        // not hit key
        e = ∈{
            key:   key,
            count: 1,
        }
        this.elementTable[key] = e
        nextGroup := this.l.Front()
        if nextGroup.Count() != e.count {
            nextGroup = NewGroup()
            this.l.head.ConnectBack(nextGroup)
        }
        this.groupTable[key] = nextGroup
        nextGroup.Push(e)
    }

}

/** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
func (this *AllOne) Dec(key string) {
    e, ok := this.elementTable[key]
    if ok{
        e.count --
        g := this.groupTable[key]
        delete(this.groupTable, key)
        g.Remove(e)
        if e.count == 0 {
            delete(this.elementTable, key)
        }else{
            prevGroup := g.prev
            if prevGroup.Count() != e.count {
                prevGroup = NewGroup()
                g.ConnectForward(prevGroup)
            }
            this.groupTable[key] = prevGroup
            prevGroup.Push(e)
        }
        if g.Empty(){
            this.l.Remove(g)
            g.Destroy()
        }
    }
}

/** Returns one of the keys with maximal value. */
func (this *AllOne) GetMaxKey() string {
    if this.l.Empty() {
        return ""
    }else{
        return this.l.Back().Back().key
    }

}

/** Returns one of the keys with Minimal value. */
func (this *AllOne) GetMinKey() string {
    if this.l.Empty(){
        return ""
    }else{
        return this.l.Front().Front().key
    }
}

2 Review

2.1 为什么每个人都如此匆忙

• 自学：在24小时内你不可能有时间编写有意义的程序，也不能从成功和失败中获取任何教训。你不会有时间从有经验的 程序员 学到经验，也不能理解如何在C++环境中活下来。简而言之，你不能从中学到任何东西。所以这本书能讨论的仅仅是表面的东西，而不是深层次的理解。正如 Alexander Pope 所说: 学一点点是非常危险的事情。
• C++：在24小时内，如果你有其他语言的基础，你可能学会C++的语法，但是你还是不能学会如何使用这个语言。换句话说，如果你是一个基础的程序员，你可能学会使用C++基础的语法编写程序，但是你不能学会C++到底哪方面是好的。哪有怎样呢？ Alan Perlis 曾经说过：如果一个语言不能影响编程的思维方式，它就是不值得学习的。可能一点就是你必须C++的皮毛（而且跟 Javascript 和 Processing 一样)，因为你需要现有的 工具 来完成特定的任务。所以你根本不是学习如何编程，而是学会去完成一个任务。
• 24小时：不幸的是，这还不够，在下一小节继续讨论。

2.2 10年自学编程

2.3 想成为程序员

想要在程序领域成功，下面是我的清单：

• 对编程感兴趣，是为了兴趣而做。确保它能使你感到快乐，这样才能你愿意在上面花10年或者10000小时；
• 编程：学习最好的方法是在学习中做。专业点来讲就是：对每个个体而言，特定领域的最高的层次的表示不是该层次的经验，而是每个个体通过刻意练习而能够提高。最有效的学习的方式是一个好的任务，而这个任务可以通过适当的难度而完成。有意义的正反馈和有机会不停的反复和错误纠正。
• 和其他程序员交流，阅读它们的代码，这个比任何书籍或者训练课程有效果。
• 如果你愿意，将它放在大学的四年。它能够帮你获取那些需要技能的工作机会，它能帮你更加理解这个领域。如果你不喜欢学校，你可以从你的工作中获取相同的精力。在任何情况下，从书本中学习远远不够的。计算机科学教育不可能让任何人变成出色的程序员，就像只学习画刷和色素不会成为出色的画家。
• 和其他程序员工作一个项目，在一些项目上成为出色的程序员，在其他项目中成为最差的。成为最棒的程序员可以测试你领导一个项目的能力，也可以帮助其他人；如果你是最差的，你可以学到如何去掌握它们，去学习他们不愿意做的。
• 在其他程序员之后的一个项目，理解其他人编写的项目。看看理解它们需要什么并且如果之前程序员没有考虑的内容去修复它们。考虑如何去设计你的程序来变得更加容易维护。
• 学习一系列编程语言。主要有一个语言能够强化面向对象抽象（比如 java 和C++）；一个能强化函数抽象（比如Lisp,ML或者Haskell）；一个能支持语言抽象（Lisp);一个支持声明规范（比如Prolog 和 C++ 模板）；一个强化并发的（比如Clojure和Go)。
• 记住在计算机科学中有个 计算机 三个字，知道计算机在执行一个指令的消耗的时间；从内存中获取一个字花费的时间（缓存命中和不命中）；从磁盘中获取一系列字节；从磁盘新的位置获取数据。
• 理解一个语言标准；它可以是 ANSI C++ 委员会；也可以是你的代码是否用2个或者4个空格缩进；去了解其他门喜欢这门语言的什么，以及为什么喜欢；
• 对偏离语言标准化的代码有很快的直觉感受。

1. 尽早地识别出顶级设计师；
2. 分配一个人作为其职业规划导师；
3. 给与机遇让成长中的设计师互相磨砺；

3 Tips

3.1 执行操作所需的时间

4 Share