LeetCode 2 Add Two Sum 解题报告
LeetCode第二题 Add Two Sum 首先我们看题目要求:
You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
题目分析
这道题目是一道基础的链表题,给定两个非负数,它们是按照逆序存储的,每个节点值保留一个数值,要求输出这两个数之和,返回结果链表。本道题目主要是考察链表遍历的一些操作。
思路
1.首先用两个指针,分别同时遍历两个链表,按位相加,设置相应进位标志。
2.当两个链表长度不一致时,结束按位相加的遍历之后,将剩余链接接上
3.需要注意连续进位。
以下给出完整的测试代码,在这里为了操作方便,在遍历时统一把数据放到了list的容器中,主要是担心,对于链接,连续进位时直接用指针new出错,直接将每一位Push到list中,最后直接通过list构造出一个ListNode的链表
#include<iostream>
#include<list>
using namespace std;
struct ListNode
{
int val;
ListNode * next;
ListNode(int x):val(x),next(NULL){}
};
ListNode * createListNode( int * arr, int num)
{
int i = 0;
ListNode * head = new ListNode(arr[0]);//head pointer
ListNode * p1 = head;
ListNode * p2 = head;
if(num == 1)
{
head->next = NULL;
return head;
}
else
{
for(i = 1; i < num; i++)
{
p1 = new ListNode(arr[i]);
p2->next = p1;
p2 = p1;
}
p1->next = NULL;
}
return head;
}
class Solution
{
public:
ListNode * createListNode2( list<int> iList)//
{
int num = iList.size();
list<int>::iterator it = iList.begin();
ListNode * head = new ListNode(*it);//head pointer
ListNode * p1 = head;
ListNode * p2 = head;
it++;
if(num == 1)
{
head->next = NULL;
return head;
}
else
{
for(; it != iList.end(); it++)
{
p1 = new ListNode(*it);
p2->next = p1;
p2 = p1;
}
p1->next = NULL;
}
return head;
}
ListNode * addTwoNumbers (ListNode * ln1,ListNode * ln2)
{
list<int> result;
ListNode * p;
ListNode * p1 = ln1;
ListNode * p2 = ln2;
int carryFlag = 0;
int curNum = 0;
while(p1 != NULL && p2 != NULL)
{
curNum = (p1->val + p2->val + carryFlag)%10;
if((p1->val + p2->val + carryFlag) >= 10)
carryFlag = 1;
else
carryFlag = 0;
result.push_back(curNum);
p1 = p1->next;
p2 = p2->next;
}
if(p1 == NULL && p2 == NULL)
{
if (carryFlag == 1)
result.push_back(carryFlag);
}
else if(p1 != NULL && p2 == NULL )
{
while(p1 != NULL)
{
curNum = (p1->val+carryFlag) %10;
if(p1->val + carryFlag >= 10)
carryFlag = 1;
else
carryFlag = 0;
result.push_back(curNum);
p1 = p1->next;
}
if(carryFlag ==1 )
result.push_back(carryFlag);
}
else if(p1 == NULL && p2 != NULL)
{
while(p2 != NULL)
{
curNum = (p2->val+carryFlag) %10;
if(p2->val + carryFlag >= 10)
carryFlag = 1;
else
carryFlag = 0;
result.push_back(curNum);
p2 = p2->next;
}
if(carryFlag == 1 )
result.push_back(carryFlag);
}
list<int>::iterator it = result.begin();
for(;it != result.end(); it++)
cout<<*it;
return createListNode2(result);
}
};
int main ()
{
int arr1[] = {1};
int arr2[] = {9,9};
Solution s1;
ListNode *l1 = createListNode(arr1,1);
ListNode *l2 = createListNode(arr2,2);
s1.addTwoNumbers(l1,l2);
return 0;
return 0;
}
LeetCode 2 Add Two Sum 解题报告的更多相关文章
-
【LeetCode】494. Target Sum 解题报告(Python & C++)
作者: 负雪明烛 id: fuxuemingzhu 个人博客: http://fuxuemingzhu.cn/ 目录 题目描述 题目大意 解题方法 动态规划 日期 题目地址:https://leetc ...
-
【LeetCode】39. Combination Sum 解题报告(Python & C++)
作者: 负雪明烛 id: fuxuemingzhu 个人博客:http://fuxuemingzhu.cn/ 目录 题目描述 题目大意 解题方法 方法一:递归 方法二:回溯法 日期 题目地址:[htt ...
-
LeetCode 2. Add Two Numbers 解题报告
题意: 有两个链表,它们表示逆序的两个非负数.例 (2 -> 4 -> 3)表示342,求两个数字的和,并用同样的方式逆序输出.如342+465 = 807,你需要把结果表达为(7 -&g ...
-
LeetCode 1 Two Sum 解题报告
LeetCode 1 Two Sum 解题报告 偶然间听见leetcode这个平台,这里面题量也不是很多200多题,打算平时有空在研究生期间就刷完,跟跟多的练习算法的人进行交流思想,一定的ACM算法积 ...
-
【LeetCode】385. Mini Parser 解题报告(Python)
[LeetCode]385. Mini Parser 解题报告(Python) 标签: LeetCode 题目地址:https://leetcode.com/problems/mini-parser/ ...
-
【LeetCode】809. Expressive Words 解题报告(Python)
[LeetCode]809. Expressive Words 解题报告(Python) 标签(空格分隔): LeetCode 作者: 负雪明烛 id: fuxuemingzhu 个人博客: http ...
-
【LeetCode】306. Additive Number 解题报告(Python)
[LeetCode]306. Additive Number 解题报告(Python) 标签(空格分隔): LeetCode 作者: 负雪明烛 id: fuxuemingzhu 个人博客: http: ...
-
【LeetCode】848. Shifting Letters 解题报告(Python)
[LeetCode]848. Shifting Letters 解题报告(Python) 标签(空格分隔): LeetCode 作者: 负雪明烛 id: fuxuemingzhu 个人博客: http ...
-
【LeetCode】554. Brick Wall 解题报告(Python)
[LeetCode]554. Brick Wall 解题报告(Python) 标签(空格分隔): LeetCode 作者: 负雪明烛 id: fuxuemingzhu 个人博客: http://fux ...
随机推荐
-
CSS之水平垂直居中
在css的世界里,如果我们想让一个块级元素水平居中,想必大家都知道利用margin:0 auto;嘛,这样就可以让块级元素在它的父元素中水平居中了. 列如这样: <!DOCTYPE html&g ...
-
.net 下判断中英文字符串长度
System.Text.Encoding.Default.GetBytes(str).Length
-
小技巧:addobject: 和 addobjectsFromArray 的区别
NSArray *array1 = [NSArray alloc]init]; NSArray *array2 = [NSArray alloc]init]; [array1 addobject: a ...
-
scikit-learn的梯度提升算法(Gradient Boosting)使用
前言:本文的目的是记录sklearn包中GBRT的使用,主要是官网各参数的意义:对于理论部分和实际的使用希望在只是给出出处,希望之后有时间能补充完整 摘要: 1.示例 2.模型主要参数 3.模型主要属 ...
-
设计数据结构O1 insert delete和getRandom
设计一个数据结构满足O(1)的insert, delete和getRandom.这个是从地里Amazon的面经中看到的. 我们可以使用一个resizable数组arr以及一个HashMap来完成. i ...
-
Lua基础之字符串(string)
1,计算字符串长度 2,返回字符串s的n个拷贝 3,返回字符串全部字母大写 4,返回字符串全部字母小写 5,返回一个类似printf的格式化字符串 6,根据下标截取字符串 7,在字符串中查找 8,在字 ...
-
jquery prop and attr
http://www.javascript100.com/?p=877 http://blog.sina.com.cn/s/blog_655388ed01017cnc.html http://www. ...
-
一个用SAM维护多个串的根号特技
一个用SAM维护多个串的根号特技 基本介绍 在多个串的字符串题中,往往会出现一类题需要用到某个子串是否在一些母串中出现.此时对于 \(\text{parent}\) 树的 \(\text{right} ...
-
tf更新tensor/自定义层
修改Tensor特定位置的值 如 stack overflow 中提到的方案. TensorFlow不让你直接单独改指定位置的值,但是留了个歪门儿,就是tf.scatter_update这个方法,它可 ...
-
20181013xlVba年级成绩报表
Public Sub 高一成绩报表() Application.ScreenUpdating = False Application.DisplayAlerts = False Application ...