gpt4 book ai didi

scala - 加一链表: Functional Approach

转载 作者:行者123 更新时间:2023-12-02 02:28:33 26 4
gpt4 key购买 nike

我一直在为这个 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)

您可以看到代码正在运行 here .

关于scala - 加一链表: Functional Approach,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/65363564/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com