一亩三分地论坛

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

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

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

[复制链接] |试试Instant~ |关注本帖
wrj5518 发表于 2014-6-23 00:00:07 | 显示全部楼层 |阅读模式

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

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

x
本帖最后由 wrj5518 于 2014-6-23 09:33 编辑

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).Thatis,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).Thatis,617 + 295.
Output: 9 -> 1 -> 2.That is, 912.

回复解法可以按照以下格式来
【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------optional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】


Notice:
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子,除了贴解法,欢迎讨论,集思广益
4、任何未尽之处,欢迎回报名帖提问,我会进一步作出修改。
chouclee 发表于 2014-6-23 12:57:27 | 显示全部楼层
【解题思路】用两个iterator,从链表的第一位,每两个数和前一个的进位相加,结果取个位add 进结果的链表,更新进位。
【时间复杂度】O(m+n)
【空间复杂度】O(max(m,n))
【gist link】https://gist.github.com/chouclee/97d1aa3bf0461fa82642
回复 支持 反对

使用道具 举报

readman 发表于 2014-6-23 16:00:42 | 显示全部楼层
【解题思路】妈的, 花了我1个多小时, 终于写了个很短的...
【时间复杂度】O(m+n)
【空间复杂度】O(max(m,n))
【gist link】https://gist.github.com/gaoyike/e150277cbd245298488a
回复 支持 反对

使用道具 举报

bearkino 发表于 2014-6-25 01:28:35 | 显示全部楼层
【解题思路】
比较暴力的写了很多判断条件,主要就是考虑进位和list的排序,使用了addlast方法,虽然不是很好,但是个人觉得比较易懂。
【时间复杂度】
O(max(m,n))
【空间复杂度】
O(max(m,n))
【gist link】
https://gist.github.com/UncleGarden/15892158c55be826ecb0

回复 支持 反对

使用道具 举报

wilbert 发表于 2014-6-25 05:58:13 | 显示全部楼层
【解题思路】
add two lists from the beginning, keep track of carrier.
FOLLOWUP: count the length of the two lists first, add 0s for shorter list at the beginning, recursively call addLast()
【时间复杂度】
O(M+N)
【空间复杂度】
O(max(M,N))
【gist link】
https://gist.github.com/iwilbert/d0ef097a92c9ce096e95
回复 支持 反对

使用道具 举报

grassgigi 发表于 2014-6-25 11:10:18 | 显示全部楼层
本帖最后由 grassgigi 于 2014-6-25 11:32 编辑

【解题思路】
- Go through list, add digit by digit
- Keep tracking the overflow value

Follow up
- reverse the input list, use original add function, add reverse answer back

【时间复杂度】
O(M +  N)

【空间复杂度】
O(max(M,N))

【gist link】
https://gist.github.com/chrislukkk/50f3322f76256c71552a
回复 支持 反对

使用道具 举报

兰橘清檬 发表于 2014-6-27 06:57:18 | 显示全部楼层
本帖最后由 兰橘清檬 于 2014-6-26 16:09 编辑

【解题思路】
新建 list,若 a, b 或进位任一不为0,则产生新节点添在后面。
follow up : 先将两个 list 补充成一样长,然后利用递归计算
【时间复杂度】
O(m+n)
【空间复杂度】
O(Max(m,n))
【gist link】https://gist.github.com/JoyceeLee/6ff64e9e5b7dab0c85b2



回复 支持 反对

使用道具 举报

林微熙 发表于 2014-6-27 12:30:19 | 显示全部楼层
【解题思路】
l1,l2为空,则为空;不为空,相加,按法则计算
【时间复杂度】
O(m+n)
【空间复杂度】
O(Max(m,n))
【gist link】https://gist.github.com/hilda8519/f5d60e652c48785b924a
回复 支持 反对

使用道具 举报

头像被屏蔽
serolins 发表于 2014-6-28 06:17:07 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

jyh橘子 发表于 2014-6-28 08:06:43 | 显示全部楼层
本帖最后由 jyh橘子 于 2014-6-28 08:08 编辑

【解题思路】  for the follow up question, we need to firstly compare the length of two linkedlist and pad zeroes at the front of the longer one.   Then use recursive method to calculate the sum
【时间复杂度】
O(Max(m,n))
【空间复杂度】
O(Max(m,n))
【gist link】  [url=https://gist.github.com/jyhjuzi/2c61556d5cbe6857a23d][/url]
回复 支持 反对

使用道具 举报

habina 发表于 2014-6-28 15:37:21 | 显示全部楼层
============================================================================
Solution        : add cooresponding value of two linkedlist and mark down the carry in
                   FolloUp:
                   using recusion to add two numbers and return carry
                   and save result in a list
                   reverse list and save to a linkedlist
Time Complexity : O(n)
Space Complexity: O(m, n)
Gist Link       : https://gist.github.com/habina/a03e10e925ef43d95e71
============================================================================
回复 支持 反对

使用道具 举报

bitcpf 发表于 2014-6-28 22:05:38 | 显示全部楼层
【解题思路】Add list from the head one by one, generate a new list to store the result
【时间复杂度】O(M+N)
【空间复杂度】O(max(M,N))
【gist link】https://gist.github.com/bitcpf/b4233e9747980b42fdb5
回复 支持 反对

使用道具 举报

aloncgo 发表于 2014-6-28 23:10:21 | 显示全部楼层
【解题思路】没思路...先发前半部分的,   FollowUP写了半天老出问题一怒之下删掉了....  之后补上吧, 头痛,睡觉去了
【时间复杂度】O(M+N)
【空间复杂度】O(MAX(M, N))
【gist link】https://gist.github.com/weazord/65bb39b3ae739b7a5b10
回复 支持 反对

使用道具 举报

pud 发表于 2014-6-29 02:26:57 | 显示全部楼层
【解题思路】写的有点复杂,很多判断条件。分别判断l1,l2,carrier 空的情况。  folow up还没写,应该是carrier加在node前面有点麻烦把
【时间复杂度】O(M+N)
【空间复杂度】O(MAX(M, N))
【gist link】
https://gist.github.com/yokiy/62724b32df4c2dc58121
回复 支持 反对

使用道具 举报

heycinderella 发表于 2014-6-29 08:45:40 | 显示全部楼层

这题解法太多,完全写吐了啊,就写两个自己想的方法吧

【解题思路】Iterative,从头扫到尾,carry一个进位的int一起相加
【时间复杂度】O(max(M,N))
【空间复杂度】O(max(M,N))

FOLLOW UP:
【解题思路】把list反转过来然后和上面一样,最后再把结果反过来。
【时间复杂度】 O(m+n)
【空间复杂度】O(max(m,n)) if we are allowed to mutate the original
         * lists when reverting them (otherwise space is O(m+n) not implemented

【gist link】
https://gist.github.com/XiaoxiaoLi/88bd156d235d6a6e7d08
回复 支持 反对

使用道具 举报

Neal 发表于 2014-6-29 12:20:22 | 显示全部楼层
【解题思路】just normal sum algorithm. FOLLOW UP: reverse, sum and recover
【时间复杂度】O(max(N,M))
【空间复杂度】O(1), constant extra space
【gist link】https://gist.github.com/nealhu/19b6891766bd9ab4b83a
回复 支持 反对

使用道具 举报

jing0328 发表于 2014-6-29 16:51:23 | 显示全部楼层
【解题思路】first read number in the list in reverse order and sum up two numbers, then store the result in a list in reverse order   
Follow up: read number in the list in order and sum them up, then store the result into a list using previous method, then reverse this list
【时间复杂度】O(m+n)
【空间复杂度】O(max(m,n))
【gist link】https://gist.github.com/startupjing/29e961b17dcf6b11018e
回复 支持 反对

使用道具 举报

donnice 发表于 2014-6-30 04:51:57 | 显示全部楼层
【解题思路】
在生成第一个linkedlist时在头上插入新元素,之后把输出结果分为两个数后相加,再把答案转化为String,利用charAt分别读取每一位后插入新list后倒序输出
没有写follow up,二者惟一的区别就是create一个是输入0,另一个输入目标List的长度
【时间复杂度】
O(m+n)
【空间复杂度】
O(max(m,n))
【gist link】直接代码
import java.util.*;

class Node{
        private Node next;
        private Object data;
       
        public Node(){
                this(null,null);
        }
        public Node(Object data){
                this(data,null);
        }
        public Node(Object data, Node next){
                this.data = data;
                this.next = next;
        }
        public Object getData(){
                return data;
        }
        public void setData(Object data){
                this.data = data;
        }
        public Node getNext(){
                return next;
        }
        public void setNext(Node next){
                this.next = next;
        }
}

class LinkedList{
        Node head = new Node();
        Scanner sc = new Scanner(System.in);
        public void create(int k){
                for(int x=sc.nextInt();x!=0;x = sc.nextInt())
                        insert(0,x);
        }
        public void insert(int i, Object x){
                Node p = head;
                int j = -1;
                while(p.getNext()!=null && j<i-1){
                        p = p.getNext();
                        j++;       
                }
                Node s = new Node(x);
                s.setNext(p.getNext());
                p.setNext(s);
        }

        public void display(){
                Node p = head.getNext();
                while(p!=null){
                        System.out.print(p.getData()+" ");
                        p = p.getNext();
                }
        }

        public int getLength(){
                Node p = head.getNext();
                int s = 0;
                while(p!=null){
                        s++;
                        p = p.getNext();
                }
                return s;
        }

        public int add(int b){
                Node p = head.getNext();
                int j = 0;
                int sum1 = 0;
                int t = 0;
                int c = b-1;
                int sum2 = 0;
                while(j<b){
                        t = (int)Math.pow(10,c);
                        sum1 +=(int)p.getData()*t;
                        p = p.getNext();
                        c--;
                        j++;
                }
                t = 0;
                c = b-1;
                while(p!=null){
                        t = (int)Math.pow(10,c);
                        sum2 +=(int)p.getData()*t;
                        p = p.getNext();
                        c--;
                        j++;
                }
                return sum1+sum2;
        }
}

public class Q2_5{
        public static void main(String[] agrs){
                LinkedList L = new LinkedList();
                LinkedList M = new LinkedList();
                Scanner sc = new Scanner(System.in);
                System.out.print("please input elements, 0 as an End:");
                L.create(0);
                L.display();
                System.out.println();
                int a = L.getLength();
                String r = String.valueOf(L.add(a/2));
                int j = r.length()-1;
                int s = 0;
                while(s<=j){
                        M.insert(0,r.charAt(s));
                        s++;
                }
                M.display();
                               
        }
}
【Test case】
in:8->7->6->5->4->3->2->1
out:6->8->0->3->1
follow up懒得写了,就是再新生成两个linkedlist(如K和N),K.create(L.length)就可以了
回复 支持 反对

使用道具 举报

心焰 发表于 2014-6-30 08:54:53 | 显示全部楼层
【解题思路】
Give each digit the right weight, then we get two numbers. (singlelinked is ok)
1. In case A, just iterate two list once
2. In case B, need to iterate them twice since need to get their length
【时间复杂度】O(m+n)
【空间复杂度】O(1)
【gist link】https://github.com/FinalF/CarrerUp/blob/master/addOperation.java
回复 支持 反对

使用道具 举报

ivycheung1208 发表于 2014-6-30 09:15:27 | 显示全部楼层
本帖最后由 ivycheung1208 于 2014-6-29 20:18 编辑

【解题思路】
zero padding the shorter list, then add by digit together with carry bit. DON'T forget the last carry bit!
FOLLOW UP:
It's impossible to proceed with prediction of carry bit, thus 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
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

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

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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