力扣2.两数相加
大整数加法,是再经典不过的模拟——即:用数组或链表模拟 表示 大整数,用数组/链表对应各位的相加、进位,模拟整数的相加、进位。
而,该力扣第二题正是一个最典型的示例。( ̄︶ ̄)↗
关键字索引:数组、链表、模拟、大整数加法
- 题目描述:
- 题意补充:
- 思路|破解
- A解:链表转数组(用数组代替链表 *** 作)
- 思路标识:
- 解题:
- B解:直接用链表模拟
- 思路标识:
- 解题:
- C解:链表模拟,进一步重构,B解优化
- 思路标识:
- 知识回顾:
- 推荐习题:
- 回到《解题者:力扣解题之路》目录:
给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。
题意补充:
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]
提示:
思路|破解 A解:链表转数组(用数组代替链表 *** 作) 思路标识:
- 1-》只要能 正确表示 出计算结果,就能AC
- 2-》无论是数组还是链表,模拟出加法过程即可
- 3-》用数组暂代链表,对初学者是相当友好取巧的策略(我刚来时就是这么干的( •̀ ω •́ )✧)
class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { vectorv1,v2;//把链表中各节点的数值转到数组中来 while(l1){ v1.emplace_back(l1->val); l1=l1->next; } while(l2){ v2.emplace_back(l2->val); l2=l2->next; } int n1=v1.size(),n2=v2.size(); int n=max(n1,n2); vector v(n,0);//使用初学数据结构时,已熟悉的数组 for(int i=0;i =10){ v[i]%=10; if(i!=n-1)v[i+1]++; else v.push_back(1); } } else if(i =n2){ v[i]+=v1[i]; if(v[i]>=10){ v[i]%=10; if(i!=n-1)v[i+1]++; else v.push_back(1); } } else if(i =n1){ v[i]+=v2[i]; if(v[i]>=10){ v[i]%=10; if(i!=n-1)v[i+1]++; else v.push_back(1); } } } //由于题目已说明数字按 逆向 存储,所以这里不用reverse ListNode* dummy=new ListNode(-1,nullptr); ListNode* cur=dummy; for(int i=0;i next=tmp; cur=cur->next; } return dummy->next; } };
B解:直接用链表模拟 思路标识:
- 1-》熟悉A解,用数组形式进行的大整数加法,将数组在换成链表即可
- 2-》理解了模拟加法的思路,我们需要的就是对 链表的熟悉
- 3-》解题过程中,会遇到各种新知识,固步自封、沉醉于已取得的成绩是不行的哦——
class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* head=new ListNode(0,nullptr);//用于移动的head ListNode* dummy=new ListNode(-1,head);//哑结点指向原来的头 while(l1||l2){ ListNode* tmp=new ListNode(0,nullptr);//表示下一位预留的节点 if(l1&&l2){ head->val+=l1->val+l2->val; if(head->val>=10){ head->val%=10; tmp->val++; } l1=l1->next; l2=l2->next; if(l1==nullptr&&l2==nullptr&&tmp->val==0)tmp=nullptr; head->next=tmp; head=tmp; } else if(l1!=nullptr&&l2==nullptr){ head->val+=l1->val; if(head->val>=10){ head->val%=10; tmp->val++; } l1=l1->next; if(l1==nullptr&&tmp->val==0)tmp=nullptr; head->next=tmp;//如果走到末尾,且无需进位,tmp置为空 head=tmp; } else if(l2!=nullptr&&l1==nullptr){ head->val+=l2->val; if(head->val>=10){ head->val%=10; tmp->val++; } l2=l2->next; if(l2==nullptr&&tmp->val==0)tmp=nullptr; head->next=tmp; head=tmp; } } return dummy->next;//返回头结点 } };
C解:链表模拟,进一步重构,B解优化 思路标识:
- 1-》由于数字采用 逆序 储存,我们可以直接对两链表对应各节点进行相加
- 2-》两链表对应位置的数字记为n1、n2,进位值记为carry(表示前一位进位的值),
- 则答案链表对应位的值为 (n1+n2+carry)mod 10⌋,
- 下一位的进位值为⌊ (n1+n2+carry) /10⌋
- 3-》 深刻理解大整数加法模拟的本质后,我们可以这样解——
class Solution { public://思路是一样的,当代码清晰干净了很多 ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode *head =nullptr; ListNode *cur = nullptr; int carry = 0; while (l1 || l2) { int n1 = l1 ? l1->val: 0; int n2 = l2 ? l2->val: 0; int sum = n1 + n2 + carry; if (!head) { head=cur=new ListNode((sum%10)); } else { cur->next = new ListNode(sum % 10); cur = cur->next; } carry = sum / 10; if (l1) l1 = l1->next; if (l2) l2 = l2->next; } if (carry > 0) { cur->next = new ListNode(carry); } return head; } };
知识回顾:
- 大整数,由于已有的数据类型(int、long long 等)无法表示,可用链表或数组模拟表示
- 对大整数进行加法,需要模拟加法过程——如列竖式计算
推荐习题:
- POJ-1 A+B问题
回到《解题者:力扣解题之路》目录:
O(∩_∩)O 《解题者:力扣解题之路》目录传送
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)