相加求和问题 | LeetCode

学习心得 做棵大树 4年前 (2020-08-18) 1667次浏览 0个评论
文章目录[隐藏]

本篇文章分享 LeetCode 中两道关于求和的题目,难度适中。

第一题是 LeetCode.415 简单·字符串相加

另一题是 LeetCode.2 中等·两数相加

这两道题目呢,一道是字符串类型的,一道是链表类型的,两道题目非常相似,思路也差不多。其实只要 415 的 字符串相加 写出来 ,就会发现第 2 题的难度并不算是中等 🤣。

好的,下边来上菜~


415 字符串相加

给定两个字符串形式的非负整数 num1num2 ,计算它们的和。

提示:

  1. num1num2 的长度都小于 5100
  2. num1num2 都只包含数字 0-9
  3. num1num2 都不包含任何前导零
  4. 不能使用任何內建 BigInteger 库, 也不能直接将输入的字符串转换为整数形式

题目中没有给出示例,但是根据题目描述的意思,我们可以知道,应该是这个样子的:

Input: "123""28"

Output: "151"

Reason: 123 + 28 = 151

首先拿到这个题目,我们可以思考加法运算的基本法则:从个位开始运算,两两相加+进位,大于 10 需要进位。 有了这个规则,我们就可以确定思路了。

  1. 从末尾开始运算,进行加减
  2. 定义一个变量存储进位,暂且命名为 carry
  3. 对于字符串长度进行统一化(怎么统一呢?补零即可。 123 + 23 = 123 + 023 这个样子)
  4. 在不将字符串转为数字的情况下如何进行?(我们可以利用字符间的大小值差距进行运算)

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

字节跳动曾使用过该题原题

有了上一题目的基础,我们发现,这道题实际上是一样的嘛,只不过将字符串换作了链表,而该链表也是经过了反序的链表,并且根据题目给出的示例,我们完全可以直接从头开始运算。在整个计算过程中我们需要注意的点依旧是:

  1. 计算过程中的进位
  2. 链表的长度及对空节点的处理

我们依旧采取 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


做棵大树 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明相加求和问题 | LeetCode
喜欢 (0)
[欢迎投币]
分享 (0)
关于作者:
一个整天无所事事的,有时候忽然热血的孩子
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址