dongzhang0418
dongzhang0418
2017-08-30 15:11

如何使用不同的数据结构递归遍历地图

已采纳

I'm trying to figure out the best way to recursively go through a [string]int map in Go. I'm building a game in which multiple countries are involved, and grouped together by teams of two in the end.

The goal is to match the first two countries with the lowest 'score' into its own group of two, and add it back to the collection giving the new map a total value of the scores of those countries.

Then recursively doing that to all the groups, ending up with one group and one total value in the end.

For example, if you had:

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

group1 = {[US:2] [Germany:3]} with a total of 5

group1 would now be put back into the initial collection with a 'score' of 5 since it takes the two lowest scores. We would now have:

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

If this was now the lowest score in the collection, the next iteration would be:

group2 = {[Korea:4] [group1:5]}

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

And so on until you're left with one.. I think the basic structure should be something like this. However, I'm unsure of the proper way to do this since the data structure is now encompassing a [string]int map, as well as this new map.

I realize this is not such a generic question, but could an interface be used for this? I'm very new to Go, so advice would be helpful.

Here is an example to further illustrate what I mean: https://play.golang.org/p/cnkTc0HBY4

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

3条回答

  • duanlu9816 duanlu9816 4年前

    Your problem can "easy" be solved using a 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)
        }
    }
    

    You can find runnable code on the Go Playground.

    点赞 评论 复制链接分享
  • dtcu5885 dtcu5885 4年前

    You can try map[string]interface{} with Type assertion。 Here is the demo

    package main
    
    import "fmt"
    
    const total = "total"
    
    
    func GetValue(i interface{}) int {
        value, ok := i.(int)
        if ok {
            return value
        }
        return i.(map[string]interface{})[total].(int)
    }
    
    func main() {
        score := map[string]interface{}{
            "Canada":  7,
            "US":      2,
            "Germany": 3,
            "Korea":   4,
        }
        groupCount := 0
    
        for len(score) > 2 {
            var (
                firstMin  = math.MaxInt32
                secondMin = math.MaxInt32
                firstKey  = ""
                secondKey = ""
            )
            for k, v := range score {
                iv := GetValue(v)
                if iv < firstMin {
                    secondMin = firstMin
                    secondKey = firstKey
                    firstMin = iv
                    firstKey = k
                    continue
                }
                if iv < secondMin {
                    secondMin = iv
                    secondKey = k
                    continue
                }
    
            }
            groupCount++
    
            score[fmt.Sprintf("Group%d", groupCount)] = map[string]interface{}{
                firstKey:  score[firstKey],
                secondKey: score[secondKey],
                total:     GetValue(score[firstKey])+ GetValue(score[secondKey]),
            }
            delete(score, firstKey)
            delete(score, secondKey)
        }
        fmt.Println(score)
    }
    

    Here is the link https://play.golang.org/p/qq5qwAsh1m

    点赞 评论 复制链接分享
  • duan41497 duan41497 4年前
    package main
    
    import (
        "container/heap"
        "fmt"
    )
    
    //Recursive data structure may looks something like
    type Group struct {
        Score   int
        Left    *Group
        Right   *Group
        Country string
    }
    
    //You can use slice to hold them organized in tree
    type GrHeap []Group
    
    //To implement your logic you can use stdlib/container/heap Heap interface
    //you must implement Heap interface for your slice
    func (h GrHeap) Len() int           { return len(h) }
    func (h GrHeap) Less(i, j int) bool { return h[i].Score < h[j].Score }
    func (h GrHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
    
    func (h *GrHeap) Push(x interface{}) {
        // Push and Pop use pointer receivers because they modify the slice's length,
        // not just its contents.
        *h = append(*h, x.(Group))
    }
    
    func (h *GrHeap) Pop() interface{} {
        old := *h
        n := len(old)
        x := old[n-1]
        *h = old[0 : n-1]
        return x
    }
    
    func main() {
        //you most likely already have a map
        //anyway it will be handy to keep it for convenient access to individual country
        score := map[string]int{
            "Canada":  7,
            "US":      2,
            "Germany": 3,
            "Korea":   4,
        }
        //here we allocate heap
        gr := make(GrHeap, 0)
        //populate it from map
        for k, v := range score {
            g := Group{v, nil, nil, k}
            gr = append(gr, g)
        }
        //and initialize
        heap.Init(&gr)
        //and here we use heap magic to implement your logic
        for len(gr) > 2 {
            l := heap.Pop(&gr).(Group)
            r := heap.Pop(&gr).(Group)
            ng := Group{l.Score + r.Score, &l, &r, ""}
            heap.Push(&gr, ng)
        }
        fmt.Println(gr)
        fmt.Println(gr[1].Left)
        fmt.Println(gr[1].Right.Left)
    //and you can see it works https://play.golang.org/p/gugJxJb7rr
    }
    
    点赞 评论 复制链接分享

相关推荐