【刷题】 leetcode 2 .两数相加

简介: 两数相加

两数相加

家人们!!!上链接!!! 两数相加

题目描述

给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。
请你将两个数相加,并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外,这两个数都不会以 0 开头。

我们来看看题目,,,,往往困难的题只需要 简单的叙述。好像只用找到两个数,整合成一个链表就可以。这里的相加是一个一个节点的相加,可以想到加法器的思路。来看样例:


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

输出:[7,0,8]

解释:342 + 465 = 807.

从右边开始逐渐相加即可。样例非常清楚!!!

1 思路一 (暴毙版)

  1. 首先 我最快想到思路是 分别根据两个链表求出对应数
  2. 然后加一起 ,得到和
  3. 再把和拆分储存到链表里

为此我们需要手撕一下链表头插。(如果使用C++的STL库会很方便,这里C语言也更锻炼我们的思路)!!!

 typedef struct ListNode SLTNode;
SLTNode* buynode(int n) {
  //开辟空间
    SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
    node->next = NULL;
    node->val = n;
    return node;
}
void pushback(SLTNode** ret, int n) {
  //创建节点
    SLTNode* node = buynode(n);
    //如果头为空 node成为头
    if (*ret == NULL)
    {
        *ret = node;
        return;
    }
  //找尾
    SLTNode* cur = *ret;
    while(cur->next) {
        cur = cur->next;
    }
    //插入
    cur->next = node;
    return;
}

SLTNode* addTwoNumbers(SLTNode* l1, SLTNode* l2) {
    //选择long long 来储存较大数
    long long  num1 = 0, num2 = 0;
    long long   a = 1;
    //计算数一
    while (l1 != NULL) {
        num1 += (l1->val) * a;
        l1 = l1->next;
        a *= 10;
    }
    a = 1;
    //计算数二
    while (l2 != NULL) {
        num2 += (l2->val) * a;
        l2 = l2->next;
        a *= 10;
    }
    //求和
    long long  sum = num1 + num2;
    //构建链表
    SLTNode* ret = NULL;
    if(sum == 0)
    {
        pushback(&ret,0);
        return ret;
    }
    while (sum != 0) {
        long long  n = sum % 10;
        pushback(&ret, n);
        sum = sum / 10;
    }
    //返回链表
    return ret;
}

一顿操作猛如虎,一看提交原地杵········

Line 39: Char 11: runtime error: signed integer overflow: 1000000000000000000 * 10 cannot be represented in type 'long long int' [solution.c]


虽然我已经使用最大的数据类型 long long ,但是最后的测试数据太大,还有3 个样例无法通过。这下子要从头开始了。

(这就得夸夸力扣了,丰富的测试用例,不会随便让你过)

该算法的弊端就显现出来了,我们是在数据类型的基础上操作,而不是在本质上进行相加!!!

2 思路二 (本质出发)

思路一的简单加和不能完成目的,那我们只好深入到加法的本质中去:

按位计算,满10进一 ,逐个逐个计算

这样就算把天文数字填进来,只要内存够,咱都能解决!!!

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode Listnode;
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    //创建头结点
    Listnode* head = (Listnode*)malloc(sizeof(Listnode));
    //创建尾指针
    Listnode* cur = head;
    //进位数
    int t = 0;
    //l1 l2 t 全为空才停止
    while(l1||l2||t){
        //l1 为真则把值赋值在t上
        if(l1) {
            t += l1->val;
            l1 = l1->next;
        }
        //l2 为真则把值赋值在t上
        if(l2) {
            t += l2->val;
            l2 = l2->next;
        }
        //创建节点
        cur->next = ( Listnode *)malloc(sizeof(Listnode));
        cur->next->val = t % 10;
        cur->next->next = NULL;
        //向后移动
        cur = cur->next;
        t /= 10;
    }
    return head->next;

}

一气呵成,呼~~~~

我们舍去手撕链表头插的痛苦。直接改为“满足条件”就开辟新空间。因此为了方便这里使用带头链表。

提交! 过过过过啦!!!!!!


来看看性能怎么样,打败了80%的用户,10ms.

来分析一下咱们算法的时间复杂度 ,遍历链表,最坏情况也是遍历了一条很长的链表。那咱时间复杂度就是O(n)。啊?还有比 O(n) 更快的算法???答案是肯定没有,运行速度的具体原因和配置环境有关。咱们的代码冲一冲也可以0ms。

这道题考察了咱们对循环的认识,通过循环实现加法器。进而完成题目!

谢谢阅读Thanks♪(・ω・)ノ

下一篇文章见!!!!!!

相关文章
|
2天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
3天前
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
|
3天前
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
|
3天前
|
索引
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
|
3天前
【LeetCode刷题】专题三:二分查找模板
【LeetCode刷题】专题三:二分查找模板
【LeetCode刷题】专题三:二分查找模板
|
3天前
|
算法
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
|
3天前
|
算法 容器
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
|
3天前
【LeetCode刷题】滑动窗口思想解决:最大连续1的个数 III、将x减到0的最小操作数
【LeetCode刷题】滑动窗口思想解决:最大连续1的个数 III、将x减到0的最小操作数
|
3天前
【LeetCode刷题】滑动窗口思想解决问题:长度最小的子数组、无重复字符的最长子串
【LeetCode刷题】滑动窗口思想解决问题:长度最小的子数组、无重复字符的最长子串