Leecode第二题:两数相加

给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。

请你将两个数相加,并以相同形式返回一个表示和的链表。

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/add-two-numbers
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

具体详情可以点进链接 题目这里就不做多余的解释了

题目分析

注意看提示
提示:

每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零

说明没有空链表 同时 肯定会越界

ok 我们就不能采用普通的办法了

代码

ok 我们看代码:
先看一个比较容易理解的
先取出数据,后计算结果,在组合答案并返回

int a[101]; int b[101];// 初始化 数组 int End[102];// 最后的结果数组 int i; for(i=0;i<101;i++) { a[i]=b[i]=End[i]=0;// 初始化 } // 我们先算出结果 然后将其写入结构体 然后返回 i=0; ListNode * l=l1; while (l) { a[i++]=l->val; l=l->next;// 取出l1 } l=l2; int aLength=i; i=0; while (l) { b[i++]=l->val; l=l->next;// 取出l2 } int bLength=i; int Cout=0;// 是否进位 int endLength=aLength >bLength? aLength :bLength;// 取最长的长度 for (i=0; i<endLength; i++) { //进位位 Cout=a[i]+b[i]+Cout; End[i]=Cout%10;; Cout/=10; } if (Cout>0) {// 最高位是否发生进位 进位长度加一 End[endLength]=Cout; endLength++; } ListNode *List =new ListNode; l=List; l->val=End[0];// 先把第一位放进去 for(i=1;i<endLength;i++) { l->next=new ListNode; l=l->next; l->val=End[i]; l->next=NULL; } // cout << endl;// 输出验证 l=List; // while (l) { // cout << l->val << "->"; // l=l->next; // } return List;

看一下结果:
执行用时: 52 ms
内存消耗: 69.4 MB

不过这个代码的效率可能会比较低 : 超越了20%的提交记录,不过这个更容易看懂
看一个更简便的方式 ,

int Cout =0; ListNode * Lis = new ListNode; ListNode * l=Lis; while(l1 && l2){ Lis->next=new ListNode; Lis=Lis->next; Cout=Cout+l1->val+l2->val; l1=l1->next; l2=l2->next; Lis->val=Cout%10; Cout/=10; } while (l1) { Cout+=l1->val; l1=l1->next; Lis->next=new ListNode; Lis=Lis->next; Lis->val=Cout%10; Cout/=10; } while (l2) { Cout+=l2->val; l2=l2->next; Lis->next=new ListNode; Lis=Lis->next; Lis->val=Cout%10; Cout/=10; } if(Cout>0){ Lis->next =new ListNode; Lis = Lis->next; Lis->val=Cout; Lis->next=NULL; } return l->next;

这个就不加注释了 ,和上面原理差不多。
这个的结果:
执行结果:
执行结果:
通过

执行用时:32 ms, 在所有 C++ 提交中击败了86.94%的用户内存消耗:69.6 MB, 在所有 C++ 提交中击败了14.75%的用户

时间上就会快很多 不过也跟处理机有关,就上面这个代码,我交了好多次,还出现过52ms的情况

总结

这里主要考察大数加法 原理根小时候学的加法一模一样 ,相信看过上面代码就理解个差不多了,就不多解释了。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wpspjp.html