我一直在思考这个leetcode问题。想知道是否有一种功能性的方法来处理这个问题。我所能想到的就是使用可变对象(在Scala中(。
给定一个表示为数字链表的非负整数，加上整数的一。
存储这些数字时，最高有效数字位于列表的开头。
示例1:
输入：head=[1,2,3]输出：[1,2,4]
示例2:
输入：head=[0]输出：[1]
限制条件：
链表中的节点数在[1, 100]的范围内。
0 <= Node.val <= 9
链表表示的数字除零本身外，不包含前导零。
* Definition for singly-linked list.
* class ListNode(_x: Int = 0, _next: ListNode = null) {
* var next: ListNode = _next
* var x: Int = _x
* }
*/
object Solution {
def plusOne(head: ListNode): ListNode = {
}
}
更有趣的输入/输出=[1,9,9,9,9] => [2,0,0,0,0]
(tail(递归救援！
type Digit = Int // Refined [1..9]
type Number = List[Digit]
def plusOne(number: Number): Number = {
def sumDigits(d1: Digit, d2: Digit): (Digit, Digit) = {
val r = d1 + d2
(r % 10) -> (r / 10)
}
@annotation.tailrec
def loop(remaining: Number, remainder: Digit, acc: Number): Number =
remaining match {
case digit :: digits =>
val (result, newRemainder) = sumDigits(digit, remainder)
loop(remaining = digits, newRemainder, result :: acc)
case Nil =>
if (remainder != 0) remainder :: acc
else acc
}
loop(remaining = number.reverse, remainder = 1, acc = List.empty)
}
你可以这样使用：
plusOne(List(1, 2, 3))
// res: Number = List(1, 2, 4)
您可以在此处看到运行的代码。
这里有一种方法：
class ListNode(_x: Int = 0, _next: ListNode = null) {
var next: ListNode = _next
var x: Int = _x
}
def toNode(l: List[Int]): ListNode = {
l.foldRight[ListNode](null)((x, acc) => new ListNode(x, acc))
}
def toList(node: ListNode): List[Int] =
Iterator.iterate(node)(_.next).takeWhile(_ != null).map(_.x).toList
def plusOne(head: ListNode): ListNode = {
val l0 = toList(head)
val l1 = List(1)
val res = l0.reverse.zipAll(l1, 0, 0).foldLeft((List.empty[Int], 0)){
case ((acc, c), (x0, x1)) =>
val s = x0 + x1 + c
if (s >= 10) (s-10 :: acc, 1) else (s :: acc, 0)
}
toNode(if (res._2 == 0) res._1 else 1 :: res._1)
}
请注意，fold不是将ListNode元素转换为可能对大型ListNode有问题的数字，而是用于执行迭代元素求和。
测试代码：
toList( plusOne( toNode(List(0)) ) )
// res0: List[Int] = List(1)
toList( plusOne( toNode(List(1, 2, 3)) ) )
// res1: List[Int] = List(1, 2, 4)
toList( plusOne( toNode(List(2, 9, 9)) ) )
// res2: List[Int] = List(3, 0, 0)
toList( plusOne( toNode(List(9, 9, 9)) ) )
// res3: List[Int] = List(1, 0, 0, 0)
不是很有效的解决方案，但肯定是最短的：
(List(1,2,3).mkString.toInt + 1).toString.toList.map(_.asDigit)
Scastie 代码运行
在Scala 2.13中，您可以使用List.unfold:
def increaseLast(list: List[Int]): List[Int] = List.unfold(list) {
case Nil =>
None
case x :: Nil =>
Some((x + 1) % 10, Nil)
case x :: xs if xs.forall(_ == 9) =>
Some((x + 1) % 10, xs)
case x :: xs =>
Some(x, xs)
}
代码在Scastie运行。