建设工程竣工验收消防备案网站,怎么防止网站被镜像,怎么用lofter做网站,江门专业网站制作公司写在前面#xff1a; 题目链接#xff1a;LeetCode2两数相加 编程语言#xff1a;C 题目难度#xff1a;中等 一、题目描述
给你两个 非空 的链表#xff0c;表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的#xff0c;并且每个节点只能存储 一位 数字。
…写在前面 题目链接LeetCode2两数相加 编程语言C 题目难度中等 一、题目描述
给你两个 非空 的链表表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的并且每个节点只能存储 一位 数字。
请你将两个数相加并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外这两个数都不会以 0 开头。 输入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] 提示 每个链表中的节点数在范围 [1, 100] 内 0 Node.val 9 题目数据保证列表表示的数字不含前导零 二、题目分析解题思路代码实现
2.1 常规老实人解法
解之前先吐槽一番计算两个数相加的结果给个单向链表也就算了存的还是数字的反序意味着本来要计算12323还得 先将链表遍历一遍 3-2-1 3-2 再反序一次得到正序 (后面才意识到不用反序) 12 3 23 接下来就开始进行 加法运算 要么先将 12 3 和23 先转换为 123、23 然后计算得出结果为 146然后再逐一的进行再把每一位取出来并且按照逆序 构建成 一个 6-4-1 单向链表再返回回去 要么直接进行按位相加自己设计进位最后 组成 641 这样有一个序列然后构建链表再返回。 各位献丑了且看我写了半小时的代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* listResult new ListNode();vectorint vct1;vectorint vct2;ListNode* nodeTemp l1;//先将l1、l2遍历一遍while(nodeTemp ! nullptr){vct1.push_back(nodeTemp-val);nodeTemp nodeTemp-next;}ListNode* nodeTemp1 l2;while(nodeTemp1 ! nullptr){vct2.push_back(nodeTemp1-val);nodeTemp1 nodeTemp1-next;}vectorint vctResult;int i 0;int j 0;int iTemp 0;bool isTen false;//是否进位//开始按位相加 从 个位开始while(ivct1.size() jvct2.size()){iTemp vct1[i] vct2[j];if(isTen){iTemp 1;}if(iTemp 10){isTen true;iTemp iTemp -10;} else{isTen false;} vctResult.push_back(iTemp);i;j;}//两个链表长度不相等那么剩下的直接继续按位加即可while( i vct1.size()){if(isTen)//注意上一个while 后可能还有进位 1{if(vct1[i] 1 10)//继续进位{vctResult.push_back(0);isTen true;}else{vctResult.push_back(vct1[i]1);isTen false;}i;}else{//没有进位直接插入即可vctResult.push_back(vct1[i]);i;}}//同理将剩下的都插入和上面进位机制一样while( j vct2.size()){if(isTen){if(vct2[j] 1 10){vctResult.push_back(0);isTen true;}else{vctResult.push_back(vct2[j]1);isTen false;}j;}else{vctResult.push_back(vct2[j]);j;}}if(isTen)//注意可能最后还有一次进位{vctResult.push_back(1);}//接下来构建出链表bool head true;ListNode* nodenext new ListNode();for(int k 0; k vctResult.size();k){ListNode* node new ListNode();node-val vctResult[k];node-next nullptr;if(head){listResult node;//保存头做返回值返回nodenext node;head false;}else{nodenext-next node;nodenext nodenext-next;}}return listResult;}
};运行结果 跑了几次好一点的就是下面这样了
2.1.2 优化后
写道最后才发现不需要用两个vector 遍历直接遍历链表即可我们常固性思维觉得加法就是这样 其实我们做个镜像对比 这不就是我们刚好要的答案吗 因此我们现在直接简化为 遍历两个链表 3 - 2 - 1 3-2 将刚才的代码额外的两次遍历与两个vector 开辟 干掉 直接做进位的加法我们将上述的代码优化为
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* listResult new ListNode();ListNode* nodeTemp l1;ListNode* nodeTemp1 l2;vectorint vctResult;int i 0;int j 0;int iTemp 0;bool isTen false;//是否进位//开始按位相加 从 个位开始while(nodeTemp!nullptr nodeTemp1!nullptr){iTemp nodeTemp-val nodeTemp1-val;if(isTen){iTemp 1;}if(iTemp 10){isTen true;iTemp iTemp -10;} else{isTen false;} vctResult.push_back(iTemp);nodeTemp nodeTemp-next;nodeTemp1 nodeTemp1-next;}//两个链表长度不相等那么剩下的直接继续按位加即可while( nodeTemp! nullptr){if(isTen)//注意上一个while 后可能还有进位 1{if(nodeTemp-val 1 10)//继续进位{vctResult.push_back(0);isTen true;}else{vctResult.push_back(nodeTemp-val1);isTen false;}nodeTempnodeTemp-next;}else{//没有进位直接插入即可vctResult.push_back(nodeTemp-val);nodeTempnodeTemp-next;;}}//同理将剩下的都插入和上面进位机制一样while( nodeTemp1 ! nullptr){if(isTen){if(nodeTemp1-val 1 10){vctResult.push_back(0);isTen true;}else{vctResult.push_back(nodeTemp1-val1);isTen false;}nodeTemp1 nodeTemp1-next;}else{vctResult.push_back(nodeTemp1-val);nodeTemp1 nodeTemp1-next;}}if(isTen)//注意可能最后还有一次进位{vctResult.push_back(1);}//接下来构建出链表bool head true;ListNode* nodenext new ListNode();for(int k 0; k vctResult.size();k){ListNode* node new ListNode();node-val vctResult[k];node-next nullptr;if(head){listResult node;//保存头做返回值返回nodenext node;head false;}else{nodenext-next node;nodenext nodenext-next;}}return listResult;}
};可以看到时间和空间上都有所优化。
但是可以看到整个代码还是臭长臭长的而且还开辟了一个新vector用于保存结果空间复杂度也没有降低还有没有更简介的写法呢
2.3 写法简化空间优化
之前还需要一个 bool 值来控制是否进位每次还需要取余数等等非常的繁琐 其实我们直接取两位和的个位数为当前位的值取 10 位上的数为进位即可 例如 5 9 当前位为 14 % 10 4 进位为14 / 10 1; 而且之前会考虑链表长度不相等的情况然后对余下的节点再做一次遍历并且判断之前的进位 换种思路我们将空缺的部分补 上 0 这样来处理长度不一样的情况 int n1 nodeTemp nullptr ? 0: nodeTemp-val;int n2 nodeTemp1 nullptr ? 0:nodeTemp1-val;完整代码示例
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* head nullptr;ListNode* tail nullptr;ListNode* nodeTemp l1;ListNode* nodeTemp1 l2;int igientle 0;//进位//开始按位相加 从 个位开始while(nodeTemp!nullptr || nodeTemp1!nullptr){//链表长度不够时补 0 int n1 nodeTemp nullptr ? 0: nodeTemp-val;int n2 nodeTemp1 nullptr ? 0:nodeTemp1-val;int temp n1n2igientle;//两位的和再加上进位if(!head)//先将头节点保存好{head new ListNode(temp % 10);//取余数tail head;} else{tail-next new ListNode(temp%10);tail tail-next;}igientletemp/10;//进位 if(nodeTemp){nodeTemp nodeTemp-next;}if(nodeTemp1){nodeTemp1 nodeTemp1-next;}}if(igientle 0)//最后还有进位时也加上{tail-next new ListNode(igientle);}return head;}
};运行结果
