題目：給定兩個非空鏈表來表示兩個非負(fù)整數(shù)瞳抓。位數(shù)按照逆序方式存儲，它們的每個節(jié)點只存儲單個數(shù)字伏恐。將兩數(shù)相加返回一個新的鏈表孩哑。
你可以假設(shè)除了數(shù)字 0 之外，這兩個數(shù)字都不會以零開頭翠桦。
示例：
輸入：[2,4,3]
[5,6,4]
,
輸出：[7,0,8]
原因：342 + 465 = 807
輸入：[5]
[5]
,
輸出：[0,1]
原因：5+5=10
分析：
- 鏈表對應(yīng)結(jié)點相加時增加前一個結(jié)點的進(jìn)位臭笆，并保存下一個結(jié)點的進(jìn)位；除法得進(jìn)位秤掌，模得結(jié)果愁铺。
- 兩個鏈表長度不一致時，要處理較長鏈表剩余的高位和進(jìn)位計算的值闻鉴；
- 如果最高位計算時還產(chǎn)生進(jìn)位茵乱，則還需要添加一個額外結(jié)點。
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]此例在死循環(huán)斤贰，以下兩處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 ) 目前提交最快的，我轉(zhuǎn)成c++反而更慢了 ┏┛┗┓
(c++573ms)
- 思想：盡量不創(chuàng)建節(jié)點直接用現(xiàn)有的結(jié)點
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一直記錄著添加的節(jié)點
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( )
- 下面函數(shù)理解
分別從左右各兩端消除輸入時空格：
//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表達(dá)式
返回：用于引用范圍[first,last] 中滿足謂詞(Predicate pred)所指定條件的元素
lambda組成
不理解的話次询，把示例代碼運行一遍(主要是區(qū)別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:
示例結(jié)果
所以
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方向第一個非空格位置屯吊。-
補(bǔ)充：調(diào)用reverse_iterator的base成員函數(shù)可以產(chǎn)生“對應(yīng)的”iterator送巡，由于所有的 erase 函數(shù)都只接受正向迭代器 iterator，所以在進(jìn)行反向遍歷刪除元素時盒卸，首先需要將 reverse_iterator 轉(zhuǎn)換為 iterator骗爆，在這里我只說明一點，兩者相差一個元素蔽介，從一個反向迭代器獲得對應(yīng)的正向迭代器需要使用 base() 方法摘投。如下圖所示：ri 是指向元素3的反向迭代器，而 i 是 ri.base() 所得到的正想迭代器虹蓄。詳細(xì)解釋犀呼。
base()函數(shù)效果
begin() 返回指向指向vector起始位置迭代器
end() 返回指向當(dāng)前vector末尾元素的下一位置的迭代器
rbegin() 返回指向當(dāng)前 vector 對象中最后一個元素的逆序迭代器。
rend() 返回逆序迭代器武花，它指向當(dāng)前 vector 對象的第一個元素前面的位置
比較 begin/end 和 rbegin/rend 迭代器
- 最后測了很多例子圆凰，才弄明白。
-
總結(jié)string::erase(begin,end) 函數(shù)
不刪除end處的值. 平常erase的end都是一個字符串最后一個字符的下一個位置体箕，所以確實刪除了整個字符串专钉。(rbegin-rend方向第一個非空格位置).base()
代表后一個位置的值
- 可以在 stringToIntegerVector函數(shù)中挑童，處理完trimLeftTrailingSpace和trimRightTrailingSpace后添加
cout << input << input.length() << endl;測試一番得到下面的例子：
測試左右函數(shù)處理
- substr(1, input.length() - 2);// 結(jié)合2的結(jié)果,就好理解去除兩端
[ ]所剩子串
- substr(1, input.length() - 2);// 結(jié)合2的結(jié)果,就好理解去除兩端
4.如何理解:基于“stringstream+getline”實現(xiàn)字符串分割
stringstream ss;
ss.str(input);
string item;
char delim = ',';
while (getline(ss, item, delim)) {
output.push_back(stoi(item));
}
getline()
這里沒有count，
實現(xiàn)getline(有字符串流跃须，得到字符串站叼，分隔符)
stringstream
