G 家电面面经# JobHunting - 待字闺中
j*y
1 楼
50分钟。
就一道题。 比如对于 数组 [1, 3, 9, 9] ,表示 1399, 实现 加 1
面试官一直让不断的优化。
后面8分钟就闲聊 project 了。
就一道题。 比如对于 数组 [1, 3, 9, 9] ,表示 1399, 实现 加 1
面试官一直让不断的优化。
后面8分钟就闲聊 project 了。
P*g
2 楼
问个菜菜的问题。
电面是开着电话免提，写code...?
电面是开着电话免提，写code...?
j*y
3 楼
我开着手机免提的。前面是电脑。下巴下面是手机
【在 P**********g 的大作中提到】
: 问个菜菜的问题。
: 电面是开着电话免提，写code...?
【在 P**********g 的大作中提到】
: 问个菜菜的问题。
: 电面是开着电话免提，写code...?
P*g
4 楼
就是只有一个大数加法的实现？
lz 你 onsite 肯定没问题啦，cong一个
lz 你 onsite 肯定没问题啦，cong一个
j*y
5 楼
多谢，多谢 :)
这个比大数加法应该要容易很多，因为另外一个数只是 1.
【在 P**********g 的大作中提到】
: 就是只有一个大数加法的实现？
: lz 你 onsite 肯定没问题啦，cong一个
这个比大数加法应该要容易很多，因为另外一个数只是 1.
【在 P**********g 的大作中提到】
: 就是只有一个大数加法的实现？
: lz 你 onsite 肯定没问题啦，cong一个
M*5
6 楼
你运气真好，这个羡慕都羡慕不来。。。
j*y
7 楼
多谢 :)
现在我发现 做完 leetcode OJ 离 优化code到最好的地步还差的好远。
【在 M********5 的大作中提到】
: 你运气真好，这个羡慕都羡慕不来。。。
现在我发现 做完 leetcode OJ 离 优化code到最好的地步还差的好远。
【在 M********5 的大作中提到】
: 你运气真好，这个羡慕都羡慕不来。。。
c*t
8 楼
我想到的就是in-place 硬做，遇到数组越界，要重新开新空间
还有什么优化吗？
【在 j*****y 的大作中提到】
: 50分钟。
: 就一道题。 比如对于 数组 [1, 3, 9, 9] ,表示 1399, 实现 加 1
: 面试官一直让不断的优化。
: 后面8分钟就闲聊 project 了。
还有什么优化吗？
【在 j*****y 的大作中提到】
: 50分钟。
: 就一道题。 比如对于 数组 [1, 3, 9, 9] ,表示 1399, 实现 加 1
: 面试官一直让不断的优化。
: 后面8分钟就闲聊 project 了。
j*y
9 楼
中间的时候如果遇到了不进位的话，就 break
【在 c********t 的大作中提到】
: 我想到的就是in-place 硬做，遇到数组越界，要重新开新空间
: 还有什么优化吗？
【在 c********t 的大作中提到】
: 我想到的就是in-place 硬做，遇到数组越界，要重新开新空间
: 还有什么优化吗？
j*y
10 楼
你这个in place 是很好的一个优化。
【在 c********t 的大作中提到】
: 我想到的就是in-place 硬做，遇到数组越界，要重新开新空间
: 还有什么优化吗？
【在 c********t 的大作中提到】
: 我想到的就是in-place 硬做，遇到数组越界，要重新开新空间
: 还有什么优化吗？
M*5
11 楼
我也是这么想的，中间遇到不进位的时候就break，然后只要给出的数组不是9999这种
的，就不许要另外allocate space，如果是9999的话，那就另外做打算。。。是这样的
思路么？
【在 j*****y 的大作中提到】
: 中间的时候如果遇到了不进位的话，就 break
的，就不许要另外allocate space，如果是9999的话，那就另外做打算。。。是这样的
思路么？
【在 j*****y 的大作中提到】
: 中间的时候如果遇到了不进位的话，就 break
c*t
12 楼
嗯，明白了。肯定on-site了，提前恭喜！
【在 j*****y 的大作中提到】
: 你这个in place 是很好的一个优化。
【在 j*****y 的大作中提到】
: 你这个in place 是很好的一个优化。
A*i
13 楼
昨天google电面问个如何遍历DAP的题，也是不断优化啥的，挺简单
不知道最后为啥挂了，这些大公司面人的时候感觉很捉摸不透啊
不知道最后为啥挂了，这些大公司面人的时候感觉很捉摸不透啊
j*y
14 楼
对的。 :)
【在 M********5 的大作中提到】
: 我也是这么想的，中间遇到不进位的时候就break，然后只要给出的数组不是9999这种
: 的，就不许要另外allocate space，如果是9999的话，那就另外做打算。。。是这样的
: 思路么？
【在 M********5 的大作中提到】
: 我也是这么想的，中间遇到不进位的时候就break，然后只要给出的数组不是9999这种
: 的，就不许要另外allocate space，如果是9999的话，那就另外做打算。。。是这样的
: 思路么？
j*y
15 楼
多谢多谢， 托您吉言 :)
【在 c********t 的大作中提到】
: 嗯，明白了。肯定on-site了，提前恭喜！
【在 c********t 的大作中提到】
: 嗯，明白了。肯定on-site了，提前恭喜！
f*e
16 楼
如果是二进制的话，是不是必须到2^32-1再进位？
【在 j*****y 的大作中提到】
: 对的。 :)
【在 j*****y 的大作中提到】
: 对的。 :)
j*y
17 楼
不是二进制的表示。就是 0-9之间的 digit表示。
【在 f*****e 的大作中提到】
: 如果是二进制的话，是不是必须到2^32-1再进位？
【在 f*****e 的大作中提到】
: 如果是二进制的话，是不是必须到2^32-1再进位？
r*e
18 楼
Bless! 应该进入下一轮了，弱问一句，一般G家的电话，要做几道题啊？
【在 j*****y 的大作中提到】
: 50分钟。
: 就一道题。 比如对于 数组 [1, 3, 9, 9] ,表示 1399, 实现 加 1
: 面试官一直让不断的优化。
: 后面8分钟就闲聊 project 了。
【在 j*****y 的大作中提到】
: 50分钟。
: 就一道题。 比如对于 数组 [1, 3, 9, 9] ,表示 1399, 实现 加 1
: 面试官一直让不断的优化。
: 后面8分钟就闲聊 project 了。
r*e
19 楼
弱问一下，啥是DAP?
【在 A*****i 的大作中提到】
: 昨天google电面问个如何遍历DAP的题，也是不断优化啥的，挺简单
: 不知道最后为啥挂了，这些大公司面人的时候感觉很捉摸不透啊
【在 A*****i 的大作中提到】
: 昨天google电面问个如何遍历DAP的题，也是不断优化啥的，挺简单
: 不知道最后为啥挂了，这些大公司面人的时候感觉很捉摸不透啊
j*y
20 楼
你说的是 DAG 吗？
【在 A*****i 的大作中提到】
: 昨天google电面问个如何遍历DAP的题，也是不断优化啥的，挺简单
: 不知道最后为啥挂了，这些大公司面人的时候感觉很捉摸不透啊
【在 A*****i 的大作中提到】
: 昨天google电面问个如何遍历DAP的题，也是不断优化啥的，挺简单
: 不知道最后为啥挂了，这些大公司面人的时候感觉很捉摸不透啊
j*y
21 楼
多谢。 :)
我也不知道，可能看你水平，像我这种弱水平的，面试官也没有时间让你做两道题目。
【在 r*****e 的大作中提到】
: Bless! 应该进入下一轮了，弱问一句，一般G家的电话，要做几道题啊？
我也不知道，可能看你水平，像我这种弱水平的，面试官也没有时间让你做两道题目。
【在 r*****e 的大作中提到】
: Bless! 应该进入下一轮了，弱问一句，一般G家的电话，要做几道题啊？
B*1
22 楼
你这道算法题用了多久时间啊？ 50分钟就一道题？
【在 j*****y 的大作中提到】
: 多谢。 :)
: 我也不知道，可能看你水平，像我这种弱水平的，面试官也没有时间让你做两道题目。
【在 j*****y 的大作中提到】
: 多谢。 :)
: 我也不知道，可能看你水平，像我这种弱水平的，面试官也没有时间让你做两道题目。
j*y
23 楼
我花了 20分钟写完，然后20分钟在提示下一步一步优化。
这40分钟就这一道题。
后面的时间就闲聊了。
【在 B*******1 的大作中提到】
: 你这道算法题用了多久时间啊？ 50分钟就一道题？
这40分钟就这一道题。
后面的时间就闲聊了。
【在 B*******1 的大作中提到】
: 你这道算法题用了多久时间啊？ 50分钟就一道题？
s*s
24 楼
祝onsite成功~
j*y
25 楼
多谢吉言 :)
【在 s**s 的大作中提到】
: 祝onsite成功~
【在 s**s 的大作中提到】
: 祝onsite成功~
M*5
26 楼
所以他是真的很幸运啦。。。这种东西嫉妒不来，咱们得move on。。。
【在 B*******1 的大作中提到】
: 你这道算法题用了多久时间啊？ 50分钟就一道题？
【在 B*******1 的大作中提到】
: 你这道算法题用了多久时间啊？ 50分钟就一道题？
A*i
27 楼
矮油我擦，一着急写错了，DAG，不是DAP
【在 r*****e 的大作中提到】
: 弱问一下，啥是DAP?
【在 r*****e 的大作中提到】
: 弱问一下，啥是DAP?
s*l
28 楼
只加一边1
还是没完没了的加啊？
【在 j*****y 的大作中提到】
: 50分钟。
: 就一道题。 比如对于 数组 [1, 3, 9, 9] ,表示 1399, 实现 加 1
: 面试官一直让不断的优化。
: 后面8分钟就闲聊 project 了。
还是没完没了的加啊？
【在 j*****y 的大作中提到】
: 50分钟。
: 就一道题。 比如对于 数组 [1, 3, 9, 9] ,表示 1399, 实现 加 1
: 面试官一直让不断的优化。
: 后面8分钟就闲聊 project 了。
j*y
29 楼
加一次 1
比如对于 19
计算 19 + 1
只不过 19存在数组里面而已
【在 s********l 的大作中提到】
: 只加一边1
: 还是没完没了的加啊？
比如对于 19
计算 19 + 1
只不过 19存在数组里面而已
【在 s********l 的大作中提到】
: 只加一边1
: 还是没完没了的加啊？
s*l
30 楼
哦~ 这样子 thanks.
【在 j*****y 的大作中提到】
: 加一次 1
: 比如对于 19
: 计算 19 + 1
: 只不过 19存在数组里面而已
【在 j*****y 的大作中提到】
: 加一次 1
: 比如对于 19
: 计算 19 + 1
: 只不过 19存在数组里面而已
s*l
31 楼
你最后 优化成什么样子的了？
【在 j*****y 的大作中提到】
: 50分钟。
: 就一道题。 比如对于 数组 [1, 3, 9, 9] ,表示 1399, 实现 加 1
: 面试官一直让不断的优化。
: 后面8分钟就闲聊 project 了。
【在 j*****y 的大作中提到】
: 50分钟。
: 就一道题。 比如对于 数组 [1, 3, 9, 9] ,表示 1399, 实现 加 1
: 面试官一直让不断的优化。
: 后面8分钟就闲聊 project 了。
s*l
32 楼
这个 你最后优化成什么样了？
【在 A*****i 的大作中提到】
: 昨天google电面问个如何遍历DAP的题，也是不断优化啥的，挺简单
: 不知道最后为啥挂了，这些大公司面人的时候感觉很捉摸不透啊
【在 A*****i 的大作中提到】
: 昨天google电面问个如何遍历DAP的题，也是不断优化啥的，挺简单
: 不知道最后为啥挂了，这些大公司面人的时候感觉很捉摸不透啊
j*y
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 的大作中提到】
: 你最后 优化成什么样子的了？
vector
{
if(input.size() == 0)
{
return vector
}
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
input.insert(input.begin(), tmp.begin(), tmp.end());
}
return input;
}
【在 s********l 的大作中提到】
: 你最后 优化成什么样子的了？
l*8
34 楼
能不能把数字反过来存？
[9, 9，3， 1] 表示1399
【在 j*****y 的大作中提到】
: 这是最后的 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)
[9, 9，3， 1] 表示1399
【在 j*****y 的大作中提到】
: 这是最后的 code
: vector
: {
: if(input.size() == 0)
: {
: return vector
: }
:
: int remainder = 1;
: for(int i = input.size() -1 ; i > -1; --i)
j*y
35 楼
没有discuss这个 :)
【在 l*********8 的大作中提到】
: 能不能把数字反过来存？
: [9, 9，3， 1] 表示1399
【在 l*********8 的大作中提到】
: 能不能把数字反过来存？
: [9, 9，3， 1] 表示1399
s*l
36 楼
这个好 多谢多谢
【在 j*****y 的大作中提到】
: 这是最后的 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 的大作中提到】
: 这是最后的 code
: vector
: {
: if(input.size() == 0)
: {
: return vector
: }
:
: int remainder = 1;
: for(int i = input.size() -1 ; i > -1; --i)
j*y
37 楼
可是刚才拷贝的时候，我发现了一个错误 :(
else 写成了 esle
【在 s********l 的大作中提到】
: 这个好 多谢多谢
else 写成了 esle
【在 s********l 的大作中提到】
: 这个好 多谢多谢
l*a
38 楼
why input.size()==0, then u return 1?
if input==0, then u can return 1
【在 j*****y 的大作中提到】
: 这是最后的 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)
if input==0, then u can return 1
【在 j*****y 的大作中提到】
: 这是最后的 code
: vector
: {
: if(input.size() == 0)
: {
: return vector
: }
:
: int remainder = 1;
: for(int i = input.size() -1 ; i > -1; --i)
s*l
39 楼
这个肯定不会有影响的~~
【在 j*****y 的大作中提到】
: 可是刚才拷贝的时候，我发现了一个错误 :(
: else 写成了 esle
【在 j*****y 的大作中提到】
: 可是刚才拷贝的时候，我发现了一个错误 :(
: else 写成了 esle
j*y
40 楼
多谢。 希望如此，托您吉言 :)
【在 s********l 的大作中提到】
: 这个肯定不会有影响的~~
【在 s********l 的大作中提到】
: 这个肯定不会有影响的~~
j*y
41 楼
should return an array
【在 l*****a 的大作中提到】
: why input.size()==0, then u return 1?
: if input==0, then u can return 1
【在 l*****a 的大作中提到】
: why input.size()==0, then u return 1?
: if input==0, then u can return 1
l*a
42 楼
i mean since nothing in the input, why u return int [] a={1};
【在 j*****y 的大作中提到】
: should return an array
【在 j*****y 的大作中提到】
: should return an array
j*y
43 楼
i asked him if it is OK to return [1] in this case, he gave yes.
【在 l*****a 的大作中提到】
: i mean since nothing in the input, why u return int [] a={1};
【在 l*****a 的大作中提到】
: i mean since nothing in the input, why u return int [] a={1};
l*a
44 楼
why not throw something like illegalArgumentException?
【在 j*****y 的大作中提到】
: i asked him if it is OK to return [1] in this case, he gave yes.
【在 j*****y 的大作中提到】
: i asked him if it is OK to return [1] in this case, he gave yes.
j*y
45 楼
too complicated to me :)
【在 l*****a 的大作中提到】
: why not throw something like illegalArgumentException?
【在 l*****a 的大作中提到】
: why not throw something like illegalArgumentException?
j*y
46 楼
bless.
昨天电面的今天就给消息了 ?
【在 A*****i 的大作中提到】
: 昨天google电面问个如何遍历DAP的题，也是不断优化啥的，挺简单
: 不知道最后为啥挂了，这些大公司面人的时候感觉很捉摸不透啊
昨天电面的今天就给消息了 ?
【在 A*****i 的大作中提到】
: 昨天google电面问个如何遍历DAP的题，也是不断优化啥的，挺简单
: 不知道最后为啥挂了，这些大公司面人的时候感觉很捉摸不透啊
l*k
47 楼
这种题对new graduate来说最危险了，算法很简单，完全
看写代码的功力。
看写代码的功力。
a*e
48 楼
谢谢分享。
【在 j*****y 的大作中提到】
: 50分钟。
: 就一道题。 比如对于 数组 [1, 3, 9, 9] ,表示 1399, 实现 加 1
: 面试官一直让不断的优化。
: 后面8分钟就闲聊 project 了。
【在 j*****y 的大作中提到】
: 50分钟。
: 就一道题。 比如对于 数组 [1, 3, 9, 9] ,表示 1399, 实现 加 1
: 面试官一直让不断的优化。
: 后面8分钟就闲聊 project 了。
e*w
49 楼
google电面两轮吧 我第一轮也是这题 一共就面了25分钟 包括我最后问问题的时间 但
第二轮没面好还是直接挂了 第二轮题是 输入两个整数 然后得出他们商的结果 在循环
部分打括号
比如输入1，3 输出0.（3）
输入1，2 输出0.5（0）
bless.昨天电面的今天就给消息了 ?
【在 j*****y 的大作中提到】
: bless.
: 昨天电面的今天就给消息了 ?
第二轮没面好还是直接挂了 第二轮题是 输入两个整数 然后得出他们商的结果 在循环
部分打括号
比如输入1，3 输出0.（3）
输入1，2 输出0.5（0）
bless.昨天电面的今天就给消息了 ?
【在 j*****y 的大作中提到】
: bless.
: 昨天电面的今天就给消息了 ?
B*1
50 楼
这题有意思啊：
比如输入1，3 输出0.（3）
输入1，2 输出0.5（0）
记得有个数学trick在里面，你怎么做的啊？
【在 e****w 的大作中提到】
: google电面两轮吧 我第一轮也是这题 一共就面了25分钟 包括我最后问问题的时间 但
: 第二轮没面好还是直接挂了 第二轮题是 输入两个整数 然后得出他们商的结果 在循环
: 部分打括号
: 比如输入1，3 输出0.（3）
: 输入1，2 输出0.5（0）
:
:
: bless.昨天电面的今天就给消息了 ?
比如输入1，3 输出0.（3）
输入1，2 输出0.5（0）
记得有个数学trick在里面，你怎么做的啊？
【在 e****w 的大作中提到】
: google电面两轮吧 我第一轮也是这题 一共就面了25分钟 包括我最后问问题的时间 但
: 第二轮没面好还是直接挂了 第二轮题是 输入两个整数 然后得出他们商的结果 在循环
: 部分打括号
: 比如输入1，3 输出0.（3）
: 输入1，2 输出0.5（0）
:
:
: bless.昨天电面的今天就给消息了 ?
w*o
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
return array;
}
}
// copied from http://www.tsechung.com/wordpress/2012/07/19/plus-one/
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
return array;
}
}
// copied from http://www.tsechung.com/wordpress/2012/07/19/plus-one/
e*w
52 楼
哈哈 大牛想想呗
其实没啥tricky
但是一开始被这题唬住了 而且那时候还没啥面试经验
所以就面挂了～
【在 B*******1 的大作中提到】
: 这题有意思啊：
: 比如输入1，3 输出0.（3）
: 输入1，2 输出0.5（0）
: 记得有个数学trick在里面，你怎么做的啊？
:
其实没啥tricky
但是一开始被这题唬住了 而且那时候还没啥面试经验
所以就面挂了～
【在 B*******1 的大作中提到】
: 这题有意思啊：
: 比如输入1，3 输出0.（3）
: 输入1，2 输出0.5（0）
: 记得有个数学trick在里面，你怎么做的啊？
:
M*5
53 楼
以前没有见过这个题，intuitive的想法：
先计算整数部分的商，这个不难，整数部分的商先保存在一个变量里面
再计算小数部分的商，怎么判断是否进入小数部分：如果商为0余数不为0，就进入小数
部分
接下来，把小数部分的商用string保存起来，并且把小数部分的结果建立trie（为了后
面计算循环部分，因为像单个的循环节好计算，但是比如1/7这种循环节很长的，就不
是那么好计算），不断地计算结果，计算到一定长度的时候如果发现某个string总是重
复出现，就可以判断为循环节。这个时候再对计算的小数部分的商做处理，只取到第一
个循环节为止（可以用简单的substring操作）
我不知道相关的数学trick，一点愚见。。。
【在 B*******1 的大作中提到】
: 这题有意思啊：
: 比如输入1，3 输出0.（3）
: 输入1，2 输出0.5（0）
: 记得有个数学trick在里面，你怎么做的啊？
:
先计算整数部分的商，这个不难，整数部分的商先保存在一个变量里面
再计算小数部分的商，怎么判断是否进入小数部分：如果商为0余数不为0，就进入小数
部分
接下来，把小数部分的商用string保存起来，并且把小数部分的结果建立trie（为了后
面计算循环部分，因为像单个的循环节好计算，但是比如1/7这种循环节很长的，就不
是那么好计算），不断地计算结果，计算到一定长度的时候如果发现某个string总是重
复出现，就可以判断为循环节。这个时候再对计算的小数部分的商做处理，只取到第一
个循环节为止（可以用简单的substring操作）
我不知道相关的数学trick，一点愚见。。。
【在 B*******1 的大作中提到】
: 这题有意思啊：
: 比如输入1，3 输出0.（3）
: 输入1，2 输出0.5（0）
: 记得有个数学trick在里面，你怎么做的啊？
:
e*w
54 楼
怎么判断出循环的string啊？
这一段能再详细说下？
【在 M********5 的大作中提到】
: 以前没有见过这个题，intuitive的想法：
: 先计算整数部分的商，这个不难，整数部分的商先保存在一个变量里面
: 再计算小数部分的商，怎么判断是否进入小数部分：如果商为0余数不为0，就进入小数
: 部分
: 接下来，把小数部分的商用string保存起来，并且把小数部分的结果建立trie（为了后
: 面计算循环部分，因为像单个的循环节好计算，但是比如1/7这种循环节很长的，就不
: 是那么好计算），不断地计算结果，计算到一定长度的时候如果发现某个string总是重
: 复出现，就可以判断为循环节。这个时候再对计算的小数部分的商做处理，只取到第一
: 个循环节为止（可以用简单的substring操作）
: 我不知道相关的数学trick，一点愚见。。。
这一段能再详细说下？
【在 M********5 的大作中提到】
: 以前没有见过这个题，intuitive的想法：
: 先计算整数部分的商，这个不难，整数部分的商先保存在一个变量里面
: 再计算小数部分的商，怎么判断是否进入小数部分：如果商为0余数不为0，就进入小数
: 部分
: 接下来，把小数部分的商用string保存起来，并且把小数部分的结果建立trie（为了后
: 面计算循环部分，因为像单个的循环节好计算，但是比如1/7这种循环节很长的，就不
: 是那么好计算），不断地计算结果，计算到一定长度的时候如果发现某个string总是重
: 复出现，就可以判断为循环节。这个时候再对计算的小数部分的商做处理，只取到第一
: 个循环节为止（可以用简单的substring操作）
: 我不知道相关的数学trick，一点愚见。。。
M*5
55 楼
等一下，我仔细想了一下具体的做法，差不多有了个大概的思路，等我先整理整理。。。
不过实在觉得这一题作为电话面试太难了，你比我还倒霉。。。
【在 e****w 的大作中提到】
: 怎么判断出循环的string啊？
: 这一段能再详细说下？
不过实在觉得这一题作为电话面试太难了，你比我还倒霉。。。
【在 e****w 的大作中提到】
: 怎么判断出循环的string啊？
: 这一段能再详细说下？
f*e
56 楼
其实就是小数部分不断取余，然后判断第一个重复余出现的时刻：
比如1/7
取余是:1,3,2,6,4,5,1
thus...
【在 M********5 的大作中提到】
: 以前没有见过这个题，intuitive的想法：
: 先计算整数部分的商，这个不难，整数部分的商先保存在一个变量里面
: 再计算小数部分的商，怎么判断是否进入小数部分：如果商为0余数不为0，就进入小数
: 部分
: 接下来，把小数部分的商用string保存起来，并且把小数部分的结果建立trie（为了后
: 面计算循环部分，因为像单个的循环节好计算，但是比如1/7这种循环节很长的，就不
: 是那么好计算），不断地计算结果，计算到一定长度的时候如果发现某个string总是重
: 复出现，就可以判断为循环节。这个时候再对计算的小数部分的商做处理，只取到第一
: 个循环节为止（可以用简单的substring操作）
: 我不知道相关的数学trick，一点愚见。。。
比如1/7
取余是:1,3,2,6,4,5,1
thus...
【在 M********5 的大作中提到】
: 以前没有见过这个题，intuitive的想法：
: 先计算整数部分的商，这个不难，整数部分的商先保存在一个变量里面
: 再计算小数部分的商，怎么判断是否进入小数部分：如果商为0余数不为0，就进入小数
: 部分
: 接下来，把小数部分的商用string保存起来，并且把小数部分的结果建立trie（为了后
: 面计算循环部分，因为像单个的循环节好计算，但是比如1/7这种循环节很长的，就不
: 是那么好计算），不断地计算结果，计算到一定长度的时候如果发现某个string总是重
: 复出现，就可以判断为循环节。这个时候再对计算的小数部分的商做处理，只取到第一
: 个循环节为止（可以用简单的substring操作）
: 我不知道相关的数学trick，一点愚见。。。
M*5
57 楼
这个我也知道，不过要用代码表达出来。。。
【在 f*****e 的大作中提到】
: 其实就是小数部分不断取余，然后判断第一个重复余出现的时刻：
: 比如1/7
: 取余是:1,3,2,6,4,5,1
: thus...
【在 f*****e 的大作中提到】
: 其实就是小数部分不断取余，然后判断第一个重复余出现的时刻：
: 比如1/7
: 取余是:1,3,2,6,4,5,1
: thus...
p*2
58 楼
是这个道理，写起来稍微麻烦一些。要考虑 1/70, 1/700这些情况。
比如1/70 输出 0.0（142857）
【在 f*****e 的大作中提到】
: 其实就是小数部分不断取余，然后判断第一个重复余出现的时刻：
: 比如1/7
: 取余是:1,3,2,6,4,5,1
: thus...
l*i
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 的大作中提到】
:
: 是这个道理，写起来稍微麻烦一些。要考虑 1/70, 1/700这些情况。
: 比如1/70 输出 0.0（142857）
感觉面试的时候现写，只能跪了
string afterPoint(int a, int b)
{
string ret;
unordered_map
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 的大作中提到】
:
: 是这个道理，写起来稍微麻烦一些。要考虑 1/70, 1/700这些情况。
: 比如1/70 输出 0.0（142857）
B*1
60 楼
的确不好写，店面这个比较坑爹了。 我以前就看过这题，但是就一次，但是从来没有
练过。
【在 p*****2 的大作中提到】
:
: 是这个道理，写起来稍微麻烦一些。要考虑 1/70, 1/700这些情况。
: 比如1/70 输出 0.0（142857）
练过。
【在 p*****2 的大作中提到】
:
: 是这个道理，写起来稍微麻烦一些。要考虑 1/70, 1/700这些情况。
: 比如1/70 输出 0.0（142857）
f*e
61 楼
试了试，好像1/70也可以用乘10取余这种方法：
1/70，每一个元素都是它前一个元素乘10取余：
1, 10, 30, 20, 60, 40, 50, 10, duplicate found
也可以判断如果分子比分母小就继续乘10，不用存map或set。
不过overflow确实需要考虑啊。
【在 p*****2 的大作中提到】
:
: 是这个道理，写起来稍微麻烦一些。要考虑 1/70, 1/700这些情况。
: 比如1/70 输出 0.0（142857）
1/70，每一个元素都是它前一个元素乘10取余：
1, 10, 30, 20, 60, 40, 50, 10, duplicate found
也可以判断如果分子比分母小就继续乘10，不用存map或set。
不过overflow确实需要考虑啊。
【在 p*****2 的大作中提到】
:
: 是这个道理，写起来稍微麻烦一些。要考虑 1/70, 1/700这些情况。
: 比如1/70 输出 0.0（142857）
M*5
62 楼
你这个思路不错，但是有没有可能出现这样的一种case，比如说有一个商是
0.3323232323(23)...
这样在出现第二个3的时候，你就觉得3就是循环节了，结果后面都没有计算了？只是提
供一个case供讨论。。。
【在 l*****i 的大作中提到】
: 没有测试很多case，只是把idea表达了出来
: 感觉面试的时候现写，只能跪了
: string afterPoint(int a, int b)
: {
: string ret;
: unordered_map m;
: if (a==0)
: {
: ret += "(0)";
: return ret;
0.3323232323(23)...
这样在出现第二个3的时候，你就觉得3就是循环节了，结果后面都没有计算了？只是提
供一个case供讨论。。。
【在 l*****i 的大作中提到】
: 没有测试很多case，只是把idea表达了出来
: 感觉面试的时候现写，只能跪了
: string afterPoint(int a, int b)
: {
: string ret;
: unordered_map
: if (a==0)
: {
: ret += "(0)";
: return ret;
M*5
63 楼
不过你怎么能知道什么时候该乘10呢?万一这个是1/71呢。。。只是一个想法。。。
【在 f*****e 的大作中提到】
: 试了试，好像1/70也可以用乘10取余这种方法：
: 1/70，每一个元素都是它前一个元素乘10取余：
: 1, 10, 30, 20, 60, 40, 50, 10, duplicate found
: 也可以判断如果分子比分母小就继续乘10，不用存map或set。
: 不过overflow确实需要考虑啊。
【在 f*****e 的大作中提到】
: 试了试，好像1/70也可以用乘10取余这种方法：
: 1/70，每一个元素都是它前一个元素乘10取余：
: 1, 10, 30, 20, 60, 40, 50, 10, duplicate found
: 也可以判断如果分子比分母小就继续乘10，不用存map或set。
: 不过overflow确实需要考虑啊。
f*e
64 楼
我就是手算看出规律的，我觉得没什么难度。不信你手算试试。
【在 M********5 的大作中提到】
: 不过你怎么能知道什么时候该乘10呢?万一这个是1/71呢。。。只是一个想法。。。
【在 M********5 的大作中提到】
: 不过你怎么能知道什么时候该乘10呢?万一这个是1/71呢。。。只是一个想法。。。
M*5
65 楼
我明白你的意思，不过我的意思是，这个规律是仅仅适用于7的倍数做分母，还是适用
于所有的数，这个还不好说。。。
【在 f*****e 的大作中提到】
: 我就是手算看出规律的，我觉得没什么难度。不信你手算试试。
于所有的数，这个还不好说。。。
【在 f*****e 的大作中提到】
: 我就是手算看出规律的，我觉得没什么难度。不信你手算试试。
j*y
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 的大作中提到】
: google电面两轮吧 我第一轮也是这题 一共就面了25分钟 包括我最后问问题的时间 但
: 第二轮没面好还是直接挂了 第二轮题是 输入两个整数 然后得出他们商的结果 在循环
: 部分打括号
: 比如输入1，3 输出0.（3）
: 输入1，2 输出0.5（0）
:
:
: bless.昨天电面的今天就给消息了 ?
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 的大作中提到】
: google电面两轮吧 我第一轮也是这题 一共就面了25分钟 包括我最后问问题的时间 但
: 第二轮没面好还是直接挂了 第二轮题是 输入两个整数 然后得出他们商的结果 在循环
: 部分打括号
: 比如输入1，3 输出0.（3）
: 输入1，2 输出0.5（0）
:
:
: bless.昨天电面的今天就给消息了 ?
l*i
67 楼
我觉的不会吧，我这是看余数是否相等，余数相等的话，后面的除法就是在重复前面的
某个序列开始的过程，所以商肯定开始重复了
【在 M********5 的大作中提到】
: 你这个思路不错，但是有没有可能出现这样的一种case，比如说有一个商是
: 0.3323232323(23)...
: 这样在出现第二个3的时候，你就觉得3就是循环节了，结果后面都没有计算了？只是提
: 供一个case供讨论。。。
某个序列开始的过程，所以商肯定开始重复了
【在 M********5 的大作中提到】
: 你这个思路不错，但是有没有可能出现这样的一种case，比如说有一个商是
: 0.3323232323(23)...
: 这样在出现第二个3的时候，你就觉得3就是循环节了，结果后面都没有计算了？只是提
: 供一个case供讨论。。。
M*5
68 楼
这个解释make sense。。。
enlinw挂在这题上确实情理之中，我也直接给跪了。。。我现在再也不觉得自己冤枉了。
。。
【在 l*****i 的大作中提到】
: 我觉的不会吧，我这是看余数是否相等，余数相等的话，后面的除法就是在重复前面的
: 某个序列开始的过程，所以商肯定开始重复了
enlinw挂在这题上确实情理之中，我也直接给跪了。。。我现在再也不觉得自己冤枉了。
。。
【在 l*****i 的大作中提到】
: 我觉的不会吧，我这是看余数是否相等，余数相等的话，后面的除法就是在重复前面的
: 某个序列开始的过程，所以商肯定开始重复了
p*2
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
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
70 楼
就是这样。结果还不能输出，要存起来，遇到过的余数也要用个hashtable存起来，并
且指向结果的位置。一旦发现有重复的。从这个位置开始画（），之前的直接输出。
【在 f*****e 的大作中提到】
: 试了试，好像1/70也可以用乘10取余这种方法：
: 1/70，每一个元素都是它前一个元素乘10取余：
: 1, 10, 30, 20, 60, 40, 50, 10, duplicate found
: 也可以判断如果分子比分母小就继续乘10，不用存map或set。
: 不过overflow确实需要考虑啊。
e*w
71 楼
没有吧 用商和用余数找循环不一样的 用余数要简单很多
我只是想听听你是怎么用商找循环的
其实面试时候他给我提示的 让我用余数找循环
其实后来想想思路清楚之后 还是能写的
【在 M********5 的大作中提到】
: 这个我也知道，不过要用代码表达出来。。。
我只是想听听你是怎么用商找循环的
其实面试时候他给我提示的 让我用余数找循环
其实后来想想思路清楚之后 还是能写的
【在 M********5 的大作中提到】
: 这个我也知道，不过要用代码表达出来。。。
e*w
72 楼
嗯嗯 对就是这个思路 不能用商来找循环
要用余数来找循环
大致是把余数存在linkedlist l1里，对应的商存在另一个linkedlist l2里，然后每来
一个新余数，都和l1里的比较，如果有出现过，那么从出现的那个到最后就是循环部分
（这里只是循环的位置，不是结果）把对应位置的商（l2里的结果）用括号括起来，之
前的商的结果就放在前面就行了，如果没有出现过，那就加到l1里面，也把商加到l2里面
【在 l*****i 的大作中提到】
: 我觉的不会吧，我这是看余数是否相等，余数相等的话，后面的除法就是在重复前面的
: 某个序列开始的过程，所以商肯定开始重复了
要用余数来找循环
大致是把余数存在linkedlist l1里，对应的商存在另一个linkedlist l2里，然后每来
一个新余数，都和l1里的比较，如果有出现过，那么从出现的那个到最后就是循环部分
（这里只是循环的位置，不是结果）把对应位置的商（l2里的结果）用括号括起来，之
前的商的结果就放在前面就行了，如果没有出现过，那就加到l1里面，也把商加到l2里面
【在 l*****i 的大作中提到】
: 我觉的不会吧，我这是看余数是否相等，余数相等的话，后面的除法就是在重复前面的
: 某个序列开始的过程，所以商肯定开始重复了
o*d
73 楼
请教一下:
1) 用vector返回是他要求的么?不能用reference argument作返回么?或者用输入参数
本身做返回?
2) 他要求用vector的？还是你自己挑的？
【在 j*****y 的大作中提到】
: 这是最后的 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)
1) 用vector返回是他要求的么?不能用reference argument作返回么?或者用输入参数
本身做返回?
2) 他要求用vector的？还是你自己挑的？
【在 j*****y 的大作中提到】
: 这是最后的 code
: vector
: {
: if(input.size() == 0)
: {
: return vector
: }
:
: int remainder = 1;
: for(int i = input.size() -1 ; i > -1; --i)
o*d
74 楼
最后的两个数组赋值,copy不快些么？为什么要loop?
【在 w**********o 的大作中提到】
: 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){
【在 w**********o 的大作中提到】
: 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
75 楼
大牛觉得楼上某个的java实现怎么样？你这样%运算慢吧？他那个基本只有if, else, +
+,应该很快似乎
【在 p*****2 的大作中提到】
: 练练第一道题
: 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
+,应该很快似乎
【在 p*****2 的大作中提到】
: 练练第一道题
: 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
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
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
77 楼
自己挑的， 说 vector 对自己比较奥 comfortable一下 :)
【在 o***d 的大作中提到】
: 请教一下:
: 1) 用vector返回是他要求的么?不能用reference argument作返回么?或者用输入参数
: 本身做返回?
: 2) 他要求用vector的？还是你自己挑的？
【在 o***d 的大作中提到】
: 请教一下:
: 1) 用vector返回是他要求的么?不能用reference argument作返回么?或者用输入参数
: 本身做返回?
: 2) 他要求用vector的？还是你自己挑的？
o*d
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
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
79 楼
为什么用链表
里面
【在 e****w 的大作中提到】
: 嗯嗯 对就是这个思路 不能用商来找循环
: 要用余数来找循环
: 大致是把余数存在linkedlist l1里，对应的商存在另一个linkedlist l2里，然后每来
: 一个新余数，都和l1里的比较，如果有出现过，那么从出现的那个到最后就是循环部分
: （这里只是循环的位置，不是结果）把对应位置的商（l2里的结果）用括号括起来，之
: 前的商的结果就放在前面就行了，如果没有出现过，那就加到l1里面，也把商加到l2里面
里面
【在 e****w 的大作中提到】
: 嗯嗯 对就是这个思路 不能用商来找循环
: 要用余数来找循环
: 大致是把余数存在linkedlist l1里，对应的商存在另一个linkedlist l2里，然后每来
: 一个新余数，都和l1里的比较，如果有出现过，那么从出现的那个到最后就是循环部分
: （这里只是循环的位置，不是结果）把对应位置的商（l2里的结果）用括号括起来，之
: 前的商的结果就放在前面就行了，如果没有出现过，那就加到l1里面，也把商加到l2里面
o*d
80 楼
thanks to let me know!
【在 j*****y 的大作中提到】
: 自己挑的， 说 vector 对自己比较奥 comfortable一下 :)
【在 j*****y 的大作中提到】
: 自己挑的， 说 vector 对自己比较奥 comfortable一下 :)
e*w
81 楼
只是为了知道位置咯～～
【在 p*****2 的大作中提到】
: 为什么用链表
:
: 里面
【在 p*****2 的大作中提到】
: 为什么用链表
:
: 里面
M*5
82 楼
我想了一下，其实用商也是可以找到循环的，只不过会麻烦很多。。。并且这个做法存
在一个假设，就是假设循环节不能太长了，比如suppose循环节不能长于某个数字。
具体的想法是这样子的，比如说我把这个数一直除，除到小数点后面100位，这样我就
有了一个长度为100的string，两个整数相除，肯定是有循环节的，那么我可以从循环
小数的特点来看，最后一位一定是循环节里面的某一位，然后我再从后往前找，找到一
个跟str[99]相同的数字的时候，判断str[pos]到str[99]是不是循环节，如果不是的话
，再接着找，直到找到循环节为止；如果是的话，我们就找到了循环节的长度，接下来
就是判断循环节里面的哪一个数字是这个循环节的开头，因为这个时候循环节的长度已
经知道了，假设为len，我们就把这个循环节里面的每一个数字不断地往前移len，然后
判断最前端可以移到哪个数字，直到不是循环节了为止，这就是循环节的最开始。。。
我说了这是个很麻烦的办法，但是如果说只要循环节没有个50，60位长，这个办法应该
是正确的，不过会比用余数麻烦很多，因为它需要足够长的string来作为样本
【在 e****w 的大作中提到】
: 没有吧 用商和用余数找循环不一样的 用余数要简单很多
: 我只是想听听你是怎么用商找循环的
: 其实面试时候他给我提示的 让我用余数找循环
: 其实后来想想思路清楚之后 还是能写的
在一个假设，就是假设循环节不能太长了，比如suppose循环节不能长于某个数字。
具体的想法是这样子的，比如说我把这个数一直除，除到小数点后面100位，这样我就
有了一个长度为100的string，两个整数相除，肯定是有循环节的，那么我可以从循环
小数的特点来看，最后一位一定是循环节里面的某一位，然后我再从后往前找，找到一
个跟str[99]相同的数字的时候，判断str[pos]到str[99]是不是循环节，如果不是的话
，再接着找，直到找到循环节为止；如果是的话，我们就找到了循环节的长度，接下来
就是判断循环节里面的哪一个数字是这个循环节的开头，因为这个时候循环节的长度已
经知道了，假设为len，我们就把这个循环节里面的每一个数字不断地往前移len，然后
判断最前端可以移到哪个数字，直到不是循环节了为止，这就是循环节的最开始。。。
我说了这是个很麻烦的办法，但是如果说只要循环节没有个50，60位长，这个办法应该
是正确的，不过会比用余数麻烦很多，因为它需要足够长的string来作为样本
【在 e****w 的大作中提到】
: 没有吧 用商和用余数找循环不一样的 用余数要简单很多
: 我只是想听听你是怎么用商找循环的
: 其实面试时候他给我提示的 让我用余数找循环
: 其实后来想想思路清楚之后 还是能写的
M*5
83 楼
并且我由此想到了一个衍生的题目，如果说给了一个无限循环小数的string表示方法（
这个string表示方法的最后一个数字不一定是循环节的最后一个数字，可以是整个循环
节里面的任何一个数字），只是告诉已知条件是一个无限循环小数的表示，但是没有说
循环节有多长或者说循环节的起始位置在哪，让你找出循环节，你怎么找？我觉得我说
的这个方法就可以判断。。。
【在 M********5 的大作中提到】
: 我想了一下，其实用商也是可以找到循环的，只不过会麻烦很多。。。并且这个做法存
: 在一个假设，就是假设循环节不能太长了，比如suppose循环节不能长于某个数字。
: 具体的想法是这样子的，比如说我把这个数一直除，除到小数点后面100位，这样我就
: 有了一个长度为100的string，两个整数相除，肯定是有循环节的，那么我可以从循环
: 小数的特点来看，最后一位一定是循环节里面的某一位，然后我再从后往前找，找到一
: 个跟str[99]相同的数字的时候，判断str[pos]到str[99]是不是循环节，如果不是的话
: ，再接着找，直到找到循环节为止；如果是的话，我们就找到了循环节的长度，接下来
: 就是判断循环节里面的哪一个数字是这个循环节的开头，因为这个时候循环节的长度已
: 经知道了，假设为len，我们就把这个循环节里面的每一个数字不断地往前移len，然后
: 判断最前端可以移到哪个数字，直到不是循环节了为止，这就是循环节的最开始。。。
这个string表示方法的最后一个数字不一定是循环节的最后一个数字，可以是整个循环
节里面的任何一个数字），只是告诉已知条件是一个无限循环小数的表示，但是没有说
循环节有多长或者说循环节的起始位置在哪，让你找出循环节，你怎么找？我觉得我说
的这个方法就可以判断。。。
【在 M********5 的大作中提到】
: 我想了一下，其实用商也是可以找到循环的，只不过会麻烦很多。。。并且这个做法存
: 在一个假设，就是假设循环节不能太长了，比如suppose循环节不能长于某个数字。
: 具体的想法是这样子的，比如说我把这个数一直除，除到小数点后面100位，这样我就
: 有了一个长度为100的string，两个整数相除，肯定是有循环节的，那么我可以从循环
: 小数的特点来看，最后一位一定是循环节里面的某一位，然后我再从后往前找，找到一
: 个跟str[99]相同的数字的时候，判断str[pos]到str[99]是不是循环节，如果不是的话
: ，再接着找，直到找到循环节为止；如果是的话，我们就找到了循环节的长度，接下来
: 就是判断循环节里面的哪一个数字是这个循环节的开头，因为这个时候循环节的长度已
: 经知道了，假设为len，我们就把这个循环节里面的每一个数字不断地往前移len，然后
: 判断最前端可以移到哪个数字，直到不是循环节了为止，这就是循环节的最开始。。。
l*h
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 的大作中提到】
: 怎么判断出循环的string啊？
: 这一段能再详细说下？
* 比如输入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 的大作中提到】
: 怎么判断出循环的string啊？
: 这一段能再详细说下？
j*y
85 楼
通过商就可以判断是循环了吗？ 感觉还是要通过余数吧
比如 0.1323.....
后面的不知道了，这个时候不见的就是 0.1(32)
感觉只有出现了相同的余数才能断定循环了。
【在 l**h 的大作中提到】
: /**
: * 比如输入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);
比如 0.1323.....
后面的不知道了，这个时候不见的就是 0.1(32)
感觉只有出现了相同的余数才能断定循环了。
【在 l**h 的大作中提到】
: /**
: * 比如输入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
86 楼
这样单单地比较商确实是不行的，比如说0.3332323(23)
【在 l**h 的大作中提到】
: /**
: * 比如输入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 的大作中提到】
: /**
: * 比如输入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
87 楼
对，要改一下,用余数
【在 j*****y 的大作中提到】
: 通过商就可以判断是循环了吗？ 感觉还是要通过余数吧
: 比如 0.1323.....
: 后面的不知道了，这个时候不见的就是 0.1(32)
: 感觉只有出现了相同的余数才能断定循环了。
【在 j*****y 的大作中提到】
: 通过商就可以判断是循环了吗？ 感觉还是要通过余数吧
: 比如 0.1323.....
: 后面的不知道了，这个时候不见的就是 0.1(32)
: 感觉只有出现了相同的余数才能断定循环了。
p*2
88 楼
感觉复杂度比较高吧？
【在 e****w 的大作中提到】
: 只是为了知道位置咯～～
p*2
89 楼
+
我也不是很清楚％慢多少。大牛讲讲。
【在 o***d 的大作中提到】
: 大牛觉得楼上某个的java实现怎么样？你这样%运算慢吧？他那个基本只有if, else, +
: +,应该很快似乎
p*2
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
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
相关阅读
上海高等研究院，科技人才招聘启事 （代转） (转载)H1B申请进行中我这人做事忙起来总是丢三落四onsite两周了，冇任何消息估计犯了致命的错误了[合集] H1B Transfer竟然被USCIS据了!!!弱问一下：大家找工作之前就要订好references了吗？版上有了解Akamai这个公司的吗？急招IT desktop support contractor, 请发简历给我站内信箱问个OPT的问题Lawyer fee for H1B application有人呢知道TANSONCORP 吗Hiring Manager一般会问什么问题?男士西装该不该收腰阿去过google面试的同学近来说说，recommendation letter 的时机申请OPT的问题，求解答 --- 给答案的发双黄蛋包子[合集] 问问版上的各位都是怎么开始学习算法和设计题目的？CIBASan Jose 公司招聘 OPT unpaid volunteer, IT & Business帮国内的朋友发职位，１２万刀, 生化，制药类