j*****y 发帖数: 1071 | 1 50分钟。
就一道题。 比如对于 数组 [1, 3, 9, 9] ,表示 1399, 实现 加 1
面试官一直让不断的优化。
后面8分钟就闲聊 project 了。 |
P**********g 发帖数: 30 | 2 问个菜菜的问题。
电面是开着电话免提,写code...? |
j*****y 发帖数: 1071 | 3 我开着手机免提的。前面是电脑。下巴下面是手机
【在 P**********g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 问个菜菜的问题。 : 电面是开着电话免提,写code...?
|
P**********g 发帖数: 30 | 4 就是只有一个大数加法的实现?
lz 你 onsite 肯定没问题啦,cong一个 |
j*****y 发帖数: 1071 | 5 多谢,多谢 :)
这个比大数加法应该要容易很多,因为另外一个数只是 1.
【在 P**********g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 就是只有一个大数加法的实现? : lz 你 onsite 肯定没问题啦,cong一个
|
M********5 发帖数: 715 | |
j*****y 发帖数: 1071 | 7 多谢 :)
现在我发现 做完 leetcode OJ 离 优化code到最好的地步还差的好远。
【在 M********5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你运气真好,这个羡慕都羡慕不来。。。
|
c********t 发帖数: 5706 | 8 我想到的就是in-place 硬做,遇到数组越界,要重新开新空间
还有什么优化吗?
【在 j*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 50分钟。 : 就一道题。 比如对于 数组 [1, 3, 9, 9] ,表示 1399, 实现 加 1 : 面试官一直让不断的优化。 : 后面8分钟就闲聊 project 了。
|
j*****y 发帖数: 1071 | 9 中间的时候如果遇到了不进位的话,就 break
【在 c********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我想到的就是in-place 硬做,遇到数组越界,要重新开新空间 : 还有什么优化吗?
|
j*****y 发帖数: 1071 | 10 你这个in place 是很好的一个优化。
【在 c********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我想到的就是in-place 硬做,遇到数组越界,要重新开新空间 : 还有什么优化吗?
|
|
|
M********5 发帖数: 715 | 11 我也是这么想的,中间遇到不进位的时候就break,然后只要给出的数组不是9999这种
的,就不许要另外allocate space,如果是9999的话,那就另外做打算。。。是这样的
思路么?
【在 j*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 中间的时候如果遇到了不进位的话,就 break
|
c********t 发帖数: 5706 | 12 嗯,明白了。肯定on-site了,提前恭喜!
【在 j*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你这个in place 是很好的一个优化。
|
A*****i 发帖数: 3587 | 13 昨天google电面问个如何遍历DAP的题,也是不断优化啥的,挺简单
不知道最后为啥挂了,这些大公司面人的时候感觉很捉摸不透啊 |
j*****y 发帖数: 1071 | 14 对的。 :)
【在 M********5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我也是这么想的,中间遇到不进位的时候就break,然后只要给出的数组不是9999这种 : 的,就不许要另外allocate space,如果是9999的话,那就另外做打算。。。是这样的 : 思路么?
|
j*****y 发帖数: 1071 | 15 多谢多谢, 托您吉言 :)
【在 c********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 嗯,明白了。肯定on-site了,提前恭喜!
|
f*****e 发帖数: 2992 | 16 如果是二进制的话,是不是必须到2^32-1再进位?
【在 j*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 对的。 :)
|
j*****y 发帖数: 1071 | 17 不是二进制的表示。就是 0-9之间的 digit表示。
【在 f*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如果是二进制的话,是不是必须到2^32-1再进位?
|
r*****e 发帖数: 146 | 18 Bless! 应该进入下一轮了,弱问一句,一般G家的电话,要做几道题啊?
【在 j*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 50分钟。 : 就一道题。 比如对于 数组 [1, 3, 9, 9] ,表示 1399, 实现 加 1 : 面试官一直让不断的优化。 : 后面8分钟就闲聊 project 了。
|
r*****e 发帖数: 146 | 19 弱问一下,啥是DAP?
【在 A*****i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 昨天google电面问个如何遍历DAP的题,也是不断优化啥的,挺简单 : 不知道最后为啥挂了,这些大公司面人的时候感觉很捉摸不透啊
|
j*****y 发帖数: 1071 | 20 你说的是 DAG 吗?
【在 A*****i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 昨天google电面问个如何遍历DAP的题,也是不断优化啥的,挺简单 : 不知道最后为啥挂了,这些大公司面人的时候感觉很捉摸不透啊
|
|
|
j*****y 发帖数: 1071 | 21 多谢。 :)
我也不知道,可能看你水平,像我这种弱水平的,面试官也没有时间让你做两道题目。
【在 r*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Bless! 应该进入下一轮了,弱问一句,一般G家的电话,要做几道题啊?
|
B*******1 发帖数: 2454 | 22 你这道算法题用了多久时间啊? 50分钟就一道题?
【在 j*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 多谢。 :) : 我也不知道,可能看你水平,像我这种弱水平的,面试官也没有时间让你做两道题目。
|
j*****y 发帖数: 1071 | 23 我花了 20分钟写完,然后20分钟在提示下一步一步优化。
这40分钟就这一道题。
后面的时间就闲聊了。
【在 B*******1 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你这道算法题用了多久时间啊? 50分钟就一道题?
|
s**s 发帖数: 70 | |
j*****y 发帖数: 1071 | 25 多谢吉言 :)
【在 s**s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 祝onsite成功~
|
M********5 发帖数: 715 | 26 所以他是真的很幸运啦。。。这种东西嫉妒不来,咱们得move on。。。
【在 B*******1 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你这道算法题用了多久时间啊? 50分钟就一道题?
|
A*****i 发帖数: 3587 | 27 矮油我擦,一着急写错了,DAG,不是DAP
【在 r*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 弱问一下,啥是DAP?
|
s********l 发帖数: 998 | 28 只加一边1
还是没完没了的加啊?
【在 j*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 50分钟。 : 就一道题。 比如对于 数组 [1, 3, 9, 9] ,表示 1399, 实现 加 1 : 面试官一直让不断的优化。 : 后面8分钟就闲聊 project 了。
|
j*****y 发帖数: 1071 | 29 加一次 1
比如对于 19
计算 19 + 1
只不过 19存在数组里面而已
【在 s********l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 只加一边1 : 还是没完没了的加啊?
|
s********l 发帖数: 998 | 30 哦~ 这样子 thanks.
【在 j*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 加一次 1 : 比如对于 19 : 计算 19 + 1 : 只不过 19存在数组里面而已
|
|
|
s********l 发帖数: 998 | 31 你最后 优化成什么样子的了?
【在 j*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 50分钟。 : 就一道题。 比如对于 数组 [1, 3, 9, 9] ,表示 1399, 实现 加 1 : 面试官一直让不断的优化。 : 后面8分钟就闲聊 project 了。
|
s********l 发帖数: 998 | 32 这个 你最后优化成什么样了?
【在 A*****i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 昨天google电面问个如何遍历DAP的题,也是不断优化啥的,挺简单 : 不知道最后为啥挂了,这些大公司面人的时候感觉很捉摸不透啊
|
j*****y 发帖数: 1071 | 33 这是最后的 code
vector plusOne(vector &input)
{
if(input.size() == 0)
{
return vector(1, 1);
}
int remainder = 1;
for(int i = input.size() -1 ; i > -1; --i)
{
int tmp = input[i] + remainder;
if(tmp >= 10)
{
input[i] = tmp - 10;
remainder = 1;
}
esle
{
input[i] = tmp;
remainder = 0;
break;
}
}
if(remainder != 0)
{
vector tmp(1, remainder);
input.insert(input.begin(), tmp.begin(), tmp.end());
}
return input;
}
【在 s********l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你最后 优化成什么样子的了?
|
l*********8 发帖数: 4642 | 34 能不能把数字反过来存?
[9, 9,3, 1] 表示1399
【在 j*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这是最后的 code : vector plusOne(vector &input) : { : if(input.size() == 0) : { : return vector(1, 1); : } : : int remainder = 1; : for(int i = input.size() -1 ; i > -1; --i)
|
j*****y 发帖数: 1071 | 35 没有discuss这个 :)
【在 l*********8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 能不能把数字反过来存? : [9, 9,3, 1] 表示1399
|
s********l 发帖数: 998 | 36 这个好 多谢多谢
【在 j*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这是最后的 code : vector plusOne(vector &input) : { : if(input.size() == 0) : { : return vector(1, 1); : } : : int remainder = 1; : for(int i = input.size() -1 ; i > -1; --i)
|
j*****y 发帖数: 1071 | 37 可是刚才拷贝的时候,我发现了一个错误 :(
else 写成了 esle
【在 s********l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个好 多谢多谢
|
l*****a 发帖数: 14598 | 38 why input.size()==0, then u return 1?
if input==0, then u can return 1
【在 j*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这是最后的 code : vector plusOne(vector &input) : { : if(input.size() == 0) : { : return vector(1, 1); : } : : int remainder = 1; : for(int i = input.size() -1 ; i > -1; --i)
|
s********l 发帖数: 998 | 39 这个肯定不会有影响的~~
【在 j*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 可是刚才拷贝的时候,我发现了一个错误 :( : else 写成了 esle
|
j*****y 发帖数: 1071 | 40 多谢。 希望如此,托您吉言 :)
【在 s********l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个肯定不会有影响的~~
|
|
|
j*****y 发帖数: 1071 | 41 should return an array
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : why input.size()==0, then u return 1? : if input==0, then u can return 1
|
l*****a 发帖数: 14598 | 42 i mean since nothing in the input, why u return int [] a={1};
【在 j*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : should return an array
|
j*****y 发帖数: 1071 | 43 i asked him if it is OK to return [1] in this case, he gave yes.
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : i mean since nothing in the input, why u return int [] a={1};
|
l*****a 发帖数: 14598 | 44 why not throw something like illegalArgumentException?
【在 j*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : i asked him if it is OK to return [1] in this case, he gave yes.
|
j*****y 发帖数: 1071 | 45 too complicated to me :)
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : why not throw something like illegalArgumentException?
|
j*****y 发帖数: 1071 | 46 bless.
昨天电面的今天就给消息了 ?
【在 A*****i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 昨天google电面问个如何遍历DAP的题,也是不断优化啥的,挺简单 : 不知道最后为啥挂了,这些大公司面人的时候感觉很捉摸不透啊
|
l*****k 发帖数: 1059 | 47 这种题对new graduate来说最危险了,算法很简单,完全
看写代码的功力。 |
a**********e 发帖数: 157 | 48 谢谢分享。
【在 j*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 50分钟。 : 就一道题。 比如对于 数组 [1, 3, 9, 9] ,表示 1399, 实现 加 1 : 面试官一直让不断的优化。 : 后面8分钟就闲聊 project 了。
|
e****w 发帖数: 19 | 49 google电面两轮吧 我第一轮也是这题 一共就面了25分钟 包括我最后问问题的时间 但
第二轮没面好还是直接挂了 第二轮题是 输入两个整数 然后得出他们商的结果 在循环
部分打括号
比如输入1,3 输出0.(3)
输入1,2 输出0.5(0)
bless.昨天电面的今天就给消息了 ?
【在 j*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : bless. : 昨天电面的今天就给消息了 ?
|
B*******1 发帖数: 2454 | 50 这题有意思啊:
比如输入1,3 输出0.(3)
输入1,2 输出0.5(0)
记得有个数学trick在里面,你怎么做的啊?
【在 e****w 的大作中提到】![](/moin_static193/solenoid/img/up.png) : google电面两轮吧 我第一轮也是这题 一共就面了25分钟 包括我最后问问题的时间 但 : 第二轮没面好还是直接挂了 第二轮题是 输入两个整数 然后得出他们商的结果 在循环 : 部分打括号 : 比如输入1,3 输出0.(3) : 输入1,2 输出0.5(0) : : : bless.昨天电面的今天就给消息了 ?
|
|
|
w**********o 发帖数: 140 | 51 This is cool:
public class Solution {
public int[] plusOne(int[] digits) {
// Start typing your Java solution below
// DO NOT write main() function
int carry=1;
for(int i=digits.length-1;i>=0;i--){
if(carry==0)
break;
if(digits[i]==9){
digits[i]=0;
}
else{
digits[i]++;
carry=0;
}
}
if(carry==0) return digits;
int[] array =new int[digits.length+1];
array[0]=1;
for(int i=0;i
array[i+1]=digits[i];
return array;
}
}
// copied from http://www.tsechung.com/wordpress/2012/07/19/plus-one/ |
e****w 发帖数: 19 | 52 哈哈 大牛想想呗
其实没啥tricky
但是一开始被这题唬住了 而且那时候还没啥面试经验
所以就面挂了~
【在 B*******1 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这题有意思啊: : 比如输入1,3 输出0.(3) : 输入1,2 输出0.5(0) : 记得有个数学trick在里面,你怎么做的啊? :
|
M********5 发帖数: 715 | 53 以前没有见过这个题,intuitive的想法:
先计算整数部分的商,这个不难,整数部分的商先保存在一个变量里面
再计算小数部分的商,怎么判断是否进入小数部分:如果商为0余数不为0,就进入小数
部分
接下来,把小数部分的商用string保存起来,并且把小数部分的结果建立trie(为了后
面计算循环部分,因为像单个的循环节好计算,但是比如1/7这种循环节很长的,就不
是那么好计算),不断地计算结果,计算到一定长度的时候如果发现某个string总是重
复出现,就可以判断为循环节。这个时候再对计算的小数部分的商做处理,只取到第一
个循环节为止(可以用简单的substring操作)
我不知道相关的数学trick,一点愚见。。。
【在 B*******1 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这题有意思啊: : 比如输入1,3 输出0.(3) : 输入1,2 输出0.5(0) : 记得有个数学trick在里面,你怎么做的啊? :
|
e****w 发帖数: 19 | 54 怎么判断出循环的string啊?
这一段能再详细说下?
【在 M********5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 以前没有见过这个题,intuitive的想法: : 先计算整数部分的商,这个不难,整数部分的商先保存在一个变量里面 : 再计算小数部分的商,怎么判断是否进入小数部分:如果商为0余数不为0,就进入小数 : 部分 : 接下来,把小数部分的商用string保存起来,并且把小数部分的结果建立trie(为了后 : 面计算循环部分,因为像单个的循环节好计算,但是比如1/7这种循环节很长的,就不 : 是那么好计算),不断地计算结果,计算到一定长度的时候如果发现某个string总是重 : 复出现,就可以判断为循环节。这个时候再对计算的小数部分的商做处理,只取到第一 : 个循环节为止(可以用简单的substring操作) : 我不知道相关的数学trick,一点愚见。。。
|
M********5 发帖数: 715 | 55 等一下,我仔细想了一下具体的做法,差不多有了个大概的思路,等我先整理整理。。。
不过实在觉得这一题作为电话面试太难了,你比我还倒霉。。。
【在 e****w 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 怎么判断出循环的string啊? : 这一段能再详细说下?
|
f*****e 发帖数: 2992 | 56 其实就是小数部分不断取余,然后判断第一个重复余出现的时刻:
比如1/7
取余是:1,3,2,6,4,5,1
thus...
【在 M********5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 以前没有见过这个题,intuitive的想法: : 先计算整数部分的商,这个不难,整数部分的商先保存在一个变量里面 : 再计算小数部分的商,怎么判断是否进入小数部分:如果商为0余数不为0,就进入小数 : 部分 : 接下来,把小数部分的商用string保存起来,并且把小数部分的结果建立trie(为了后 : 面计算循环部分,因为像单个的循环节好计算,但是比如1/7这种循环节很长的,就不 : 是那么好计算),不断地计算结果,计算到一定长度的时候如果发现某个string总是重 : 复出现,就可以判断为循环节。这个时候再对计算的小数部分的商做处理,只取到第一 : 个循环节为止(可以用简单的substring操作) : 我不知道相关的数学trick,一点愚见。。。
|
M********5 发帖数: 715 | 57 这个我也知道,不过要用代码表达出来。。。
【在 f*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 其实就是小数部分不断取余,然后判断第一个重复余出现的时刻: : 比如1/7 : 取余是:1,3,2,6,4,5,1 : thus...
|
p*****2 发帖数: 21240 | 58
是这个道理,写起来稍微麻烦一些。要考虑 1/70, 1/700这些情况。
比如1/70 输出 0.0(142857)
【在 f*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 其实就是小数部分不断取余,然后判断第一个重复余出现的时刻: : 比如1/7 : 取余是:1,3,2,6,4,5,1 : thus...
|
l*****i 发帖数: 136 | 59 没有测试很多case,只是把idea表达了出来
感觉面试的时候现写,只能跪了
string afterPoint(int a, int b)
{
string ret;
unordered_map m;
if (a==0)
{
ret += "(0)";
return ret;
}
int p=0;
while(true)
{
m[a] = p;
a *= 10;
int d = a/b;
int r = a%b;
ret += char(d+'0');
if ( m.find( r)!= m.end() ) // find the cycle
{
ret.insert(m[r], "(");
ret += ')';
return ret;
}
p++;
a = r;
}
}
string Solution(int a, int b)
{
string ret;
int d = a/b;
ret = to_string(d);
ret += ".";
ret += afterPoint(a%b, b);
return ret;
}
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 是这个道理,写起来稍微麻烦一些。要考虑 1/70, 1/700这些情况。 : 比如1/70 输出 0.0(142857)
|
B*******1 发帖数: 2454 | 60 的确不好写,店面这个比较坑爹了。 我以前就看过这题,但是就一次,但是从来没有
练过。
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 是这个道理,写起来稍微麻烦一些。要考虑 1/70, 1/700这些情况。 : 比如1/70 输出 0.0(142857)
|
|
|
f*****e 发帖数: 2992 | 61 试了试,好像1/70也可以用乘10取余这种方法:
1/70,每一个元素都是它前一个元素乘10取余:
1, 10, 30, 20, 60, 40, 50, 10, duplicate found
也可以判断如果分子比分母小就继续乘10,不用存map或set。
不过overflow确实需要考虑啊。
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 是这个道理,写起来稍微麻烦一些。要考虑 1/70, 1/700这些情况。 : 比如1/70 输出 0.0(142857)
|
M********5 发帖数: 715 | 62 你这个思路不错,但是有没有可能出现这样的一种case,比如说有一个商是
0.3323232323(23)...
这样在出现第二个3的时候,你就觉得3就是循环节了,结果后面都没有计算了?只是提
供一个case供讨论。。。
【在 l*****i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 没有测试很多case,只是把idea表达了出来 : 感觉面试的时候现写,只能跪了 : string afterPoint(int a, int b) : { : string ret; : unordered_map m; : if (a==0) : { : ret += "(0)"; : return ret;
|
M********5 发帖数: 715 | 63 不过你怎么能知道什么时候该乘10呢?万一这个是1/71呢。。。只是一个想法。。。
【在 f*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 试了试,好像1/70也可以用乘10取余这种方法: : 1/70,每一个元素都是它前一个元素乘10取余: : 1, 10, 30, 20, 60, 40, 50, 10, duplicate found : 也可以判断如果分子比分母小就继续乘10,不用存map或set。 : 不过overflow确实需要考虑啊。
|
f*****e 发帖数: 2992 | 64 我就是手算看出规律的,我觉得没什么难度。不信你手算试试。
【在 M********5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不过你怎么能知道什么时候该乘10呢?万一这个是1/71呢。。。只是一个想法。。。
|
M********5 发帖数: 715 | 65 我明白你的意思,不过我的意思是,这个规律是仅仅适用于7的倍数做分母,还是适用
于所有的数,这个还不好说。。。
【在 f*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我就是手算看出规律的,我觉得没什么难度。不信你手算试试。
|
j*****y 发帖数: 1071 | 66 调试了无数次,似乎搞了一个 work的, 花了两个小时阿。换作是我,当场悲剧的更惨。
string func(int a, int b)
{
bool negative = false;
if(a < 0)
{
negative = true;
a = -a;
}
if(b < 0)
{
if(negative)
{
negative = false;
}
else
{
negative = true;
}
b = -b;
}
int x = a / b;
int y = a % b;
string s;
stringstream ss;
ss << x;
s=ss.str();
if(negative)
{
s = "-" + s;
}
if(y == 0)
{
return s;
}
s += ".";
int pos[b];
for(int i = 0; i < b; ++i)
{
pos[i] = 0;
}
string tail;
int next_y = y;
int count = 0;
while(y != 0)
{
pos[y] = ++count;
x = 10 * y;
next_y = x % b;
tail.append(1, x / b + '0');
if(next_y == 0)
{
tail += "(0)";
break;
}
if(pos[next_y] != 0)
{
tail.insert(tail.begin() + pos[next_y] - 1, '(');
tail.append(1, ')');
break;
}
y = next_y;
}
s = s + tail;
return s;
}
【在 e****w 的大作中提到】![](/moin_static193/solenoid/img/up.png) : google电面两轮吧 我第一轮也是这题 一共就面了25分钟 包括我最后问问题的时间 但 : 第二轮没面好还是直接挂了 第二轮题是 输入两个整数 然后得出他们商的结果 在循环 : 部分打括号 : 比如输入1,3 输出0.(3) : 输入1,2 输出0.5(0) : : : bless.昨天电面的今天就给消息了 ?
|
l*****i 发帖数: 136 | 67 我觉的不会吧,我这是看余数是否相等,余数相等的话,后面的除法就是在重复前面的
某个序列开始的过程,所以商肯定开始重复了
【在 M********5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你这个思路不错,但是有没有可能出现这样的一种case,比如说有一个商是 : 0.3323232323(23)... : 这样在出现第二个3的时候,你就觉得3就是循环节了,结果后面都没有计算了?只是提 : 供一个case供讨论。。。
|
M********5 发帖数: 715 | 68 这个解释make sense。。。
enlinw挂在这题上确实情理之中,我也直接给跪了。。。我现在再也不觉得自己冤枉了。
。。
【在 l*****i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我觉的不会吧,我这是看余数是否相等,余数相等的话,后面的除法就是在重复前面的 : 某个序列开始的过程,所以商肯定开始重复了
|
p*****2 发帖数: 21240 | 69 练练第一道题
def plusOne(num)
c=1
for i in -1.downto(-num.length)
c+=num[i]
num[i]=c%10
c/=10
end
if c>0
num.unshift(c)
end
end |
p*****2 发帖数: 21240 | 70
就是这样。结果还不能输出,要存起来,遇到过的余数也要用个hashtable存起来,并
且指向结果的位置。一旦发现有重复的。从这个位置开始画(),之前的直接输出。
【在 f*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 试了试,好像1/70也可以用乘10取余这种方法: : 1/70,每一个元素都是它前一个元素乘10取余: : 1, 10, 30, 20, 60, 40, 50, 10, duplicate found : 也可以判断如果分子比分母小就继续乘10,不用存map或set。 : 不过overflow确实需要考虑啊。
|
|
|
e****w 发帖数: 19 | 71 没有吧 用商和用余数找循环不一样的 用余数要简单很多
我只是想听听你是怎么用商找循环的
其实面试时候他给我提示的 让我用余数找循环
其实后来想想思路清楚之后 还是能写的
【在 M********5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个我也知道,不过要用代码表达出来。。。
|
e****w 发帖数: 19 | 72 嗯嗯 对就是这个思路 不能用商来找循环
要用余数来找循环
大致是把余数存在linkedlist l1里,对应的商存在另一个linkedlist l2里,然后每来
一个新余数,都和l1里的比较,如果有出现过,那么从出现的那个到最后就是循环部分
(这里只是循环的位置,不是结果)把对应位置的商(l2里的结果)用括号括起来,之
前的商的结果就放在前面就行了,如果没有出现过,那就加到l1里面,也把商加到l2里面
【在 l*****i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我觉的不会吧,我这是看余数是否相等,余数相等的话,后面的除法就是在重复前面的 : 某个序列开始的过程,所以商肯定开始重复了
|
o***d 发帖数: 313 | 73 请教一下:
1) 用vector返回是他要求的么?不能用reference argument作返回么?或者用输入参数
本身做返回?
2) 他要求用vector的?还是你自己挑的?
【在 j*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这是最后的 code : vector plusOne(vector &input) : { : if(input.size() == 0) : { : return vector(1, 1); : } : : int remainder = 1; : for(int i = input.size() -1 ; i > -1; --i)
|
o***d 发帖数: 313 | 74 最后的两个数组赋值,copy不快些么?为什么要loop?
【在 w**********o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : This is cool: : public class Solution { : public int[] plusOne(int[] digits) { : // Start typing your Java solution below : // DO NOT write main() function : int carry=1; : for(int i=digits.length-1;i>=0;i--){ : if(carry==0) : break; : if(digits[i]==9){
|
o***d 发帖数: 313 | 75 大牛觉得楼上某个的java实现怎么样?你这样%运算慢吧?他那个基本只有if, else, +
+,应该很快似乎
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 练练第一道题 : def plusOne(num) : c=1 : for i in -1.downto(-num.length) : c+=num[i] : num[i]=c%10 : c/=10 : end : : if c>0
|
o***d 发帖数: 313 | 76 还有个问题,似乎我看大家一般都用index来loop stl container,but normally, we
are suggested to use iterator, right?
do you guys think that will be a problem when we write the code onsite/at
phone interview?
tks |
j*****y 发帖数: 1071 | 77 自己挑的, 说 vector 对自己比较奥 comfortable一下 :)
【在 o***d 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 请教一下: : 1) 用vector返回是他要求的么?不能用reference argument作返回么?或者用输入参数 : 本身做返回? : 2) 他要求用vector的?还是你自己挑的?
|
o***d 发帖数: 313 | 78 还有个问题,似乎我看大家一般都用index来loop stl container,but normally, we
are suggested to use iterator, right?
do you guys think that will be a problem when we write the code onsite/at
phone interview?
tks |
p*****2 发帖数: 21240 | 79 为什么用链表
里面
【在 e****w 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 嗯嗯 对就是这个思路 不能用商来找循环 : 要用余数来找循环 : 大致是把余数存在linkedlist l1里,对应的商存在另一个linkedlist l2里,然后每来 : 一个新余数,都和l1里的比较,如果有出现过,那么从出现的那个到最后就是循环部分 : (这里只是循环的位置,不是结果)把对应位置的商(l2里的结果)用括号括起来,之 : 前的商的结果就放在前面就行了,如果没有出现过,那就加到l1里面,也把商加到l2里面
|
o***d 发帖数: 313 | 80 thanks to let me know!
【在 j*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 自己挑的, 说 vector 对自己比较奥 comfortable一下 :)
|
|
|
e****w 发帖数: 19 | 81 只是为了知道位置咯~~
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 为什么用链表 : : 里面
|
M********5 发帖数: 715 | 82 我想了一下,其实用商也是可以找到循环的,只不过会麻烦很多。。。并且这个做法存
在一个假设,就是假设循环节不能太长了,比如suppose循环节不能长于某个数字。
具体的想法是这样子的,比如说我把这个数一直除,除到小数点后面100位,这样我就
有了一个长度为100的string,两个整数相除,肯定是有循环节的,那么我可以从循环
小数的特点来看,最后一位一定是循环节里面的某一位,然后我再从后往前找,找到一
个跟str[99]相同的数字的时候,判断str[pos]到str[99]是不是循环节,如果不是的话
,再接着找,直到找到循环节为止;如果是的话,我们就找到了循环节的长度,接下来
就是判断循环节里面的哪一个数字是这个循环节的开头,因为这个时候循环节的长度已
经知道了,假设为len,我们就把这个循环节里面的每一个数字不断地往前移len,然后
判断最前端可以移到哪个数字,直到不是循环节了为止,这就是循环节的最开始。。。
我说了这是个很麻烦的办法,但是如果说只要循环节没有个50,60位长,这个办法应该
是正确的,不过会比用余数麻烦很多,因为它需要足够长的string来作为样本
【在 e****w 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 没有吧 用商和用余数找循环不一样的 用余数要简单很多 : 我只是想听听你是怎么用商找循环的 : 其实面试时候他给我提示的 让我用余数找循环 : 其实后来想想思路清楚之后 还是能写的
|
M********5 发帖数: 715 | 83 并且我由此想到了一个衍生的题目,如果说给了一个无限循环小数的string表示方法(
这个string表示方法的最后一个数字不一定是循环节的最后一个数字,可以是整个循环
节里面的任何一个数字),只是告诉已知条件是一个无限循环小数的表示,但是没有说
循环节有多长或者说循环节的起始位置在哪,让你找出循环节,你怎么找?我觉得我说
的这个方法就可以判断。。。
【在 M********5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我想了一下,其实用商也是可以找到循环的,只不过会麻烦很多。。。并且这个做法存 : 在一个假设,就是假设循环节不能太长了,比如suppose循环节不能长于某个数字。 : 具体的想法是这样子的,比如说我把这个数一直除,除到小数点后面100位,这样我就 : 有了一个长度为100的string,两个整数相除,肯定是有循环节的,那么我可以从循环 : 小数的特点来看,最后一位一定是循环节里面的某一位,然后我再从后往前找,找到一 : 个跟str[99]相同的数字的时候,判断str[pos]到str[99]是不是循环节,如果不是的话 : ,再接着找,直到找到循环节为止;如果是的话,我们就找到了循环节的长度,接下来 : 就是判断循环节里面的哪一个数字是这个循环节的开头,因为这个时候循环节的长度已 : 经知道了,假设为len,我们就把这个循环节里面的每一个数字不断地往前移len,然后 : 判断最前端可以移到哪个数字,直到不是循环节了为止,这就是循环节的最开始。。。
|
l**h 发帖数: 893 | 84 /**
* 比如输入1,3 输出0.(3)
* 输入1,2 输出0.5(0)
* 输入1,700, 输出 0.00(142857)
* 暂不考虑输入为负数
*/
public class Division {
public static String getQuotientInString(int i, int j) {
StringBuffer quotient = new StringBuffer();
quotient.append(i/j);
quotient.append(".");
int modular = i%j * 10;
while(modular/j == 0) {
quotient.append("0");
modular = modular * 10;
}
int a[] = new int[10];
Arrays.fill(a, 0);
int dividend = modular;
while(true) {
int tmpQuotient = dividend/j;
if (a[tmpQuotient] != 0) {
quotient.insert(a[tmpQuotient], "(");
quotient.append(")");
break;
}
else {
a[tmpQuotient] = quotient.length();
quotient.append(tmpQuotient);
}
dividend = (dividend%j) * 10;
}
return quotient.toString();
}
}
【在 e****w 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 怎么判断出循环的string啊? : 这一段能再详细说下?
|
j*****y 发帖数: 1071 | 85 通过商就可以判断是循环了吗? 感觉还是要通过余数吧
比如 0.1323.....
后面的不知道了,这个时候不见的就是 0.1(32)
感觉只有出现了相同的余数才能断定循环了。
【在 l**h 的大作中提到】![](/moin_static193/solenoid/img/up.png) : /** : * 比如输入1,3 输出0.(3) : * 输入1,2 输出0.5(0) : * 输入1,700, 输出 0.00(142857) : * 暂不考虑输入为负数 : */ : public class Division { : public static String getQuotientInString(int i, int j) { : StringBuffer quotient = new StringBuffer(); : quotient.append(i/j);
|
M********5 发帖数: 715 | 86 这样单单地比较商确实是不行的,比如说0.3332323(23)
【在 l**h 的大作中提到】![](/moin_static193/solenoid/img/up.png) : /** : * 比如输入1,3 输出0.(3) : * 输入1,2 输出0.5(0) : * 输入1,700, 输出 0.00(142857) : * 暂不考虑输入为负数 : */ : public class Division { : public static String getQuotientInString(int i, int j) { : StringBuffer quotient = new StringBuffer(); : quotient.append(i/j);
|
l**h 发帖数: 893 | 87 对,要改一下,用余数
【在 j*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 通过商就可以判断是循环了吗? 感觉还是要通过余数吧 : 比如 0.1323..... : 后面的不知道了,这个时候不见的就是 0.1(32) : 感觉只有出现了相同的余数才能断定循环了。
|
p*****2 发帖数: 21240 | 88
感觉复杂度比较高吧?
【在 e****w 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 只是为了知道位置咯~~
|
p*****2 发帖数: 21240 | 89
+
我也不是很清楚%慢多少。大牛讲讲。
【在 o***d 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 大牛觉得楼上某个的java实现怎么样?你这样%运算慢吧?他那个基本只有if, else, + : +,应该很快似乎
|
p*****2 发帖数: 21240 | 90 第二题练了练
def divide(a,b)
if b==0
return
end
print("#{a/b}.")
a=(a%b)*10
arr=[]
hm={}
while hm[a]==nil
hm[a]=arr.length
if(a!=0 && a
a*=10;
arr.push(0)
else
arr.push(a/b)
a=(a%b)*10
end
end
for i in 0..hm[a]-1
print(arr[i])
end
print("(")
for i in hm[a]..arr.length-1
print(arr[i])
end
print(")\n")
end |