在Golang中解决Hackerrank的Climbing The Leaderboard问题

huangapple go评论82阅读模式
英文:

Climbing The Leaderboard Hackerrank Solutions in Golang

问题

线索:

一个街机游戏玩家想要爬到排行榜的顶部并追踪他们的排名。游戏使用密集排名,所以排行榜的工作方式如下:

  1. 得分最高的玩家在排行榜上排名第1。
  2. 得分相同的玩家获得相同的排名号码,下一个玩家获得紧随其后的排名号码。

这是我用于爬榜的代码解决方案,通过了8个测试用例,但有4个用例超时。有没有办法提高代码的性能?

func contains(s []int32, e int32) bool {
    for _, a := range s {
        if a == e {
            return true
        }
    }
    return false
}

func remove(slice []int32, s int) []int32 {
    return append(slice[:s], slice[s+1:]...)
}

func climbingLeaderboard(ranked []int32, player []int32) []int32 {
    // 在这里编写你的代码
    for i := 0; i < len(ranked); i++ {
        if contains(ranked[i+1:], ranked[i]) {
            ranked = remove(ranked, i)
            i--
        }
    }
    sort.Slice(ranked, func(i, j int) bool { return ranked[i] < ranked[j] })
    var result = make([]int32, len(player))

    if len(ranked) == 1 {
        for i := 0; i < len(player); i++ {
            if player[i] > ranked[0] {
                result[i] = 1
            } else if player[0] == ranked[0] {
                result[i] = 1
            } else if player[0] < ranked[0] {
                result[i] = 2
            }
        }
    } else {
        for i := 0; i < len(player); i++ {
            l := len(ranked)
            l32 := int32(l)
            p := player[i]
            var temp int32
            for j := 1; j < l; j++ {
                if p > ranked[j] {
                    temp = 1
                } else if p > ranked[j-1] && p < ranked[j] {
                    temp = l32 - int32(j) + 1
                    break
                } else if p == ranked[j-1] {
                    temp = l32 - int32(j) + 1
                    break
                } else if p < ranked[j-1] {
                    temp = l32 + 1
                    break
                }
            }
            result[i] = temp
            temp = 0
        }
    }
    return result
}

请注意,这只是代码的翻译部分,不包括回答你的问题。

英文:

Clue :

An arcade game player wants to climb to the top of the leaderboard and track their ranking. The game uses Dense Ranking, so its leaderboard works like this:

  1. The player with the highest score is ranked number 1 on the leaderboard.
  2. Players who have equal scores receive the same ranking number, and the next player(s) receive the immediately following ranking number.

This is my code solution for climbing the leaderboard, 8/12 test case is passed. but 4 case is timeout. any solution for boosting the performance of my code?

func contains(s []int32, e int32) bool {
for _, a := range s {
if a == e {
return true
}
}
return false
}
func remove(slice []int32, s int) []int32 {
return append(slice[:s], slice[s+1:]...)
}
func climbingLeaderboard(ranked []int32, player []int32) []int32 {
// Write your code here
for i := 0; i &lt; len(ranked); i++ {
if contains(ranked[i+1:], ranked[i]) {
ranked = remove(ranked, i)
i--
}
}
sort.Slice(ranked, func(i, j int) bool { return ranked[i] &lt; ranked[j] })
var result = make([]int32, len(player))
if len(ranked) == 1 {
for i := 0; i &lt; len(player); i++ {
if player[i] &gt; ranked[0] {
result[i] = 1
} else if player[0] == ranked[0] {
result[i] = 1
} else if player[0] &lt; ranked[0] {
result[i] = 2
}
}
} else {
for i := 0; i &lt; len(player); i++ {
l := len(ranked)
l32 := int32(l)
p := player[i]
var temp int32
for j := 1; j &lt; l; j++ {
if p &gt; ranked[j] {
temp = 1
} else if p &gt; ranked[j-1] &amp;&amp; p &lt; ranked[j] {
temp = l32 - int32(j) + 1
break
} else if p == ranked[j-1] {
temp = l32 - int32(j) + 1
break
} else if p &lt; ranked[j-1] {
temp = l32 + 1
break
}
}
result[i] = temp
temp = 0
}
}
return result
}

答案1

得分: 1

你的代码在去重ranked的部分效率很低。

func contains(s []int32, e int32) bool {
    for _, a := range s {
        if a == e {
            return true
        }
    }
    return false
}

func remove(slice []int32, s int) []int32 {
    return append(slice[:s], slice[s+1:]...)
}

for i := 0; i < len(ranked); i++ {
    if contains(ranked[i+1:], ranked[i]) {
        ranked = remove(ranked, i)
        i--
    }
}
sort.Slice(ranked, func(i, j int) bool { return ranked[i] < ranked[j] })

你用于搜索玩家游戏排名的代码也不够高效。

效率不仅仅取决于你的操作,还取决于你执行操作的次数。

你的代码过于复杂。


以下是一段简单的代码,可以解决这个问题而不会触发超时。

import (
    "sort"
)

func climbingLeaderboard(ranked []int32, player []int32) []int32 {
    ranks := ranked[:1]
    last := ranks[0]
    for _, score := range ranked[1:] {
        if score != last {
            ranks = append(ranks, score)
        }
        last = score
    }

    climb := make([]int32, 0, len(player))
    for _, score := range player {
        rank := sort.Search(
            len(ranks),
            func(i int) bool { return ranks[i] <= score },
        )
        climb = append(climb, int32(rank+1))
    }
    return climb
}
英文:

Your code to dedupe ranked is very inefficient.

func contains(s []int32, e int32) bool {
for _, a := range s {
if a == e {
return true
}
}
return false
}
func remove(slice []int32, s int) []int32 {
return append(slice[:s], slice[s+1:]...)
}
for i := 0; i &lt; len(ranked); i++ {
if contains(ranked[i+1:], ranked[i]) {
ranked = remove(ranked, i)
i--
}
}
sort.Slice(ranked, func(i, j int) bool { return ranked[i] &lt; ranked[j] })

Your code to search for player game ranks is not efficient.

Efficiency is not just what you do, it's also how many times you do it.

Your code is too complicated.


Here is some simple code that solves the challenge without triggering a timeout.

import (
&quot;sort&quot;
)
func climbingLeaderboard(ranked []int32, player []int32) []int32 {
ranks := ranked[:1]
last := ranks[0]
for _, score := range ranked[1:] {
if score != last {
ranks = append(ranks, score)
}
last = score
}
climb := make([]int32, 0, len(player))
for _, score := range player {
rank := sort.Search(
len(ranks),
func(i int) bool { return ranks[i] &lt;= score },
)
climb = append(climb, int32(rank+1))
}
return climb
}

huangapple
  • 本文由 发表于 2022年9月25日 00:48:47
  • 转载请务必保留本文链接:https://go.coder-hub.com/73838996.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定