程式隨筆
0%

【LeetCode】Add Two Numbers

Posted on Edited on In Disqus:

有感於自己是個廢物工程師，開了LeetCode帳號好幾個月一題都還沒刷，所以決定寫一系列紀錄自己刷LeetCode的過程跟解題方法，希望幾年後回頭能看見自己的進步，廢話不多說直接進入題目。

#題目

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
        
    }
}

#解題

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
public class Solution
   {
       public ListNode AddTwoNumbers(ListNode l1, ListNode l2)
       {
           ListNode Result = new ListNode(0);

           ListNode CN1 = l1;
           ListNode CN2 = l2;

           ListNode RCN = Result;
           bool Flag = true;
           while (Flag)
           {
               var Sum = RCN.val +  GetNodeValue(CN1) + GetNodeValue(CN2);

               RCN.val = Sum % 10;

               if (Sum > 9)
                   RCN.next = new ListNode(1);

               CN1 = CN1 == null ? null : CN1.next;
               CN2 = CN2 == null ? null : CN2.next;
               

               Flag = (CN1 != null || CN2 != null);

               if (Flag && RCN.next == null)
                   RCN.next = new ListNode(0);

               RCN = RCN.next;
           }

           return Result;
       }

       private int GetNodeValue(ListNode node)
       {
           return node == null ?  0 : node.val;
       }
   }

Unit Testing

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
[TestClass]
public class SolutionTests
{
    [TestMethod]
    public void AddTwoNumbersTest_輸入L1為342_L2為456_應得到807()
    {
        //arrange
        var l1 = new ListNode(2);
        l1.next = new ListNode(4);
        l1.next.next = new ListNode(3);

        var l2 = new ListNode(5);
        l2.next = new ListNode(6);
        l2.next.next = new ListNode(4);

        var sut = new Solution();

        var expected = new ListNode(7);
        expected.next = new ListNode(0);
        expected.next.next = new ListNode(8);
        //act
        var actual = sut.AddTwoNumbers(l1,l2);

        //assert
        actual.Should().BeEquivalentTo(expected);
    }

    [TestMethod]
    public void AddTwoNumbersTest_輸入L1為42_L2為708_應得到750()
    {
        //arrange
        var l1 = new ListNode(2);
        l1.next = new ListNode(4);

        var l2 = new ListNode(8);
        l2.next = new ListNode(0);
        l2.next.next = new ListNode(7);

        var sut = new Solution();

        var expected = new ListNode(0);
        expected.next = new ListNode(5);
        expected.next.next = new ListNode(7);
        //act
        var actual = sut.AddTwoNumbers(l1, l2);

        //assert
        actual.Should().BeEquivalentTo(expected);
    }

    [TestMethod]
    public void AddTwoNumbersTest_輸入L1為1_L2為99_應得到100()
    {
        //arrange
        var l1 = new ListNode(1);

        var l2 = new ListNode(9);
        l2.next = new ListNode(9);

        var sut = new Solution();

        var expected = new ListNode(0);
        expected.next = new ListNode(0);
        expected.next.next = new ListNode(1);
        //act
        var actual = sut.AddTwoNumbers(l1, l2);

        //assert
        actual.Should().BeEquivalentTo(expected);
    }
}

#分析結果

雖然過了但是效率不佳，執行完LeetCode全部的測試總共花費 176 ms只贏過38.84%的提交範例，所以試試看優化它

/images/20180615/leetcode/1.jpg

移除三元運算子

基本上三元運算子比較耗效能，所以優先改進它

原本

1
2
3
4
private int GetNodeValue(ListNode node)
{
    return node == null ?  0 : node.val;
}

修改後

1
2
3
4
5
6
7
8
9
private int GetNodeValue(ListNode node)
{
    if (node == null)
    {
        return 0;
    }

    return node.val;
}

原本

1
2
CN1 = CN1 == null ? null : CN1.next;
CN2 = CN2 == null ? null : CN2.next;

修改後

1
2
3
4
5
if (Node1Cursor != null)
    Node1Cursor = Node1Cursor.next;

if (Node2Cursor != null)
    Node2Cursor = Node2Cursor.next;

測試結果

/images/20180615/leetcode/2.jpg

簡直是三元運算子定生死….

優化可讀性

乾淨的程式碼，閱讀起來應該像是幾何證明般

Uncle Bob

所以試著讓變數命名更貼近意義一點

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
public class Solution
{
    public ListNode AddTwoNumbers(ListNode l1, ListNode l2)
    {
        ListNode Result = new ListNode(0);

        ListNode Node1Cursor = l1;
        ListNode Node2Cursor = l2;

        ListNode Head = Result;
        bool NeedNextRun = true;
        while (NeedNextRun)
        {
            var Sum = Head.val + GetNodeValue(Node1Cursor) + GetNodeValue(Node2Cursor);

            Head.val = Sum % 10;

            if (Sum > 9)
                Head.next = new ListNode(1);


            if (Node1Cursor != null)
                Node1Cursor = Node1Cursor.next;

            if (Node2Cursor != null)
                Node2Cursor = Node2Cursor.next;

            NeedNextRun = (Node1Cursor != null || Node2Cursor != null);

            if (NeedNextRun && Head.next == null)
                Head.next = new ListNode(0);

            Head = Head.next;
        }

        return Result;
    }

    private int GetNodeValue(ListNode node)
    {
        if (node == null)
        {
            return 0;
        }

        return node.val;
    }
}

也因為有寫單元測試的關係，上述的調整過程中都沒讓程式壞掉，最後希望藉由這樣的練習能讓自己TDD與重構的技巧再更純熟一些