j*****y
发帖数: 1071 | 1 50分钟。
就一道题。 比如对于 数组 [1, 3, 9, 9] ,表示 1399, 实现 加 1
面试官一直让不断的优化。
后面8分钟就闲聊 project 了。 |
P**********g
发帖数: 30 | 2 问个菜菜的问题。
电面是开着电话免提，写code...? |
j*****y
发帖数: 1071 | 3 我开着手机免提的。前面是电脑。下巴下面是手机
【在 P**********g 的大作中提到】
: 问个菜菜的问题。
: 电面是开着电话免提，写code...?
|
P**********g
发帖数: 30 | 4 就是只有一个大数加法的实现？
lz 你 onsite 肯定没问题啦，cong一个 |
j*****y
发帖数: 1071 | 5 多谢，多谢 :)
这个比大数加法应该要容易很多，因为另外一个数只是 1.
【在 P**********g 的大作中提到】
: 就是只有一个大数加法的实现？
: lz 你 onsite 肯定没问题啦，cong一个
|
M********5
发帖数: 715 | |
j*****y
发帖数: 1071 | 7 多谢 :)
现在我发现 做完 leetcode OJ 离 优化code到最好的地步还差的好远。
【在 M********5 的大作中提到】
: 你运气真好，这个羡慕都羡慕不来。。。
|
c********t
发帖数: 5706 | 8 我想到的就是in-place 硬做，遇到数组越界，要重新开新空间
还有什么优化吗？
【在 j*****y 的大作中提到】
: 50分钟。
: 就一道题。 比如对于 数组 [1, 3, 9, 9] ,表示 1399, 实现 加 1
: 面试官一直让不断的优化。
: 后面8分钟就闲聊 project 了。
|
j*****y
发帖数: 1071 | 9 中间的时候如果遇到了不进位的话，就 break
【在 c********t 的大作中提到】
: 我想到的就是in-place 硬做，遇到数组越界，要重新开新空间
: 还有什么优化吗？
|
j*****y
发帖数: 1071 | 10 你这个in place 是很好的一个优化。
【在 c********t 的大作中提到】
: 我想到的就是in-place 硬做，遇到数组越界，要重新开新空间
: 还有什么优化吗？
|
|
|
M********5
发帖数: 715 | 11 我也是这么想的，中间遇到不进位的时候就break，然后只要给出的数组不是9999这种
的，就不许要另外allocate space，如果是9999的话，那就另外做打算。。。是这样的
思路么？
【在 j*****y 的大作中提到】
: 中间的时候如果遇到了不进位的话，就 break
|
c********t
发帖数: 5706 | 12 嗯，明白了。肯定on-site了，提前恭喜！
【在 j*****y 的大作中提到】
: 你这个in place 是很好的一个优化。
|
A*****i
发帖数: 3587 | 13 昨天google电面问个如何遍历DAP的题，也是不断优化啥的，挺简单
不知道最后为啥挂了，这些大公司面人的时候感觉很捉摸不透啊 |
j*****y
发帖数: 1071 | 14 对的。 :)
【在 M********5 的大作中提到】
: 我也是这么想的，中间遇到不进位的时候就break，然后只要给出的数组不是9999这种
: 的，就不许要另外allocate space，如果是9999的话，那就另外做打算。。。是这样的
: 思路么？
|
j*****y
发帖数: 1071 | 15 多谢多谢， 托您吉言 :)
【在 c********t 的大作中提到】
: 嗯，明白了。肯定on-site了，提前恭喜！
|
f*****e
发帖数: 2992 | 16 如果是二进制的话，是不是必须到2^32-1再进位？
【在 j*****y 的大作中提到】
: 对的。 :)
|
j*****y
发帖数: 1071 | 17 不是二进制的表示。就是 0-9之间的 digit表示。
【在 f*****e 的大作中提到】
: 如果是二进制的话，是不是必须到2^32-1再进位？
|
r*****e
发帖数: 146 | 18 Bless! 应该进入下一轮了，弱问一句，一般G家的电话，要做几道题啊？
【在 j*****y 的大作中提到】
: 50分钟。
: 就一道题。 比如对于 数组 [1, 3, 9, 9] ,表示 1399, 实现 加 1
: 面试官一直让不断的优化。
: 后面8分钟就闲聊 project 了。
|
r*****e
发帖数: 146 | 19 弱问一下，啥是DAP?
【在 A*****i 的大作中提到】
: 昨天google电面问个如何遍历DAP的题，也是不断优化啥的，挺简单
: 不知道最后为啥挂了，这些大公司面人的时候感觉很捉摸不透啊
|
j*****y
发帖数: 1071 | 20 你说的是 DAG 吗？
【在 A*****i 的大作中提到】
: 昨天google电面问个如何遍历DAP的题，也是不断优化啥的，挺简单
: 不知道最后为啥挂了，这些大公司面人的时候感觉很捉摸不透啊
|
|
|
j*****y
发帖数: 1071 | 21 多谢。 :)
我也不知道，可能看你水平，像我这种弱水平的，面试官也没有时间让你做两道题目。
【在 r*****e 的大作中提到】
: Bless! 应该进入下一轮了，弱问一句，一般G家的电话，要做几道题啊？
|
B*******1
发帖数: 2454 | 22 你这道算法题用了多久时间啊？ 50分钟就一道题？
【在 j*****y 的大作中提到】
: 多谢。 :)
: 我也不知道，可能看你水平，像我这种弱水平的，面试官也没有时间让你做两道题目。
|
j*****y
发帖数: 1071 | 23 我花了 20分钟写完，然后20分钟在提示下一步一步优化。
这40分钟就这一道题。
后面的时间就闲聊了。
【在 B*******1 的大作中提到】
: 你这道算法题用了多久时间啊？ 50分钟就一道题？
|
s**s
发帖数: 70 | |
j*****y
发帖数: 1071 | 25 多谢吉言 :)
【在 s**s 的大作中提到】
: 祝onsite成功~
|
M********5
发帖数: 715 | 26 所以他是真的很幸运啦。。。这种东西嫉妒不来，咱们得move on。。。
【在 B*******1 的大作中提到】
: 你这道算法题用了多久时间啊？ 50分钟就一道题？
|
A*****i
发帖数: 3587 | 27 矮油我擦，一着急写错了，DAG，不是DAP
【在 r*****e 的大作中提到】
: 弱问一下，啥是DAP?
|
s********l
发帖数: 998 | 28 只加一边1
还是没完没了的加啊？
【在 j*****y 的大作中提到】
: 50分钟。
: 就一道题。 比如对于 数组 [1, 3, 9, 9] ,表示 1399, 实现 加 1
: 面试官一直让不断的优化。
: 后面8分钟就闲聊 project 了。
|
j*****y
发帖数: 1071 | 29 加一次 1
比如对于 19
计算 19 + 1
只不过 19存在数组里面而已
【在 s********l 的大作中提到】
: 只加一边1
: 还是没完没了的加啊？
|
s********l
发帖数: 998 | 30 哦~ 这样子 thanks.
【在 j*****y 的大作中提到】
: 加一次 1
: 比如对于 19
: 计算 19 + 1
: 只不过 19存在数组里面而已
|
|
|
s********l
发帖数: 998 | 31 你最后 优化成什么样子的了？
【在 j*****y 的大作中提到】
: 50分钟。
: 就一道题。 比如对于 数组 [1, 3, 9, 9] ,表示 1399, 实现 加 1
: 面试官一直让不断的优化。
: 后面8分钟就闲聊 project 了。
|
s********l
发帖数: 998 | 32 这个 你最后优化成什么样了？
【在 A*****i 的大作中提到】
: 昨天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 的大作中提到】
: 你最后 优化成什么样子的了？
|
l*********8
发帖数: 4642 | 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)
|
j*****y
发帖数: 1071 | 35 没有discuss这个 :)
【在 l*********8 的大作中提到】
: 能不能把数字反过来存？
: [9, 9，3， 1] 表示1399
|
s********l
发帖数: 998 | 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
发帖数: 1071 | 37 可是刚才拷贝的时候，我发现了一个错误 :(
else 写成了 esle
【在 s********l 的大作中提到】
: 这个好 多谢多谢
|
l*****a
发帖数: 14598 | 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)
|
s********l
发帖数: 998 | 39 这个肯定不会有影响的~~
【在 j*****y 的大作中提到】
: 可是刚才拷贝的时候，我发现了一个错误 :(
: else 写成了 esle
|
j*****y
发帖数: 1071 | 40 多谢。 希望如此，托您吉言 :)
【在 s********l 的大作中提到】
: 这个肯定不会有影响的~~
|
|
|
j*****y
发帖数: 1071 | 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
发帖数: 14598 | 42 i mean since nothing in the input, why u return int [] a={1};
【在 j*****y 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: why not throw something like illegalArgumentException?
|
j*****y
发帖数: 1071 | 46 bless.
昨天电面的今天就给消息了 ?
【在 A*****i 的大作中提到】
: 昨天google电面问个如何遍历DAP的题，也是不断优化啥的，挺简单
: 不知道最后为啥挂了，这些大公司面人的时候感觉很捉摸不透啊
|
l*****k
发帖数: 1059 | 47 这种题对new graduate来说最危险了，算法很简单，完全
看写代码的功力。 |
a**********e
发帖数: 157 | 48 谢谢分享。
【在 j*****y 的大作中提到】
: 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 的大作中提到】
: bless.
: 昨天电面的今天就给消息了 ?
|
B*******1
发帖数: 2454 | 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.昨天电面的今天就给消息了 ?
|
|
|
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 的大作中提到】
: 这题有意思啊：
: 比如输入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 的大作中提到】
: 这题有意思啊：
: 比如输入1，3 输出0.（3）
: 输入1，2 输出0.5（0）
: 记得有个数学trick在里面，你怎么做的啊？
:
|
e****w
发帖数: 19 | 54 怎么判断出循环的string啊？
这一段能再详细说下？
【在 M********5 的大作中提到】
: 以前没有见过这个题，intuitive的想法：
: 先计算整数部分的商，这个不难，整数部分的商先保存在一个变量里面
: 再计算小数部分的商，怎么判断是否进入小数部分：如果商为0余数不为0，就进入小数
: 部分
: 接下来，把小数部分的商用string保存起来，并且把小数部分的结果建立trie（为了后
: 面计算循环部分，因为像单个的循环节好计算，但是比如1/7这种循环节很长的，就不
: 是那么好计算），不断地计算结果，计算到一定长度的时候如果发现某个string总是重
: 复出现，就可以判断为循环节。这个时候再对计算的小数部分的商做处理，只取到第一
: 个循环节为止（可以用简单的substring操作）
: 我不知道相关的数学trick，一点愚见。。。
|
M********5
发帖数: 715 | 55 等一下，我仔细想了一下具体的做法，差不多有了个大概的思路，等我先整理整理。。。
不过实在觉得这一题作为电话面试太难了，你比我还倒霉。。。
【在 e****w 的大作中提到】
: 怎么判断出循环的string啊？
: 这一段能再详细说下？
|
f*****e
发帖数: 2992 | 56 其实就是小数部分不断取余，然后判断第一个重复余出现的时刻：
比如1/7
取余是:1,3,2,6,4,5,1
thus...
【在 M********5 的大作中提到】
: 以前没有见过这个题，intuitive的想法：
: 先计算整数部分的商，这个不难，整数部分的商先保存在一个变量里面
: 再计算小数部分的商，怎么判断是否进入小数部分：如果商为0余数不为0，就进入小数
: 部分
: 接下来，把小数部分的商用string保存起来，并且把小数部分的结果建立trie（为了后
: 面计算循环部分，因为像单个的循环节好计算，但是比如1/7这种循环节很长的，就不
: 是那么好计算），不断地计算结果，计算到一定长度的时候如果发现某个string总是重
: 复出现，就可以判断为循环节。这个时候再对计算的小数部分的商做处理，只取到第一
: 个循环节为止（可以用简单的substring操作）
: 我不知道相关的数学trick，一点愚见。。。
|
M********5
发帖数: 715 | 57 这个我也知道，不过要用代码表达出来。。。
【在 f*****e 的大作中提到】
: 其实就是小数部分不断取余，然后判断第一个重复余出现的时刻：
: 比如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 的大作中提到】
: 其实就是小数部分不断取余，然后判断第一个重复余出现的时刻：
: 比如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 的大作中提到】
:
: 是这个道理，写起来稍微麻烦一些。要考虑 1/70, 1/700这些情况。
: 比如1/70 输出 0.0（142857）
|
B*******1
发帖数: 2454 | 60 的确不好写，店面这个比较坑爹了。 我以前就看过这题，但是就一次，但是从来没有
练过。
【在 p*****2 的大作中提到】
:
: 是这个道理，写起来稍微麻烦一些。要考虑 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 的大作中提到】
:
: 是这个道理，写起来稍微麻烦一些。要考虑 1/70, 1/700这些情况。
: 比如1/70 输出 0.0（142857）
|
M********5
发帖数: 715 | 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;
|
M********5
发帖数: 715 | 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
发帖数: 2992 | 64 我就是手算看出规律的，我觉得没什么难度。不信你手算试试。
【在 M********5 的大作中提到】
: 不过你怎么能知道什么时候该乘10呢?万一这个是1/71呢。。。只是一个想法。。。
|
M********5
发帖数: 715 | 65 我明白你的意思，不过我的意思是，这个规律是仅仅适用于7的倍数做分母，还是适用
于所有的数，这个还不好说。。。
【在 f*****e 的大作中提到】
: 我就是手算看出规律的，我觉得没什么难度。不信你手算试试。
|
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 的大作中提到】
: google电面两轮吧 我第一轮也是这题 一共就面了25分钟 包括我最后问问题的时间 但
: 第二轮没面好还是直接挂了 第二轮题是 输入两个整数 然后得出他们商的结果 在循环
: 部分打括号
: 比如输入1，3 输出0.（3）
: 输入1，2 输出0.5（0）
:
:
: bless.昨天电面的今天就给消息了 ?
|
l*****i
发帖数: 136 | 67 我觉的不会吧，我这是看余数是否相等，余数相等的话，后面的除法就是在重复前面的
某个序列开始的过程，所以商肯定开始重复了
【在 M********5 的大作中提到】
: 你这个思路不错，但是有没有可能出现这样的一种case，比如说有一个商是
: 0.3323232323(23)...
: 这样在出现第二个3的时候，你就觉得3就是循环节了，结果后面都没有计算了？只是提
: 供一个case供讨论。。。
|
M********5
发帖数: 715 | 68 这个解释make sense。。。
enlinw挂在这题上确实情理之中，我也直接给跪了。。。我现在再也不觉得自己冤枉了。
。。
【在 l*****i 的大作中提到】
: 我觉的不会吧，我这是看余数是否相等，余数相等的话，后面的除法就是在重复前面的
: 某个序列开始的过程，所以商肯定开始重复了
|
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 的大作中提到】
: 试了试，好像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 的大作中提到】
: 这个我也知道，不过要用代码表达出来。。。
|
e****w
发帖数: 19 | 72 嗯嗯 对就是这个思路 不能用商来找循环
要用余数来找循环
大致是把余数存在linkedlist l1里，对应的商存在另一个linkedlist l2里，然后每来
一个新余数，都和l1里的比较，如果有出现过，那么从出现的那个到最后就是循环部分
（这里只是循环的位置，不是结果）把对应位置的商（l2里的结果）用括号括起来，之
前的商的结果就放在前面就行了，如果没有出现过，那就加到l1里面，也把商加到l2里面
【在 l*****i 的大作中提到】
: 我觉的不会吧，我这是看余数是否相等，余数相等的话，后面的除法就是在重复前面的
: 某个序列开始的过程，所以商肯定开始重复了
|
o***d
发帖数: 313 | 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)
|
o***d
发帖数: 313 | 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){
|
o***d
发帖数: 313 | 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
|
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 的大作中提到】
: 请教一下:
: 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 的大作中提到】
: 嗯嗯 对就是这个思路 不能用商来找循环
: 要用余数来找循环
: 大致是把余数存在linkedlist l1里，对应的商存在另一个linkedlist l2里，然后每来
: 一个新余数，都和l1里的比较，如果有出现过，那么从出现的那个到最后就是循环部分
: （这里只是循环的位置，不是结果）把对应位置的商（l2里的结果）用括号括起来，之
: 前的商的结果就放在前面就行了，如果没有出现过，那就加到l1里面，也把商加到l2里面
|
o***d
发帖数: 313 | 80 thanks to let me know!
【在 j*****y 的大作中提到】
: 自己挑的， 说 vector 对自己比较奥 comfortable一下 :)
|
|
|
e****w
发帖数: 19 | 81 只是为了知道位置咯～～
【在 p*****2 的大作中提到】
: 为什么用链表
:
: 里面
|
M********5
发帖数: 715 | 82 我想了一下，其实用商也是可以找到循环的，只不过会麻烦很多。。。并且这个做法存
在一个假设，就是假设循环节不能太长了，比如suppose循环节不能长于某个数字。
具体的想法是这样子的，比如说我把这个数一直除，除到小数点后面100位，这样我就
有了一个长度为100的string，两个整数相除，肯定是有循环节的，那么我可以从循环
小数的特点来看，最后一位一定是循环节里面的某一位，然后我再从后往前找，找到一
个跟str[99]相同的数字的时候，判断str[pos]到str[99]是不是循环节，如果不是的话
，再接着找，直到找到循环节为止；如果是的话，我们就找到了循环节的长度，接下来
就是判断循环节里面的哪一个数字是这个循环节的开头，因为这个时候循环节的长度已
经知道了，假设为len，我们就把这个循环节里面的每一个数字不断地往前移len，然后
判断最前端可以移到哪个数字，直到不是循环节了为止，这就是循环节的最开始。。。
我说了这是个很麻烦的办法，但是如果说只要循环节没有个50，60位长，这个办法应该
是正确的，不过会比用余数麻烦很多，因为它需要足够长的string来作为样本
【在 e****w 的大作中提到】
: 没有吧 用商和用余数找循环不一样的 用余数要简单很多
: 我只是想听听你是怎么用商找循环的
: 其实面试时候他给我提示的 让我用余数找循环
: 其实后来想想思路清楚之后 还是能写的
|
M********5
发帖数: 715 | 83 并且我由此想到了一个衍生的题目，如果说给了一个无限循环小数的string表示方法（
这个string表示方法的最后一个数字不一定是循环节的最后一个数字，可以是整个循环
节里面的任何一个数字），只是告诉已知条件是一个无限循环小数的表示，但是没有说
循环节有多长或者说循环节的起始位置在哪，让你找出循环节，你怎么找？我觉得我说
的这个方法就可以判断。。。
【在 M********5 的大作中提到】
: 我想了一下，其实用商也是可以找到循环的，只不过会麻烦很多。。。并且这个做法存
: 在一个假设，就是假设循环节不能太长了，比如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 的大作中提到】
: 怎么判断出循环的string啊？
: 这一段能再详细说下？
|
j*****y
发帖数: 1071 | 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);
|
M********5
发帖数: 715 | 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
发帖数: 893 | 87 对，要改一下,用余数
【在 j*****y 的大作中提到】
: 通过商就可以判断是循环了吗？ 感觉还是要通过余数吧
: 比如 0.1323.....
: 后面的不知道了，这个时候不见的就是 0.1(32)
: 感觉只有出现了相同的余数才能断定循环了。
|
p*****2
发帖数: 21240 | 88
感觉复杂度比较高吧？
【在 e****w 的大作中提到】
: 只是为了知道位置咯～～
|
p*****2
发帖数: 21240 | 89
+
我也不是很清楚％慢多少。大牛讲讲。
【在 o***d 的大作中提到】
: 大牛觉得楼上某个的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 |
