LeetCode Add Two Numbers

发表于 | 分类于 | 阅读次数：
本文字数： 2.7k | 阅读时长 ≈ 2 分钟

前言

有空的时候就用scala刷一些题，熟悉一下scala和FP编程，也算复习算法。

思路

题目是两数相加，用链表表示一个整数，每个节点一个数字。

trick是相加之后的之后一个数字如果大于等于10就要新加一个节点。

看到题目想到可以用scala的高阶函数来进行操作。

题解

函数式

使用zip操作，zip又叫拉链，像拉链一样，把两个有序集合按序一对对拼在一起，形成一个Tuple。

比如

1
2
3
4
5
val a = List(1, 2, 3)
val b = List("a", "b", "c", "d")

val c = a.zip(b) 
//List[(Int, String)] = List((1,a), (2,b), (3,c))

但是zip操作一般是应用于两个相同长度的列表。它会把两个不同长度的列表，按照较短的那个列表进行截断。

这时候就需要用到 zipAll方法，它可以补全较短的列表，按照较长的列表的长短来进行拉链操作，这样就需要传入两个用于补充长度的默认值参数。
zipAll(B, aa, bb)
其中 aa 是前一个列表的默认值，bb 是第二个列表的默认值。

1
2
val d = a.zipAll(b, 0, "T")
//List[(Int, String)] = List((1,a), (2,b), (3,c), (0,d))

然后在应用 reduceLeft来合并节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
object AddTwoNumbers {

  def addTwoNumbers(l1: ListNode, l2: ListNode): ListNode = {
    val a1 = listNode2List(l1)
    val a2 = listNode2List(l2)
    val lns = a1.zipAll(a2, 0, 0).map(x => x._1 + x._2).map(new ListNode(_))
    val last = lns.reduceLeft((n1, n2) => {
      n2.x += n1.x / 10
      n1.x = n1.x % 10
      n1.next = n2
      n2
    })
    if (last.x >= 10) {
      val ll = new ListNode(last.x / 10)
      last.x = last.x % 10
      last.next = ll
    }
    lns(0)
  }

  def listNode2List(ln: ListNode): List[Int] = {
    val arrBuffer = new collection.mutable.ArrayBuffer[Int]()
    var curNode = ln
    while (curNode != null) {
      arrBuffer.append(curNode.x)
      curNode = curNode.next
    }
    arrBuffer.toList
  }

  def list2ListNode(list: List[Int]): ListNode = {
    val lns = list.map(new ListNode(_))
    lns.reduceLeft((n1, n2) => {
      n1.next = n2
      n2
    })
    lns(0)
  }

  def main(args: Array[String]): Unit = {
    /** addTwoNumbers */
//    val ln1 = list2ListNode(List(2, 4, 3))
//    val ln2 = list2ListNode(List(3, 8, 9, 9, 3))
    val ln1 = list2ListNode(List(5, 5, 9, 9))
    val ln2 = list2ListNode(List(5, 5))
    val ln3 = addTwoNumbers(ln1, ln2)
    listNode2List(ln3).map( println )
  }
}

这样执行用时是 3148 ms。好像有点久，换过程式方法试试看。

过程式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def addTwoNumbers(l1: ListNode, l2: ListNode): ListNode = {
    var p1 = l1
    var p2 = l2
    while (p1 != null && p2 != null) {
      p1.x = p1.x + p2.x
      p2.x = p1.x
      p1 = p1.next
      p2 = p2.next
    }
    p1 = if (p1 == null) l2 else l1
    p2 = p1
    while (p1 != null) {
      if (p1.x >= 10) {
        if (p1.next != null) {
          p1.next.x += p1.x / 10
          p1.x = p1.x % 10
        } else {
          val nn = new ListNode(1)
          p1.x = p1.x % 10
          p1.next = nn
        }
      }
      p1 = p1.next
    }
    p2
  }

这样执行用时也要 2232 ms。应该还是有不少改进空间。

------ EOF ------