前言：
眼前兄弟们对“java求整数各位数字之和”大致比较注重，咱们都需要分析一些“java求整数各位数字之和”的相关文章。那么小编也在网络上网罗了一些有关“java求整数各位数字之和””的相关内容，希望看官们能喜欢，小伙伴们快快来学习一下吧！2. 两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
例子
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]输出：[7,0,8]解释：342 + 465 = 807.
示例 2：
输入：l1 = [0], l2 = [0]输出：[0]
示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]输出：[8,9,9,9,0,0,0,1]提示：
每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零
V1-简单思路思路
l1 反转构建为数字
l2 反转构建为数字
num = l1+l2
然后反转列表输出。
坑：这里限定了入参是一个单向链表
java 实现
这里使用 BigInteger，因为位数会比较长，避免超长的情况。
import java.math.BigInteger;import java.util.LinkedList;import java.util.List;import java.util.ListIterator;/** * @author binbin.hou * @since 1.0.0 * @date 2020-6-9 11:38:48 */public class T002_AddTwoNumbers { public static class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } } /** * 最基本思路 * @param l1 列表1 * @param l2 列表2 * @date 2020-6-9 12:08:44 */ public ListNode addTwoNumbers(ListNode l1, ListNode l2) { List<Integer> numOneList = getIntegerList(l1); List<Integer> numTwoList = getIntegerList(l2); BigInteger numOne = buildBigInteger(numOneList); BigInteger numTwo = buildBigInteger(numTwoList); BigInteger sum = numOne.add(numTwo); return buildListNode(sum); } /** * 构建最后的结果 * @param sum 和 * @return 结果 * @since 1.0.0 */ private ListNode buildListNode(final BigInteger sum) { String string = sum.toString(); ListNode headNode = buildListNode(string, string.length()-1); ListNode currentNode = headNode; for(int i = string.length()-2; i >= 0; i--) { currentNode.next = buildListNode(string, i); currentNode = currentNode.next; } return headNode; } private ListNode buildListNode(String string, int index) { int integer = Integer.parseInt(string.charAt(index) + ""); return new ListNode(integer); } /** * 获取整数的链表 * @param listNode 节点 * @return 结果 * @since 1.0.0 */ public List<Integer> getIntegerList(ListNode listNode) { // 使用 linkedList，避免扩容 List<Integer> resultList = new LinkedList<>(); ListNode oneNode = listNode; while (oneNode != null) { int value = oneNode.val; resultList.add(value); oneNode = oneNode.next; } return resultList; } /** * 根据单个数字构建 BigInteger，不知道入参有多长 * @param integers 数组 * @return 结果 * @since 1.0.0 */ private BigInteger buildBigInteger(final List<Integer> integers) { // 逆序遍历 LinkedList 应该有双向指针，理论上不慢。 integers.iterator(); ListIterator<Integer> iterator = integers.listIterator(integers.size()); // 避免扩容 StringBuilder stringBuilder = new StringBuilder(integers.size()); while(iterator.hasPrevious()){ int integer = iterator.previous(); stringBuilder.append(integer); } return new BigInteger(stringBuilder.toString()); }}效果这种是比较慢的。
效果如下[1]
Runtime: 18 ms, faster than 5.29% of Java online submissions for Add Two Numbers.Memory Usage: 40.4 MB, less than 16.38% of Java online submissions for Add Two Numbers.V2-记录进位思路
每一个节点的值都是 0-9，处理的时候其实我们只需要关心相加是否进位即可。
并不需要这么复杂的把信息处理完相加，从而减少处理时间。
java 实现
说明：这里是自己实现模拟了 BigInteger 的加法。
import java.util.LinkedList;import java.util.List;/** * 官方的解法 * * 核心： * 5+7=12 会产生进位，但是最多只有一次进位 * 因为：9+9+1=19 * * @author binbin.hou * @since 1.0.0 * @date 2020-6-9 11:38:48 */public class T002_AddTwoNumbersV1 { public static class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } } /** * Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) * Output: 7 -> 0 -> 8 * Explanation: 342 + 465 = 807. * * 注意： * （1）两个列表并不是一样长的，可能还有数字为空。 * （2）末尾也可能产生进位 * * 思路： * 直接遍历链表，使用一个位置保留进位。 * * 列表的遍历一直是以最长的为准，走到最后。 * * @param l1 列表1 * @param l2 列表2 * @return 结果 * @date 2020-6-9 12:08:44 */ public ListNode addTwoNumbers(ListNode l1, ListNode l2) { List<Integer> oneList = getIntegerList(l1); List<Integer> twoList = getIntegerList(l2); //[5,5] 最后一位进1 int size = oneList.size() > twoList.size() ? oneList.size() : twoList.size(); // 借助第三条数组，存放进位 int[] overflowFlags = new int[size+1]; // 直接构建结果列表 ListNode headNode = buildListNode(oneList, twoList, 0, overflowFlags); ListNode currentNode = headNode; for(int i = 1; i < size; i++) { currentNode.next = buildListNode(oneList, twoList, i, overflowFlags); currentNode = currentNode.next; } // 最后如果存在进位的话 if(overflowFlags[size] == 1) { currentNode.next = new ListNode(1); } return headNode; } /** * 构建元素列表 * * （1）为了避免 index == 0 时，判断 * 将 index==0 时的信息直接保存在 0 位，当前进位保存在下一位。 * @param oneList 第一个列表 * @param twoList 第二个列表 * @param index 下标 * @param overflowFlags 越界标识 * @return 结果 */ private ListNode buildListNode(final List<Integer> oneList, final List<Integer> twoList, final int index, int[] overflowFlags) { int one = getIndexValue(oneList, index); int two = getIndexValue(twoList, index); int sum = one + two; int previousOverflow = overflowFlags[index]; // 一般都是小于 10 int value = sum + previousOverflow; if(value >= 10) { overflowFlags[index+1] = 1; // 保留个位 value -= 10; } return new ListNode(value); } /** * 获取下标对应的值 * @param list 列表 * @param index 下标 * @return 值 * @since 1.0.0 */ private int getIndexValue(final List<Integer> list, final int index) { if(index < list.size()) { return list.get(index); } return 0; } /** * 获取整数的链表 * @param listNode 节点 * @return 结果 * @since 1.0.0 */ private List<Integer> getIntegerList(ListNode listNode) { // 使用 linkedList，避免扩容 List<Integer> resultList = new LinkedList<>(); ListNode oneNode = listNode; while (oneNode != null) { int value = oneNode.val; resultList.add(value); oneNode = oneNode.next; } return resultList; }}效果效果如下[2]：
Runtime: 3 ms, faster than 29.29% of Java online submissions for Add Two Numbers.Memory Usage: 42.64 MB, less than 47.4% of Java online submissions for Add Two Numbers.V3-优化链表遍历思路
上面的方式中，对于链表的遍历是分别独立进行的。
性能至少有两个优化点：
1）同时遍历两个链表
2）遍历链表的同时，构建节点
内存优化：因为是一边遍历，一边构建节点。所以进位的标识，可以用一个值替代。
java 实现
import com.github.houbb.leetcode.ListNode;/** * 官方的解法 * * 核心： * 5+7=12 会产生进位，但是最多只有一次进位 * 因为：9+9+1=19 * * 核心流程： * * @author binbin.hou * @since 1.0.0 * @date 2020-6-9 11:38:48 */public class T002_AddTwoNumbersV3 { /** * 进位标识 * @since 0.0.1 */ private static volatile int overflowFlag = 0 ; /** * Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) * Output: 7 -> 0 -> 8 * Explanation: 342 + 465 = 807. * * TODO: 要学会避免前两次的列表循环。 * * 注意： * （1）两个列表并不是一样长的，可能还有数字为空。 * （2）末尾也可能产生进位 * * 思路： * 直接遍历链表，使用一个位置保留进位。 * * 列表的遍历一直是以最长的为准，走到最后。 * * * @param l1 列表1 * @param l2 列表2 * @return 结果 * @date 2020-6-9 12:08:44 */ public ListNode addTwoNumbers(ListNode l1, ListNode l2) { overflowFlag = 0; // 直接构建结果列表 ListNode headNode = buildListNode(l1, l2); ListNode currentNode = headNode; ListNode l1Next = l1.next; ListNode l2Next = l2.next; while (l1Next != null || l2Next != null) { currentNode.next = buildListNode(l1Next, l2Next); currentNode = currentNode.next; // 往后遍历 if(l1Next != null) { l1Next = l1Next.next; } if(l2Next != null) { l2Next = l2Next.next; } } // 最后如果存在进位的话 if(overflowFlag == 1) { currentNode.next = new ListNode(1); } return headNode; } /** * 获取下一个元素值 * * 默认返回 0 * @param listNode 当前节点 * @return 下一个节点的值 * @since 1.0.0 */ private int getValue(ListNode listNode) { if(listNode == null) { return 0; } return listNode.val; } /** * 构建元素列表 * * （1）为了避免 index == 0 时，判断 * 将 index==0 时的信息直接保存在 0 位，当前进位保存在下一位。 * @param l1 节点1 * @param l2 节点2 * @return 结果 * @since 0.0.1 */ private ListNode buildListNode(ListNode l1, ListNode l2) { int valueOne = getValue(l1); int valueTwo = getValue(l2); int sum = valueOne+valueTwo + overflowFlag; if(sum >= 10) { sum -= 10; overflowFlag = 1; } else { overflowFlag = 0; } return new ListNode(sum); }}效果效果如下[3]：
Runtime: 1 ms, faster than 100.00% of Java online submissions for Add Two Numbers.Memory Usage: 39.7 MB, less than 44.45% of Java online submissions for Add Two Numbers.小结
对于链表的题目，基本都可以先使用笨方法，把节点放点列表中，然后处理，构建结果列表来解决。
但是这种性能基本是最差的。
对于节点的遍历和构建，值得我们进一步思考与学习。
开源地址
为了便于大家学习，所有实现均已开源。欢迎 fork + star~
参考资料
References
[1] 效果如下:
[2] 效果如下:
[3] 效果如下:
版权声明：
本站文章均来自互联网搜集，如有侵犯您的权益，请联系我们删除，谢谢。
标签： #java求整数各位数字之和
