一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 969|回复: 12
收起左侧

[CareerCup] 【第四轮】4.6 - 4.12 Career Cup 2.5

[复制链接] |试试Instant~ |关注本帖
pure0909 发表于 2015-4-7 01:46:26 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
2.5 You have two numbers represented by a linked list, where each node contains a
single digit. The digits are stored in reverse order, such that the Ts digit is at the
head of the list. Write a function that adds the two numbers and returns the sum
as a linked list.
EXAMPLE
Input: (7-> 1 -> 6) + (5 -> 9 -> 2).That is, 617 + 295.
Output: 2 -> 1 -> 9.That is, 912.
FOLLOW UP
Suppose the digits are stored in forward order. Repeat the above problem.
EXAMPLE
Input: (6 -> 1 -> 7) + (2 -> 9 -> 5).That is, 617 + 295.
Output: 9 -> 1 -> 2.That is, 912

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link]
【test case】(optional,如果觉得比较好,欢迎贴出来分享)

Notice:
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子,除了贴解法,欢迎探讨各种follow up questions,集思广益
4、任何未尽之处,欢迎回报名帖提问,我会进一步作出修改


laonong15 发表于 2015-4-8 23:41:01 | 显示全部楼层
【解题思路】
use an  variable to  store the carry,  from the second one  add the carry  and two numbers, if one  list reach the end  copy the other list's rest
O(m+n) O(M+n)

Follow up   :

use two stacks  to push the  two linked List  and pop up  them and  calculate,
if the stack is not  allowed,  we could do  two temp Linklist  to reverse the   two original  link list  then calculate.   below gives the  reverse Linked list method.  

Note :  review the book solutions  I dont think it is  better than mine but   it is the book solution
【时间复杂度】
O(n)
【空间复杂度】
O(n)
【gist link]
https://gist.github.com/michaelniu/c75fef84cbb5c15db731
【test case】
https://gist.github.com/michaelniu/c75fef84cbb5c15db731(main)
回复 支持 反对

使用道具 举报

JamesJi 发表于 2015-4-9 22:45:42 | 显示全部楼层
laonong15 发表于 2015-4-8 10:41
【解题思路】
use an  variable to  store the carry,  from the second one  add the carry  and two num ...

可以详细解释一下follow up的思路做法吗?我没有看很明白
回复 支持 反对

使用道具 举报

laonong15 发表于 2015-4-10 03:30:24 | 显示全部楼层
JamesJi 发表于 2015-4-9 22:45
可以详细解释一下follow up的思路做法吗?我没有看很明白

lets talk about  the stack  solution
linklist one is  1->2->3-->4    linklist two is  5->6-->7   push to  stack as below   ,  sum with   carray   from  top  to bottom  and put to a new result list.


                               
登录/注册后可看大图


The reverse  solution is easy to understand

Thanks

回复 支持 反对

使用道具 举报

slaink 发表于 2015-4-11 03:48:24 | 显示全部楼层
【解题思路】
When digits are stored reversely, traverse through the list sum all numbers together by p * 10^(i), where i is the index in the linked list, starting at 0.
When digits are stored sequentially, traverse once to determine the length L, then all all numbers together by p * 10^(L-i), where L is the length of the list and i is the index starting at 0.
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link] https://github.com/bxshi/intervi ... sum_number_list.cpp
【test case】(optional,如果觉得比较好,欢迎贴出来分享)https://github.com/bxshi/intervi ... c/test/2_5_test.cpp
回复 支持 反对

使用道具 举报

alikewmk 发表于 2015-4-12 04:37:11 | 显示全部楼层
【解题思路】
同时遍历两个list, 用加数list存储结果
1.要特别注意两个list的长度不同,我的解决方法是建立数值为0的节点并插到短的list末尾
2.要注意最后一个进位

Follow up:
将两个list反转,按之前的方式相加,然后把结果再反转

【时间复杂度】
O(n), n= the length of the larger list
Followup: O(n)
【空间复杂度】
O(n), n= the length of the larger list
Followup: O(n)
【gist link】
https://gist.github.com/alikewmk ... 5-addnodedigit-java
【test case】

9 9 9
9 9
8 9 0 1

9 9
9 9 9 9
8 9 0 0 1

Follow up:

3 5
3 5 2 7
3 5 6 2
回复 支持 反对

使用道具 举报

coperdli 发表于 2015-4-13 09:07:04 | 显示全部楼层
思路:同时遍历两个链表,将对应位置的相加,并加上前一节点相加的进位。
时间复杂度:O(max(m, n))
空间复杂度:由于在处理过程中将结果都存储到第一个链表中,故而O(1)
code snippet & test case: https://gist.github.com/coperd/93fe35d8b92414034406
Follow up: 目前只想到将链表先翻转一下,然后一样的处理,时间复杂度没有增加。
回复 支持 反对

使用道具 举报

A30041839 发表于 2015-4-13 22:01:12 | 显示全部楼层
[solution]
add each digit together and store the sum to the result linked list, keep a flag number to indicate whether the sum generates a carry.
[time]
O(max(m,n))
[space]
O(1)
[gist]
https://gist.github.com/A30041839/83a798443048751267bd

FOLLOW UP:
[solution]
traverse the two linked list and store the elements into stacks, then pop up the two stacks to add numbers together, and store the sum to a result stack.
[time]
O(max(m,n))
[space]
O(m+n)
[gist]
https://gist.github.com/A30041839/83a798443048751267bd
回复 支持 反对

使用道具 举报

iker01 发表于 2015-4-14 09:22:31 | 显示全部楼层
【解题思路】
# use one extra linked list to store the sum
# traverse two original linked list to find the sum for each digit
# pass the carry one forward
【时间复杂度】
O(max(m, n))
【空间复杂度】
O(max(m, n))
【gist link】
https://gist.github.com/zhangjiang2013/9189cc74bba08a022d5b
回复 支持 反对

使用道具 举报

苏DsL 发表于 2015-4-15 21:34:38 | 显示全部楼层
laonong15 发表于 2015-4-10 03:30
lets talk about  the stack  solution
linklist one is  1->2->3-->4    linklist two is  5->6-->7   ...

stack的方法确实比较巧,但是空间复杂度跟反转链表是一样的,然后stack的方法算到最后还是要反转结果链表,所以感觉还是书上的方法效率高些
回复 支持 反对

使用道具 举报

sevenwonder 发表于 2015-4-22 11:33:09 | 显示全部楼层
【解题思路】
  use new list to store the sum of two list, note plus carry.
  follow up:
reverse linked list first and sum together then reverse the result.
【时间复杂度】
O(max(m, n))
【空间复杂度】
O(max(m, n))
【gist link】
https://gist.github.com/songpu2015617/e917b568f3360e2ab486
回复 支持 反对

使用道具 举报

Godbless 发表于 2015-5-30 09:56:18 | 显示全部楼层
【解题思路】Recursively add two lists from head to the end, and append results to a new list from head to the end
【时间复杂度】O(max(m,n))
【空间复杂度】O(max(m,n))
【gist link] https://github.com/StephenWeiXu/ ... aster/Chap2/2_5.cpp
【test case】(optional,如果觉得比较好,欢迎贴出来分享)
回复 支持 反对

使用道具 举报

窗外一棵树 发表于 2015-7-15 01:49:42 | 显示全部楼层
我感觉最直观的思路是 分别遍历两个list,把两个数字还原,然后相加,再放到一个新的list里。

用的时间也是O(n),为啥没人这么做呢,这个做法有什么问题吗
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 19:11

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表