Java 解决方案在内存中击败 86%，简单的暴力算法

比眉伴天荒 2024-03-16 15:44 31阅读 0赞

1.  两个数字相加 - Java 解决方案在内存中胜过 86%，简单的蛮力算法  
    概述  
    在本文中，我们将讨论 LeetCode 问题（2. 两个数字相加）的超低内存 Java 解决方案，该问题涉及将两个表示为链表的数字相加。

问题陈述  
给定两个表示两个非负整数的链表，将两个数字相加并将总和作为链表返回。

数字以相反的顺序存储，因此 1 的数字位于列表的开头。

例子  
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)  
输出：7 -> 0 -> 8  
解释：342 + 465 = 807

直觉  
为了解决这个问题，我们可以首先解析 ListNode 输入的各自编号。完成后，我们可以遍历总和中的每个数字并将其添加到 ListNode，将所有数字链接在一起。

方法  
此方法将两个链表 l1 和 l2 作为输入，并返回一个新的链表，该链表是两个输入链表的总和。该方法将输入的链表转换为 BigInteger 对象，将两个 BigInteger 对象相加求和，然后根据相加结果创建一个新的链表。该方法返回新的链表作为 addTwoNumbers() 方法的结果。

以下是我们方法的概述：

获取链表中两个数的位数。  
将数字相加以获得总和。  
从总和创建一个新的链表。  
返回新的链表作为结果。  
现在让我们在代码中实现这种方法。

代码

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    import java.util.ArrayList;
    import java.lang.StringBuilder;
    import java.math.BigInteger;
    
    class Solution {
        
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        
            // Get digits of L2
            ListNode placeholder = l1;
            ArrayList<Integer> num1Array = new ArrayList<>();
    
            for (int i = 0; i < 100; i++) {
        
                if (placeholder == null) {
        
                    break;
                }
                num1Array.add(placeholder.val);
                placeholder = placeholder.next;
            }
            String stringNum1 = "";
            for (int i = 0; i < num1Array.size(); i++) {
        
                    stringNum1 += num1Array.get(i);
            }
            StringBuilder sb = new StringBuilder(stringNum1).reverse();
            BigInteger num1 = new BigInteger(sb.toString());
    
            // Get digits of L2
            placeholder = l2;
            ArrayList<Integer> num2Array = new ArrayList<>();
    
            for (int i = 0; i < 100; i++) {
        
                if (placeholder == null) {
        
                    break;
                }
                num2Array.add(placeholder.val);
                placeholder = placeholder.next;
            }
            String stringNum2 = "";
            for (int i = 0; i < num2Array.size(); i++) {
        
                    stringNum2 += num2Array.get(i);
            }
            sb = new StringBuilder(stringNum2).reverse();
            BigInteger num2 = new BigInteger(sb.toString());
    
            BigInteger intSum = num1.add(num2);
            String stringSum = String.valueOf(intSum);
            
            ArrayList<ListNode> listNodes = new ArrayList<>();
    
            ListNode current;
            ListNode previous = new ListNode();
            for (int i = 0; i < stringSum.length(); i++) {
        
                if (i == 0) {
        
                    previous = new ListNode(Integer.parseInt(stringSum.charAt(0) + ""));
                    listNodes.add(previous);  
                } else {
        
                    current = new ListNode(Integer.parseInt(stringSum.charAt(i) + ""), previous);
                    listNodes.add(current);
                    previous = current;
                }
            }
    
            return listNodes.get(stringSum.length() - 1);
        }
    }

1.前几行只是给我们的 ListNode 类的定义和 Solution 类的声明。  
2.我们要做的第一件事就是获取链表中两个数的位数。  
3.由于数字的顺序相反，我们可以使用 for 循环遍历链表并将每个数字添加到 ArrayList。  
4.现在我们有了数字，我们可以将它们加在一起。  
5.由于我们在 ArrayLists 中有数字，我们可以使用 StringBuilder 将数字反转，然后将它们转换为字符串。  
6.由于我们不能在 Java 中使用字符串来进行数学运算，因此我们需要将字符串转换为 BigIntegers。  
7.我们现在可以将 BigIntegers 相加并将结果转换为 String。  
8.现在我们将总和作为字符串，我们可以遍历字符串并创建新的 ListNode 对象。  
9.由于我们需要在最后返回ListNode对象，我们可以将每个ListNode添加到一个ArrayList中。  
10.在 for 循环的最后，我们可以返回 ArrayList 末尾的 ListNode 对象（LeetCode 的测试用例检查器可以通过数字跟踪链接）。  
复杂  
时间复杂度：O(n)

空间复杂度：O(n)

如果你喜欢我的文章，记得关注获取更多的信息。感谢您的阅读，祝您有美好的一天！