Más una lista vinculada: Enfoque funcional

Question

He estado golpeando mi cabeza en este problema de código de leet. Me pregunto si hay una manera funcional de abordar esto. Todo lo que puedo inventar es usar objetos mutables (en Scala). Dado un entero no negativo representado como una lista vinculada de dígitos, más uno al entero. Los dígitos se almacenan de tal manera que el dígito más significativo está en la cabeza de la lista. Ejemplo 1: Entrada: cabeza = [1,2,3]Producto: [1,2,4] Ejemplo 2: Entrada: cabeza = [0]Producto: [1] Constraints: El número de nodos en la lista vinculada está en el rango [1, 100]. 0 <= Node.val <= 9 El número representado por la lista enlazada no contiene ceros principales excepto el cero mismo. * 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 = { } } Más interesante entrada / salida = [1,9,9,9,9] => [2,0,0,0,0]

scriptsorcerer4f7e · Accepted Answer

(detalle) ¡Recusión al rescate! 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) } Lo que puedes usar así: plusOne(List(1, 2, 3)) // res: Number = List(1, 2, 4) Puedes ver el código en funcionamiento Aquí..

pixelpioneerx · Answer

Aquí hay un enfoque:

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

Tenga en cuenta que en lugar de convertir elementos ListNode a números que podrían ser problemáticos para ListNodes grandes, fold se utiliza para realizar summación de elementos iterativos.

Pruebas del código:

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)

Respondida el Dec 18, 2020 a las 20:47 - por pixelpioneerx

devepicenter · Answer

No muy eficiente solución, pero seguro el más corto:

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

Código Scastie

En Scala 2.13 se puede utilizar 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)
}

Código Scastie.

Respondida el Dec 18, 2020 a las 20:54 - por devepicenter

Gpt · Answer

Para abordar este problema de sumar uno a un entero representado como una lista vinculada de dígitos de manera funcional, puedes hacer uso de una función recursiva en Scala. Aquí te dejo una posible implementación utilizando un enfoque funcional:

```scala // 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 = { def addOne(node: ListNode): (ListNode, Int) = { if (node == null) { (new ListNode(1), 0) } else { val (nextNode, carry) = addOne(node.next) val sum = node.x + carry node.x = sum % 10 (node, sum / 10) } }

val (newHead, carry) = addOne(head)
if (carry == 1) {
  val newHeadWithCarry = new ListNode(1)
  newHeadWithCarry.next = newHead
  newHeadWithCarry

Respondida el Dec 19, 2020 a las 20:40 - por Gpt

Gemini · Answer

Solución funcional en Scala scala object Solution { def plusOne(head: ListNode): ListNode = { def reverse(list: ListNode): ListNode = { @annotation.tailrec def loop(current: ListNode, acc: ListNode = null): ListNode = { if (current == null) acc else loop(current.next, ListNode(current.x, acc)) } loop(list) } def increment(list: ListNode): ListNode = { @annotation.tailrec def loop(current: ListNode, carry: Int = 0): ListNode = { if (current == null) { if (carry != 0) ListNode(carry, null) else null } else { val sum = current.x + carry loop(current.next, sum / 10) } } loop(list) } if (head == null) null else { val reversed = reverse(head) val incremented = increment(reversed) reverse(incremented) } } // ListNode class (assuming it's defined elsewhere) case class ListNode(_x: Int = 0, _next: ListNode = null) { var next: ListNode = _next var x: Int = _x } } Explicación: La función reverse invierte la lista vinculada para facilitar el procesamiento de los dígitos. La función increment recorre la lista enlazada invertida, incrementando cada dígito y propagando el acarreo. El resultado de increment se invierte nuevamente para obtener la lista vinculada final con el entero incrementado. Se manejan casos especiales para listas vacías y ceros iniciales.

Más una lista vinculada: Enfoque funcional

5 Respuestas: