加一个链表:函数式方法

Question

一直在研究这个leetcode问题。我想知道是否有一种可行的方法来解决这个问题。我所能想到的就是使用可变对象(在Scala中)。

给定一个表示为数字链表的非负整数，该整数加1。

存储这些数字，使得最高有效数字位于列表的头部。

示例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]

Answer 1

(尾巴)递归拯救！

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)

您可以看到运行here的代码。

Answer 2

这里有一种方法：

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)
}

请注意，不是将ListNode元素转换为对于大型ListNodes可能有问题的数字，而是使用fold来执行迭代的元素求和。

测试代码：

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)

Answer 3

不是非常有效的解决方案，但肯定是最短的：

(List(1,2,3).mkString.toInt + 1).toString.toList.map(_.asDigit)

在Scastie上运行的代码

在Scala2.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上运行的代码。