目录

BM86 大数加法

题目：BM86 大数加法

思路：

代码：

2. 两数相加

题目：2. 两数相加

思路：

代码：

445. 两数相加 II

题目：445. 两数相加 II

思路：

代码：

这三个题是一个类型的题，应该秒解；

BM86 大数加法

题目：BM86 大数加法

以字符串的形式读入两个数字，编写一个函数计算它们的和，以字符串形式返回；

数据范围：s.length,t.length≤100000，字符串仅由'0'~‘9’构成

要求：时间复杂度 O(n)

示例1

输入：

"1","99"

返回值：

"100"

说明：

1+99=100      

示例2

输入：

"114514",""

返回值：

"114514"

思路：

• 大整数相加，就可以按照整数相加的方式，从个位开始，逐渐往上累加，换到字符串中就是从两个字符串的末尾开始相加；
• 因为s.charAt(i) - 'A' + 'a'是数字；
• 循环条件是两个字符串不都为空，或存在进位；
• 判断索引是否到0了，小于等于0之后都是0；
• 从低位到高位进行计算；
• 所以最后需要反过来；reverse()方法；
• 注意长度与索引的关系，是-1的；

代码：

	import java.util.*;
	
	public class Solution {
		public String solve (String s, String t) {
			if (s.length() == 0)return t;
			if (t.length() == 0)return s;
 
			int carry = 0;
			StringBuilder res = new StringBuilder();
			int i1 = s.length(), i2 = t.length();
			while (i1 > 0 || i2 > 0 || carry > 0) {
				int a = (i1 > 0) ? s.charAt(i1 - 1) - '0' : 0;
				int b = (i2 > 0) ? t.charAt(i2 - 1) - '0': 0;
				int cur = a + b + carry;
				carry = cur / 10;
				cur %= 10;
				res.append(cur);
				i1--;
				i2--;
			}
			return res.reverse().toString();
		}
	}

2. 两数相加

题目：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
• 题目数据保证列表表示的数字不含前导零

思路：

 和上面那个题一模一样，只是换成了链表而已

代码：

	class Solution {
		public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
			// 使用预先指针的目的在于链表初始化时无可用节点值，而且链表构造过程需要指针移动，进而会导致头指针丢失，无法返回结果
			// pre就是为了指向头结点，cur是需要新建并一直移动往前走的
			ListNode pre = new ListNode(0);
			ListNode cur = pre;
			int carry = 0;
			while (l1 != null || l2 != null|| carry!=0) {
				// 有可能l1或l2是空，所以需要进行补零操作
				int x = l1 == null ? 0 : l1.val;
				int y = l2 == null ? 0 : l2.val;
				int sum = x + y + carry;
				// 每一位计算的同时需要考虑上一位的进位问题，而当前位计算结束后同样需要更新进位值
				
				carry = sum / 10;
				sum = sum % 10;
				
				// 将sum作为cur的下一个新建的值
				cur.next = new ListNode(sum);
				// 往前移动cur
				cur = cur.next;
				if (l1 != null)
					l1 = l1.next;
				if (l2 != null)
					l2 = l2.next;
			}
			return pre.next;
		}
}

445. 两数相加 II

题目：445. 两数相加 II

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头；

示例1：

输入：l1 = [7,2,4,3], l2 = [5,6,4]

输出：[7,8,0,7]

示例2：

输入：l1 = [2,4,3], l2 = [5,6,4]

输出：[8,0,7]

示例3：

输入：l1 = [0], l2 = [0]

输出：[0]

提示：

• 链表的长度范围为 [1, 100]；
• 0 <= node.val <= 9；
• 输入数据保证链表代表的数字无前导 0；

思路：

 思路还是一样，只不过需要先使用栈逆序处理；

代码：

	import java.util.Deque;
	import java.util.LinkedList;
	
	class Solution {
		public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
			Deque stack1 = new LinkedList();
			Deque stack2 = new LinkedList();
			while (l1 != null) {
				stack1.push(l1.val);
				l1 = l1.next;
			}
			while (l2 != null) {
				stack2.push(l2.val);
				l2 = l2.next;
			}
			int carry = 0;
			ListNode pre= null;
			while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
				int a = stack1.isEmpty() ? 0 : stack1.pop();
				int b = stack2.isEmpty() ? 0 : stack2.pop();
				int cur = a + b + carry;
				carry = cur / 10;
				cur %= 10;
				ListNode newnode = new ListNode(cur);
				newnode.next = pre;
				pre= newnode;
			}
			return ans;
		}
}