scala - 以更不可变的方式解决此练习的更好方法是什么?
问题描述
我正在尝试解决 HackerRank 上的问题。我试图以更实用的方式解决这个问题(使用不变性)。我尝试了一个解决方案,但我对此并不完全有信心。
这是问题的链接:
我的可变解决方案是这样的:
/**
* Mutable solution
* MSet => mutable set is used
* val pairs => it is delclared var and getting reassigned
*/
import scala.annotation.tailrec
import scala.collection.mutable.{Set => MSet}
def sockMerchant2(n: Int, ar: Array[Int]): Int = {
val sockInventory : MSet[Int] = MSet.empty[Int]
var pairs = 0
ar.foreach { elem =>
if(sockInventory.contains(elem)) {
pairs = pairs + 1
sockInventory -= elem
} else sockInventory += elem
}
pairs
}
sockMerchant(5, Array(1,2,1,2,4,2,2))
相同解决方案的不可变版本:
/**
* Solution with tail recursion.
* Immutable Set is used. No variable is getting reassigned
* How it is getting handled internally ?
* In each iteration new states are assigned to same variables.
* @param n
* @param ar
* @return
*/
import scala.annotation.tailrec
def sockMerchant(n: Int, ar: Array[Int]): Int = {
@tailrec
def loop(arr: Array[Int], counter: Int, sockInventory: Set[Int]): Int ={
if(arr.isEmpty) counter
else if(sockInventory.contains(arr.head))
loop(arr.tail, counter +1, sockInventory-arr.head)
else loop(arr.tail, counter, sockInventory + arr.head)
}
loop(ar, 0, Set.empty)
}
sockMerchant(5, Array(1,2,1,2,4,2,2))
考虑到函数式编程原则,解决这个问题的理想方法是什么?
解决方案
第一种可能性是使用模式匹配:
def sockMerchant(n: Int, ar: Array[Int]): Int = {
@tailrec
def loop(list: List[Int], counter: Int, sockInventory: Set[Int]): Int =
list match {
case Nil =>
counter
case x::xs if sockInventory.contains(x) =>
loop(xs, counter +1, sockInventory-x)
case x::xs =>
loop(xs, counter, sockInventory + x)
}
loop(ar.toList, 0, Set.empty)
}
如果您将其更改Array
为 a List
,您将获得一个很好的可读解决方案。
一个更实用的解决方案是使用folding
:
def sockMerchant(n: Int, ar: Array[Int]): Int = {
ar.foldLeft((0, Set.empty[Int])){case ((counter, sockInventory), x: Int) =>
if (sockInventory.contains(x))
(counter +1, sockInventory-x)
else
(counter, sockInventory + x)
}._1
}
这有点难以阅读/理解 - 所以当我开始时,我更喜欢带有recursion
.
正如jwvh在其评论中所显示的那样——如果你不能用Scala在一行中做到这一点——你可能会错过一些东西;)。
推荐阅读
- java - Android View layoutInflater 通过字符串获取布局
- excel - VBA或公式在Excel中分隔街道名称和后缀?
- python - 为什么在 django 中返回 json 响应后值会改变
- python - 我可以在 kivy 2d gui 中预览终端 bash 输出吗
- r - R 对每个事件的每个主题进行最近的观察
- azure-devops - 在 Azure DevOps 的 Dropbox 中隐藏 Azure Boards
- python - 如何使用 rgba 值列表设置散点图中点的颜色?
- java - 通过 Java 反射 API 查找 Lombok getter/setter
- c++ - 如何制作一个重置while循环的函数?
- javascript - 带有 HTML *和*输入字段数据的 Javascript