123
返回列表 发新帖
楼主: wrj5518
跳转到指定楼层
上一主题 下一主题
收起左侧

[CareerCup] 【第三轮】6.23-6.29 CareerCup 2.5

🔗
ivycheung1208 2014-6-30 09:15:45 | 只看该作者
全局:
【解题思路】
add by digit, keep the carry
FOLLOW UP:
considering the carry bit, it's impossible to proceed with prediction of carry bit, to avoid recursion, reverse the lists and perform reverse addition as implemented before, then reverse the summation and return
【时间复杂度】
O(N)
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/5832983c129d537298d5
【test case】
9999 + 1 = 10000
回复

使用道具 举报

🔗
jason51122 2014-7-1 14:45:15 | 只看该作者
全局:
本帖最后由 jason51122 于 2014-7-1 15:02 编辑

【解题思路】Reverse 2 linked list. Then add two linked lists as usual and reverse the result at end.
【时间复杂度】O(N)
【空间复杂度】O(N)
【gist link】https://gist.github.com/jason51122/1337cd3ec53243326f01
回复

使用道具 举报

🔗
guchang 2014-7-4 08:51:35 | 只看该作者
全局:
【解题思路】用同步遍历两个链表,各取出一个数,与进位做sum,保存carry。需要注意99+1.的情况。最高位还有1的情况。
一大早写状态差,写得乱七八糟。
Follow up: 待会儿写
【时间复杂度】O(m+n)
【空间复杂度】O(max(m,n))
【gist link】https://gist.github.com/guchang/d96d2d5bf2b8a6c67c7d
回复

使用道具 举报

🔗
tonygxxx1212 2014-7-4 11:54:50 | 只看该作者
全局:
【解题思路】
  list->numer, add two number, sum->list
  list 初始化用的自己的 initialize 函数,要用到数组
【时间复杂度】
O(N)
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/xun-gong/6e06f9a82676012ab7aa
回复

使用道具 举报

🔗
whiteflower 2014-7-5 09:39:38 | 只看该作者
全局:
【解题思路】
reverse the two lists, and invoke addLists() to get
sumList, and reverse sumList to get correct result
【时间复杂度】O(max(M, N))
【空间复杂度】O(M + N + max(M, N)) (.....I'm not sure.......)
【gist link】https://gist.github.com/JoshuaTang/f71459369611d69d7354
回复

使用道具 举报

🔗
Tsien 2014-7-6 23:53:37 | 只看该作者
全局:
//【解题思路】
//从头到尾遍历两条链,一位一位地相加,若有进位,则记录下,加到下一位。
//【时间复杂度】
//O(n+m)
//【空间复杂度】
//O(1)
//【gist link】
https://gist.github.com/Tsien/2b657a0bc23f0ca63350
回复

使用道具 举报

全局:
【解题思路】
traverse two list at the same time and use the sum to create a new node

Follow Up: just reverse two list, use the previous method to add two list and reverse the result

【时间复杂度】
O(max(m, n))

【空间复杂度】
O(max(m, n))

【gist link】
https://gist.github.com/happyWinner/ed0fd5ca340f8f1cbcf8

回复

使用道具 举报

🔗
daisyang 2014-8-16 13:52:17 | 只看该作者
全局:
follow up学习了下前面童鞋们的,用递归从后面开始加
时间复杂度 O(N)
空间复杂度: O(1)

https://gist.github.com/daisyang/5521dd686dcb792ff86d
回复

使用道具 举报

🔗
水逼一枚 2014-8-27 01:31:48 | 只看该作者
全局:
想问一下这个题大家有没有考虑, 两个运算数的digits数目不一样的情况啊?感觉各种情况考虑完,写起来还挺复杂。
可能是因为我的Node定义不太合理?
回复

使用道具 举报

🔗
sanguine 2014-12-30 06:24:00 | 只看该作者
全局:
Idea: add two lists from the beginning, keep track of carrier

Time Complexity: O(m+n)
Space Complexity: O(max(m, n))

Solution2
Improvement: reduce the space complexity if we can change the original linkedList

if we first calculate the max length of the two input linkedList and using the max length LinkedList, as the result, we can reduce the space complexity to be O(1)

Time Complexity: O(m+n)
Space Complexity: O(max(m, n) – min(m, n))

Solution3
IDEA: Using Recursion

Improvement: same way, if we can modify the original LinkedList, we can implement it using Recursive within O(1) space complexity

Follow Up
Solution1
Idea: first reverse the two input linkedList, using addLinkedList() method and reverse the result list.

Solution2
Idea: Recursive algorithm, same with the idea in book

Notice
Consider the boundary
Consider the situation (9 -> 9 -> 9) + (2). Which the result will have four node rather than three
Make the code more cleanly is also very important.
create a virtual node and return the node.next can avoid to consider the null situation.
using ((list1 != null) ? list1.val : 0) rather than if-statement can more the code more clean.

Code:
http://www.jyuan92.com/post-465
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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