时间戳

首页 > 解决方案 > 加一链表：函数式方法

scala - 加一链表：函数式方法

问题描述

一直在努力解决这个 leetcode 问题。想知道是否有一种实用的方法来解决这个问题。我能想到的就是使用可变对象（在 Scala 中）。

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

存储数字以使最高有效数字位于列表的开头。

示例 1：

输入：头 =[1,2,3] 输出：[1,2,4]

示例 2：

输入：头 =[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]

标签： scalafunctional-programming

解决方案

（尾）递归救援！

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)

您可以看到这里运行的代码。

推荐阅读