go - 如何使用不同的数据结构递归循环 map

Question

我正在尝试找出在 Go 中递归遍历 [string]int 映射的最佳方法。我正在构建一个涉及多个国家的游戏，并最终由两人一组组成。

目标是将“得分”最低的前两个国家匹配到自己的一组中，并将其添加回集合中，从而为新 map 提供这些国家得分的总值。

然后递归地对所有组执行此操作，最后得到一组和一个总值。

例如，如果您有:

score := map[string]int{
        "Canada": 7,
        "US": 2,
        "Germany": 3,
        "Korea": 4,
}

group1 = {[US:2] [Germany:3]} 共有 5

group1 现在将以“分数”5 放回初始集合中，因为它获得了两个最低分数。我们现在有:

score := map[string]int{
        "Canada": 7,
        "Korea": 4,
        group1: `US:2 Germany:3` with a total of 5
}

如果这是集合中的最低分数，则下一次迭代将是:

group2 = {[韩国:4] [group1:5]}

 score := map[string]int{
            "Canada": 7,
            group2: `Korea:4 group1:5` with a total of 9
  }

依此类推，直到剩下一个..我认为基本结构应该是这样的。但是，我不确定执行此操作的正确方法，因为数据结构现在包含一个 [string]int 映射以及这个新映射。

我意识到这不是一个普遍的问题，但是可以为此使用接口(interface)吗？我是 Go 的新手，所以建议会很有帮助。

这里有一个例子来进一步说明我的意思: https://play.golang.org/p/cnkTc0HBY4

Answer 1

使用 heap data structure 可以“轻松”解决您的问题.

package main

import (
    "container/heap"
    "fmt"
)



// Something that has a score
type Scoreable interface {
    fmt.Stringer
    Score() int
}



// A country has a name and a score
type Country struct {
    name  string
    score int
}

// Country implements Scoreable
func (c Country) Score() int {
    return c.score
}

// ... and fmt.Stringer
func (c Country) String() string {
    return fmt.Sprintf("%s [%d]", c.name, c.score)
}



// A team consists of two Scoreable's and has itself a score
type Team struct {
    team1, team2 Scoreable
    score        int
}

// Team implements Scoreable
func (t Team) Score() int {
    return t.score
}

// ... and fmt.Stringer
func (t Team) String() string {
    return fmt.Sprintf("(%s + %s)", t.team1.String(), t.team2.String())
}



// The heap will be implemented using a slice of Scoreables
type TeamHeap []Scoreable

// TeamHeap implements heap.Interface
func (th TeamHeap) Len() int {
    return len(th)
}

func (th TeamHeap) Less(i, j int) bool {
    return th[i].Score() < th[j].Score()
}

func (th TeamHeap) Swap(i, j int) {
    th[i], th[j] = th[j], th[i]
}

func (th *TeamHeap) Push(t interface{}) {
    *th = append(*th, t.(Scoreable))
}

func (th *TeamHeap) Pop() interface{} {
    old := *th
    n := len(old)
    t := old[n-1]
    *th = old[0 : n-1]
    return t
}


// The main function
func main() {

    // Create a heap and initialize it
    teams := &TeamHeap{}
    heap.Init(teams)

    // Push the countries (NB: heap.Push(), not teams.Push())
    heap.Push(teams, Country{"Canada", 7})
    heap.Push(teams, Country{"US", 2})
    heap.Push(teams, Country{"Germany", 3})
    heap.Push(teams, Country{"Korea", 4})

    // Take the two teams with lowest score and make a new team of them
    // Repeat this until there's only one team left
    for teams.Len() > 1 {
        t1 := heap.Pop(teams).(Scoreable)
        t2 := heap.Pop(teams).(Scoreable)
        heap.Push(teams, Team{t1, t2, t1.Score() + t2.Score()})
    }

    // Print the teams that we now have in the heap
    for teams.Len() > 0 {
        t := heap.Pop(teams).(Team)
        fmt.Println(t)
    }
}

你可以找到runnable code在 Go Playground 上。