按顺序来吧,今天打卡第二题
两数相加
解一:
上来直接暴力求解,即先还原两个加数,对其进行加法运算后,再依次取余计算每一位并存入链表中返回。
运行测试例子的时候没什么问题,但倒在提交上了 (失败例子:999999+9999),long类型顶不住啊,又算了算链表最多可以有100个节点,这啥类型也不行啊。暴力失败,但还是把这个失败代码贴上来看看(C++)
/**
* 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* res =new ListNode();
long a=0;
long b=0;
for (ListNode* i=l1;i;i=i->next)
a=(long)(a*10+i->val);
for (ListNode* j=l2;j;j=j->next)
b=(long)(b*10+j->val);
long c = a+b;
ListNode* l_ = res;
for(long d=c;d>0;d=d/10){
int e = (int)d%10;
l_->val = e;
if(d>10){
ListNode* lt = new ListNode();
l_->next = lt;
l_ = lt;
}
}
return res;
}
};
解二:
没有想到特别快速有效的方法(就是那种要灵机一动的),所以决定直接按照加法的思路来进行了,即单独计算每一位,记录进位(Java)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode res =new ListNode();
int a;
int b;
int flag = 0;
ListNode r_ = res;
while(l1!=null || l2!=null || flag!=0){
if(l1!=null){
a = l1.val;
l1 = l1.next;
}else
a = 0;
if(l2!=null){
b = l2.val;
l2 = l2.next;
}else
b = 0;
int c=a+b+flag;
r_.val = c%10;
if(c>=10)
flag = 1; // 两个数相加,最多进1
else
flag = 0;
if(l1!=null || l2!=null || flag!=0)
r_.next = new ListNode();
r_ = r_.next;
}
return res;
}
}
运行提交通过
说说我遇到的思维坑点:刚开始判断的时候忽略了即使l1和l2链表完成了遍历,但若存在进位还需要进行一轮循环的情况,导致结果丢失了最高位的1。
周五了,早溜一会儿,不待到21:50了,其他大佬的解法有时间再重现吧。