相加求和问题 | LeetCode
相加求和问题 | LeetCode
本篇文章分享 LeetCode 中两道关于求和的题目，难度适中。 第一题是 LeetCode.415 简单·字符串相加 另一题是 LeetCode.2 中等·两数相加
这两道题目呢，一道是字符串类型的，一道是链表类型的，两道题目非常相似，思路也差不多。其实只要 415 的 「字符串相加」 写出来 ，就会发现第 2 题的难度并不算是「中等」 🤣。
好的，下边来上菜~
✔415 字符串相加
给定两个字符串形式的非负整数
num1和num2，计算它们的和。 提示：
num1和num2的长度都小于 5100num1和num2都只包含数字 0-9num1和num2都不包含任何前导零- 「不能使用」任何內建
BigInteger库， 也不能直接将输入的字符串转换为整数形式
题目中没有给出示例，但是根据题目描述的意思，我们可以知道，应该是这个样子的：
Input:
"123"，"28"Output:"151"Reason: 123 + 28 = 151
首先拿到这个题目，我们可以思考加法运算的基本法则：「从个位开始运算，两两相加+进位，大于10需要进位」。有了这个规则，我们就可以确定思路了。
- 从末尾开始运算，进行加减
- 定义一个变量存储进位，暂且命名为
carry - 对于字符串长度进行统一化（怎么统一呢？补零即可。123 + 23 = 123 + 023 这个样子）
- 在不将字符串转为数字的情况下如何进行？（我们可以利用字符间的大小值差距进行运算）
OK，分析之后，我们便可以写出来 Solution 了 👇
class Solution {
public String addStrings(String num1, String num2) {
int i = num1.length() - 1, j = num2.length() - 1;
int carry = 0; // 进位
StringBuffer sb = new StringBuffer();
// 从末尾开始遍历，当存在字符串未遍历完或进位不为0进入循环
while(i > -1 || j > -1 || carry != 0){
// 判断是否越界，若越界则用 0 进行填充
int first = (i > -1) ? num1.charAt(i) - '0' : 0;
int second = (j > -1) ? num1.charAt(j) - '0' : 0;
int sum = first + second + carry; // 总和为 两数相加再加上进位
carry = sum / 10; // 计算本次相加的进位
sb.append(sum % 10); // 将计算结果拼接到stringbuffer末尾
// 移动指针
i--;
j--;
}
// 由于上述得到的 StringBuffer 结果实际为反过来的运算结果，所以在返回前需要执行 reverse() 进行反转
return sb.reverse().toString();
}
}
对于该解法，我们可以计算出它的时间空间复杂度：
- 时间复杂度：O(max(len1, len2)). len1 代表
num1的长度，len2 代表num2的长度 - 空间复杂度：O(n). 因为过程中用到了
StringBuffer进行存储，消耗了对应长度的空间
✔2 两数相加
给出两个 「非空」 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 「逆序」 的方式存储的，并且它们的每个节点只能存储 「一位」 数字。 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。 「示例：」 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807
字节跳动曾使用过该题原题
有了上一题目的基础，我们发现，这道题实际上是一样的嘛，只不过将字符串换作了链表，而该链表也是经过了反序的链表，并且根据题目给出的示例，我们完全可以直接从头开始运算。在整个计算过程中我们需要注意的点依旧是：
- 计算过程中的进位
- 链表的长度及对空节点的处理
我们依旧采取 carry 进行存储进位，并将短链表补齐长度，所填充的节点用 0 进行运算。
好，下边让我们献上代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode result = new ListNode(); // 定义返回值
ListNode curr = result; // 定义指针指向链表当前节点
int carry = 0;
// 当链表未遍历完成或进位不为 0 的时候，执行循环
while(l1 != null || l2 != null || carry != 0){
int first = (l1 != null) ? l1.val : 0;
int second = (l2 != null) ? l2.val : 0;
int sum = first + second + carry;
carry = sum / 10;
curr.next = new ListNode(sum % 10);
// 移动链表指针
if(l1 != null) l1 = l1.next;
if(l2 != null) l2 = l2.next;
curr = curr.next;
}
return result.next;
}
}
对于该解法，我们可以计算出它的时间空间复杂度：
- 时间复杂度：O(max(len1, len2)). 其中 len1 代表
l1的长度， len2 代表l2的长度，空间复杂度含义相同。 - 空间复杂度：O(max(len1, len2)). 空间复杂度最多在最后存在进位的情况下会在 max(len1, len2) 的基础上 + 1
看完上边两道题目的解法，是不是感觉如出一辙呢，没有什么难度之分？😋
好啦，最后结尾再给大家基于第二题链表题，留一道简单的拓展题：
如果链表中的数字不是按逆序存储的呢？例如： (3 → 4 → 2) + (4 → 6 → 5) = 8 → 0 → 7
腾讯云开发者
