[Leetcode] 2.Add Two Numbers(List To Long,模拟)
2024-09-30 17:34:27
本题题意是指将两个数倒序存储在链表中,再将两数之和同样存储在链表中输出。
我最开始的思路是将每一位相加,再考虑是否进位,但这时就需要考虑一些情况,比较麻烦。
于是我决定采取另一种在网上新学到的方法:这个方法就是将链表中的数字串起来,当做一个long,例如2->4->5,可以根据题目具体要求转化成long型的542,再做后续的操作,就很容易了。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution
{
public:
long ListToLong(ListNode* l)
{
long res = ;
long tem = ;
while(l)
{
res = res + l->val * tem;
tem = tem * ;
l = l->next;
}
return res;
}
long get_n(long num)
{
long x = ;
long n = ;
while(num >= x)
{
n ++;
x = x * ;
}
return n;
}
void add(ListNode* l1, ListNode* l2)
{
while(l1->next)
{
l1 = l1->next;
}
l1->next = l2;
}
ListNode* LongToList(long num)
{
ListNode* res = new ListNode(-);
int n = get_n(num);
//cout<<"n = "<<n<<endl;
int x = ;
for(int i = ;i < n;i ++)
{
x = num % ;
num = num / ;
ListNode* node = new ListNode(x);
add(res,node);
}
return res->next;
}
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
{
long num1 = ListToLong(l1);
long num2 = ListToLong(l2);
//cout<<"num1 = "<<num1<<" num2 = "<<num2<<endl;
long num3 = num1 + num2;
//cout<<"num3 = "<<num3<<endl;
ListNode* res = LongToList(num3);
return res;
}
};
但上面的代码提交后的结果很让我无语。。。见下图
只有两个示例没有通过。。。将long改成long long依旧不能通过,应该是特意添加的这两个示例,这种算法看来只能做到这步了。
于是我不得不回到最开始的思路,下面是AC代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution
{
public:
int M = ;//表示进位
ListNode* res = new ListNode();//结果链表
int flag = ;
void add(ListNode* l1, ListNode* l2)
{
while(l1->next)
{
l1 = l1->next;
}
l1->next = l2;
}
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
{
ListNode* temp = new ListNode();
if(l1 == NULL && l2 == NULL)
return res->next;
else if(l1 == NULL)
{
temp->val = temp->val + M + l2->val;
if(temp->val >= )
{
temp->val = temp->val - ;
M = ;
}
else
{
M = ;
}
ListNode* e1 = new ListNode(temp->val);
add(res,e1);
if(M && (l2->next == NULL))
{
ListNode* e3 = new ListNode();
add(res,e3);
}
addTwoNumbers(NULL,l2->next);
return res->next;
}
else if(l2 == NULL)
{
temp->val = temp->val + M + l1->val;
if(temp->val >= )
{
temp->val = temp->val - ;
M = ;
}
else
{
M = ;
}
ListNode* e2 = new ListNode(temp->val);
add(res,e2);
if(M && (l1->next == NULL))
{
ListNode* e4 = new ListNode();
add(res,e4);
}
addTwoNumbers(l1->next,l2);
return res->next;
}
else
{
int x = l1->val + l2->val + M;
if(x >= )
{
x = x - ;
M = ;
}
else
{
M = ;
}
ListNode* Node = new ListNode(x);
add(res,Node);
if(l1->next == NULL && l2->next == NULL && M == )
{
ListNode* e = new ListNode();
add(res,e);
}
else
{
addTwoNumbers(l1->next,l2->next);
}
return res->next;
}
}
};
最新文章
- 关于 CSS 反射倒影的研究思考
- PHP变量作用域(花括号、global、闭包)
- 反复请求某个URL缓存严重解决办法
- Windows2008系统忘记密码的解决方法
- SpringMVC源码解析 - HandlerMethod
- 案例:利用累加器计算前N个学生的总成绩和平均成绩
- 第四章——SQLServer2008-2012资源及性能监控(2) .
- Flex 日志管理
- java复习-多线程
- python xpath学习
- ClickHouse之初步认识
- 手动升级11.2.0.1的rac数据库到11.2.0.4
- DOS下读取PCI配置空间信息的汇编程序(通过IOCF8/IOCFC)
- Win10系列:VC++媒体播放控制4
- Oracle12C版本安装步骤
- 使用eclipse启动系统时报错“ java.lang.OutOfMemoryError: PermGen space”问题的解决
- Python如何实现文本转语音
- BC#29A:GTY&#39;s math problem(math) B:GTY&#39;s birthday gift(矩阵快速幂)
- SaltStack部署配置Tomcat-第三篇
- [Luogu1462]通往奥格瑞玛的道路