一亩三分地论坛

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

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

FB店面

[复制链接] |试试Instant~ |关注本帖
lby8833 发表于 2015-3-29 09:11:35 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 全职@Facebook - 猎头 - 技术电面 |Other在职跳槽

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

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

x
Leetcode上那道String Multiplication的类似题。-google 1point3acres
. 鍥磋鎴戜滑@1point 3 acres
ericzeze 发表于 2015-3-30 01:53:44 | 显示全部楼层
yuxrose 发表于 2015-3-29 13:16
但我还是不很明白为什么array比string更efficient。。。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
我用string写的solution和你的一样,
看到网上 ...

面试官的意思可能是说因为Java String是不可改变的对象,每次对String类型修改的时候都要生成新对象,操作起来更费时间,如果用Array或者StringBuilder来做的话消耗时间更短。
回复 支持 1 反对 0

使用道具 举报

yuxrose 发表于 2015-3-29 10:10:15 | 显示全部楼层
lz请问题目给的两个乘数是存在string里还是存在array里?我记得看过一个面经说这题用array比用string much faster,能分享一下你的想法吗?
回复 支持 反对

使用道具 举报

 楼主| lby8833 发表于 2015-3-29 10:16:47 | 显示全部楼层
yuxrose 发表于 2015-3-29 10:10
lz请问题目给的两个乘数是存在string里还是存在array里?我记得看过一个面经说这题用array比用string much  ...

这个确实值得讨论一下,我是用的一个int array存每次算出来的数,再mod 10,处理完0之后再返回string,他当时给我是一个generic type,<T> multiply(<T> t1, <T> t2), 我当时就思维惯性用string来代替,后来被面试官纠正讨论为什么用string还是别的data structure之类的,反正communicate的不大好,后来挂掉了- - 总体感觉真的要写得很熟才行,因为时间很短:-(
回复 支持 反对

使用道具 举报

yuxrose 发表于 2015-3-29 13:16:44 | 显示全部楼层
lby8833 发表于 2015-3-29 10:16. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
这个确实值得讨论一下,我是用的一个int array存每次算出来的数,再mod 10,处理完0之后再返回string,他 ...

但我还是不很明白为什么array比string更efficient。。。
我用string写的solution和你的一样,
看到网上一个用array的这么写的
public static String multiply2(String num1, String num2){
                if(num1 == null || num2 == null || num1.length() == 0 || num2.length() == 0). more info on 1point3acres.com
                        return null;. 1point 3acres 璁哄潧

                if(num1.equals("0") || num2.equals("0"))
                        return "0";                       
                int len1 = num1.length();
                int[] N1 = new int[len1];. 鍥磋鎴戜滑@1point 3 acres
                int len2 = num2.length();
                int[] N2 = new int[len2];
                int len3 = len1 + len2;. more info on 1point3acres.com
                int[] result = new int[len3];
                for(int i = 0; i < num1.length(); i++){
                        N1 = num1.charAt(i) - '0';
                } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                for(int i = 0; i < num2.length(); i++){
                        N2 = num2.charAt(i) - '0';
                }
               
                for(int i = 0; i < len1; i++){
                        for(int j = 0; j < len2; j++){
                                result[i + j + 1] += N1 * N2[j];
                        }
                }
                StringBuilder sb = new StringBuilder();.鐣欏璁哄潧-涓浜-涓夊垎鍦
                for(int k = len1 + len2 - 1; k >= 0; k--){
                        sb.append((char)(result[k] % 10 + '0'));
                        if(k > 0){
                                result[k - 1] += result[k] / 10;
                        }
                }
                int startPos = sb.charAt(sb.length() - 1) == '0' ? 1 : 0;
                String s = sb.reverse().substring(startPos, sb.length());
                return s;
        }
.1point3acres缃
.鏈枃鍘熷垱鑷1point3acres璁哄潧
这个当然更好理解,计算的也更方便,不易出错,但具体到复杂度,和string
并没有区别啊,都是space m + n,  time m * n, array access a 或者是
string.charAt(i)都是O(1)的复杂度。。。不知道为什么一定要纠结用array啊

回复 支持 反对

使用道具 举报

likenisha 发表于 2015-3-31 05:25:01 | 显示全部楼层
请问类似的话,哪里不太一样呢
回复 支持 反对

使用道具 举报

 楼主| lby8833 发表于 2015-3-31 05:29:09 | 显示全部楼层
likenisha 发表于 2015-3-31 05:25
请问类似的话,哪里不太一样呢

就是signature不一样,没有给定type是string
回复 支持 反对

使用道具 举报

likenisha 发表于 2015-3-31 22:34:35 | 显示全部楼层
lby8833 发表于 2015-3-30 16:29
就是signature不一样,没有给定type是string

那要转换成String么。。。int 或者 long么
回复 支持 反对

使用道具 举报

 楼主| lby8833 发表于 2015-3-31 23:19:28 | 显示全部楼层
likenisha 发表于 2015-3-31 22:34. from: 1point3acres.com/bbs
那要转换成String么。。。int 或者 long么

我当时就直接说用一些data structure可以用,char array啊,list神马的,可能我也没分析好各种优缺点。对啊,因为他说了,可能是个big integer,但既然给了统一的类型,输入选什么,输出就选什么咯。
回复 支持 反对

使用道具 举报

likenisha 发表于 2015-4-2 07:39:49 | 显示全部楼层
不明白为什么还用数据结构。。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 00:58

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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