题目：给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
示例：
输入：[2,4,3]
[5,6,4]
,
输出：[7,0,8]
原因：342 + 465 = 807
输入：[5]
[5]
,
输出：[0,1]
原因：5+5=10
分析：
- 链表对应结点相加时增加前一个结点的进位，并保存下一个结点的进位；除法得进位，模得结果。
- 两个链表长度不一致时，要处理较长链表剩余的高位和进位计算的值；
- 如果最高位计算时还产生进位，则还需要添加一个额外结点。
c++ code 32ms:
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <sstream> //stringstream
using namespace std;
//Definition for singly-linked list.
/*
注释： 先CTRL+K，然后CTRL+C
取消注释： 先CTRL+K，然后CTRL+U
*/
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
//notice: my submit
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* l3 = new ListNode(0);
ListNode* p = l1, *q = l2, *curr = l3;
int cup = 0;
while (p != NULL || q != NULL){
int x = (p != NULL) ? p->val : 0;
int y = (q != NULL) ? q->val : 0;
int sum = x + y + cup;
cup = sum / 10;
curr->next = new ListNode(sum % 10);
curr = curr->next;
if (p != NULL)p = p->next;
if (q != NULL)q = q->next;
}
if (cup>0){
curr->next = new ListNode(cup);
curr = curr->next;
}
return l3->next;
}
};
//修剪左 尾随空格
void trimLeftTrailingSpaces(string &input) {
input.erase(input.begin(), find_if(input.begin(), input.end(), [](int ch) {
return !isspace(ch);
}));
}
//修剪右 尾随空格
void trimRightTrailingSpaces(string &input) {
input.erase(find_if(input.rbegin(), input.rend(), [](int ch) {
return !isspace(ch);
}).base(), input.end());
}
vector<int> stringToIntegerVector(string input) {
vector<int> output;
trimLeftTrailingSpaces(input);
trimRightTrailingSpaces(input);
input = input.substr(1, input.length() - 2);
stringstream ss;
ss.str(input);
string item;
char delim = ',';
while (getline(ss, item, delim)) {
output.push_back(stoi(item));
}
return output;
}
ListNode* stringToListNode(string input) {
// Generate list from the input
vector<int> list = stringToIntegerVector(input);
// Now convert that list into linked list
ListNode* dummyRoot = new ListNode(0);
ListNode* ptr = dummyRoot;
for (int item : list) {
ptr->next = new ListNode(item);
ptr = ptr->next;
}
ptr = dummyRoot->next;
delete dummyRoot;
return ptr;
}
string listNodeToString(ListNode* node) {
if (node == nullptr) {
return "[]";
}
string result;
while (node) {
result += to_string(node->val) + ", ";
node = node->next;
}
return "[" + result.substr(0, result.length() - 2) + "]";
}
int main() {
string s;
while (getline(cin, s)) {
ListNode* l1 = stringToListNode(s);
getline(cin, s);// 读取换行
ListNode* l2 = stringToListNode(s);
ListNode* ret = Solution().addTwoNumbers(l1, l2);
string out = listNodeToString(ret);
cout << out << endl;
}
return 0;
}
测试c++
python code:
- 和上面的思路不一样，参考了目前最快c++ 20ms 提交的代码,改成python运行了200ms。
import json
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
# notice: submit
class Solution(object):
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
curr=ListNode(0)
headl3=curr
while l1 or l2:
if l1:
curr.val+=l1.val
if l2:
curr.val+=l2.val
if l1.next or l2.next or curr.val>9:
curr.next=ListNode(0)
if curr.val>9:
curr.next.val+=1
curr.val-=10
if l1.next:
l1=l1.next
else:
'''[5][5]此例在死循环，以下两处else考虑l1.next不存在
但是还存在回到上面第一个if处加l1.val'''
l1.val=0
if l2.next:
l2=l2.next
else:
l2.val=0
else:
break
curr=curr.next
return headl3
def stringToIntegerList(input):
return json.loads(input)
def stringToListNode(input):
# Generate list from the input
numbers = stringToIntegerList(input)
# Now convert that list into linked list
dummyRoot = ListNode(0)
ptr = dummyRoot
for number in numbers:
ptr.next = ListNode(number)
ptr = ptr.next
ptr = dummyRoot.next
return ptr
def listNodeToString(node):
if not node:
return "[]"
result = ""
while node:
result += str(node.val) + ", "
node = node.next
return "[" + result[:-2] + "]"
def main():
import sys
def readlines():
for line in sys.stdin:
yield line.strip('\n')
lines = readlines()
while True:
try:
line = next(lines)
l1 = stringToListNode(line)
line = next(lines)
l2 = stringToListNode(line)
ret = Solution().addTwoNumbers(l1, l2)
out = listNodeToString(ret)
print(out)
except StopIteration:
break
if __name__ == '__main__':
main()
测试python
在贴一个python( 104ms ) 目前提交最快的，我转成c++反而更慢了 ┏┛┗┓
(c++573ms)
- 思想：尽量不创建节点直接用现有的结点
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
//ListNode* l3 = new ListNode(0);
ListNode* p = l1, *q = l2, *curr = NULL;
int cup = 0;
while (p &&q )
{
int x = (p != NULL) ? p->val : 0;
int y = (q != NULL) ? q->val : 0;
int sum = x + y + cup;
cup = sum / 10;
p->val = sum % 10;
curr = p;
if (p != NULL)p = p->next;
if (q != NULL)q = q->next;
}
while (p)
{
p->val = p->val + cup;
cup = (p->val) / 10;
p->val = p->val % 10;
curr = p;
p = p->next;
}
if (q)
{
//p一直记录着添加的节点
curr->next = q;
}
while (q)
{
q->val = q->val + cup;
cup = (q->val) / 10;
q->val = q->val % 10;
curr = q;
q = q->next;
}
if (cup > 0)
{
curr->next = new ListNode(cup);
curr = curr->next;
}
return l1;
}
};
测试c++
c++小白记录
- getline(cin, s);// 读取字符串
- basic_string::erase( )
- basic_string::isspace( )
- 下面函数理解
分别从左右各两端消除输入时空格：
//erase
void trimLeftTrailingSpaces(string &input) {
input.erase(input.begin(), find_if(input.begin(), input.end(), [](int ch) {
return !isspace(ch);
}));
}
//修剪右 尾随空格
void trimRightTrailingSpaces(string &input) {
input.erase(find_if(input.rbegin(), input.rend(), [](int ch) {
return !isspace(ch);
}).base(), input.end());
}
- find_if:参看手册
find_if(InputIterator first, InputIterator last, Predicate pred);
first:第一个位置
last：最后元素之后下一个元素的位置
Predicate pred：lambda表达式
返回：用于引用范围[first,last] 中满足谓词(Predicate pred)所指定条件的元素
lambda组成
不理解的话，把示例代码运行一遍(主要是区别find() ,find_if())。
code：
// cl.exe /W4 /nologo /EHsc /MTd
#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
template <typename S> void print(const S& s) {
for (const auto& p : s) {
cout << "(" << p << ") ";
}
cout << endl;
}
// Test std::find()
template <class InputIterator, class T>
void find_print_result(InputIterator first, InputIterator last, const T& value) {
// call <algorithm> std::find()
auto p = find(first, last, value);
cout << "value " << value;
if (p == last) {
cout << " not found." << endl;
}
else {
cout << " found." << endl;
}
}
// Test std::find_if()
template <class InputIterator, class Predicate>
void find_if_print_result(InputIterator first, InputIterator last,
Predicate Pred, const string& Str) {
// call <algorithm> std::find_if()
auto p = find_if(first, last, Pred);
if (p == last) {
cout << Str << " not found." << endl;
}
else {
cout << "first " << Str << " found: " << *p << endl;
}
}
// Function to use as the UnaryPredicate argument to find_if() in this example
bool is_odd_int(int i) {
return ((i % 2) != 0);
}
int main()
{
// Test using a plain old array.
const int x[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
cout << "array x[] contents: ";
print(x);
// Using non-member std::begin()/std::end() to get input iterators for the plain old array.
cout << "Test std::find() with array..." << endl;
find_print_result(begin(x), end(x), 10);
find_print_result(begin(x), end(x), 42);
cout << "Test std::find_if() with array..." << endl;
find_if_print_result(begin(x), end(x), is_odd_int, "odd integer"); // function name
find_if_print_result(begin(x), end(x), // lambda
[](int i){ return ((i % 2) == 0); }, "even integer");
// Test using a vector.
vector<int> v;
for (int i = 0; i < 10; ++i) {
v.push_back((i + 1) * 10);
}
cout << endl << "vector v contents: ";
print(v);
cout << "Test std::find() with vector..." << endl;
find_print_result(v.begin(), v.end(), 20);
find_print_result(v.begin(), v.end(), 12);
cout << "Test std::find_if() with vector..." << endl;
find_if_print_result(v.begin(), v.end(), is_odd_int, "odd integer");
find_if_print_result(v.begin(), v.end(), // lambda
[](int i){ return ((i % 2) == 0); }, "even integer");
}
result:
示例结果
所以
find_if(input.begin(), input.end(), [](int ch) { return !isspace(ch); })表示找到字符串里按照begin-end方向第一个非空格位置。find_if(input.rbegin(), input.rend(), [](int ch) { return !isspace(ch); }).base()表示找到字符串里按照rbegin-rend方向第一个非空格位置。-
补充：调用reverse_iterator的base成员函数可以产生“对应的”iterator，由于所有的 erase 函数都只接受正向迭代器 iterator，所以在进行反向遍历删除元素时，首先需要将 reverse_iterator 转换为 iterator，在这里我只说明一点，两者相差一个元素，从一个反向迭代器获得对应的正向迭代器需要使用 base() 方法。如下图所示：ri 是指向元素3的反向迭代器，而 i 是 ri.base() 所得到的正想迭代器。详细解释。
base()函数效果
begin() 返回指向指向vector起始位置迭代器
end() 返回指向当前vector末尾元素的下一位置的迭代器
rbegin() 返回指向当前 vector 对象中最后一个元素的逆序迭代器。
rend() 返回逆序迭代器，它指向当前 vector 对象的第一个元素前面的位置
比较 begin/end 和 rbegin/rend 迭代器
- 最后测了很多例子，才弄明白。
-
总结string::erase(begin,end) 函数
不删除end处的值. 平常erase的end都是一个字符串最后一个字符的下一个位置，所以确实删除了整个字符串。(rbegin-rend方向第一个非空格位置).base()
代表后一个位置的值
- 可以在 stringToIntegerVector函数中，处理完trimLeftTrailingSpace和trimRightTrailingSpace后添加
cout << input << input.length() << endl;测试一番得到下面的例子：
测试左右函数处理
- substr(1, input.length() - 2);// 结合2的结果,就好理解去除两端
[ ]所剩子串
- substr(1, input.length() - 2);// 结合2的结果,就好理解去除两端
4.如何理解:基于“stringstream+getline”实现字符串分割
stringstream ss;
ss.str(input);
string item;
char delim = ',';
while (getline(ss, item, delim)) {
output.push_back(stoi(item));
}
getline()
这里没有count，
实现getline(有字符串流，得到字符串，分隔符)
stringstream
