楼主: wrj5518
跳转到指定楼层
上一主题 下一主题
收起左侧

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

🔗
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
回复

使用道具 举报

🔗
锦木千束 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
回复

使用道具 举报

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

本版积分规则

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