如何加速这个Scala解决方案来解决Leetcode问题？

mwngjboj 于 2023-03-18 发布在 Scala

关注(0)|答案(2)|浏览(161)

我在Scala中解决了简单的Leetcode问题Ransom Note，如下所示：

def canConstruct(ransomNote: String, magazine: String): Boolean = {
    val magazineChars = magazine.toSeq.groupBy(identity).mapValues(_.size)
    val ransomChars = ransomNote.toSeq.groupBy(identity).mapValues(_.size)
    ransomChars.forall { case (c, num) => magazineChars.getOrElse(c, 0) >= num }
  }

这个解决方案还可以，但是比Scala中其他公认的解决方案要慢。
现在我想知道如何加快速度。你会建议如何优化这个解决方案？

scala

来源：https://stackoverflow.com/questions/75211334/how-to-speed-up-this-scala-solution-for-a-leetcode-problem

2条答案

按热度按时间

hgncfbus1#

出于性能考虑，您应使用低级数据结构（primitive type代替object type，array of primitive type代替List, Map，即）和低级语法（while代替foreach loop，即）
这是我的解决方案，击败90% ~ 100%（它是随机的），你可以通过替换foreach到while loop和替换forall到while loop太快，但它太繁琐：

赞(0）回复(0）举报 2023-03-18

2nbm6dog2#

上述解决方案的略微优化版本：

def canConstruct(ransomNote: String, magazine: String): Boolean = {
    if (magazine.length < ransomNote.length) {
      false // if the magazine has fewer letters than the ransom note, then we definitely can't make the note
    } else {
      var i = 0
      val counts = Array.ofDim[Int](26)
      while (i < magazine.length) {
        counts(magazine(i) - 'a') += 1
        if (i < ransomNote.length) counts(ransomNote(i) - 'a') -= 1 // avoid the need for another loop for the ransom note letters
        i += 1
      }

      var c = 0;
      while (c < counts.length) {
        if (counts(c) < 0) {
          return false
        }
        c += 1
      }

      true
    }
  }

结果如下（运行几次后）：

赞(0）回复(0）举报 2023-03-18

我来回答

如何加速这个Scala解决方案来解决Leetcode问题？

2条答案

相关问题

热门标签

最新问答