g***j
发帖数: 1275 | 1 给定一个range，假设1-20，给定一个输入，假设4 3 5 6 如何判断输入是否是连续的
。 输入的可能不是有序的
我答，给个数组，1-20的，然后map进去，然后扫描数组，他说如何改进，我说用bit
map，他说那如何判断bit map是否是连续的1呢，我说往右边移动，然后根据最后一位
判断，他说如何改进，我说考虑所有可能的bitmap情况一个个比较，这个我胡说的，自
己也没有想清楚。
后来他说如果要更加快更加快，如果不准用所有判断，只用一句话，怎么搞？
我不知道了，他提示我，给1-1000，怎么迅速判断一个数是否是质数？我说求出所有质
数然后看那个数是否是啊，他说，对，这个题目也这么搞，用一个lookup table
后来我在想怎么lookup table呢？难道把所有可能的情况都放在lookup table里面？
他反复强调只能用一句code
大家有什么想法? |
f*****e
发帖数: 2992 | 2 1,1,2,3,4,2算不算连续？还是必须是扫20个数，每个数必须distinct？
【在 g***j 的大作中提到】
: 给定一个range，假设1-20，给定一个输入，假设4 3 5 6 如何判断输入是否是连续的
: 。 输入的可能不是有序的
: 我答，给个数组，1-20的，然后map进去，然后扫描数组，他说如何改进，我说用bit
: map，他说那如何判断bit map是否是连续的1呢，我说往右边移动，然后根据最后一位
: 判断，他说如何改进，我说考虑所有可能的bitmap情况一个个比较，这个我胡说的，自
: 己也没有想清楚。
: 后来他说如果要更加快更加快，如果不准用所有判断，只用一句话，怎么搞？
: 我不知道了，他提示我，给1-1000，怎么迅速判断一个数是否是质数？我说求出所有质
: 数然后看那个数是否是啊，他说，对，这个题目也这么搞，用一个lookup table
: 后来我在想怎么lookup table呢？难道把所有可能的情况都放在lookup table里面？
|
f*****e
发帖数: 2992 | 3 记录一个low，一个max，所有扫描完了，max-low+1 = N就连续。否则不连续。
【在 g***j 的大作中提到】
: 给定一个range，假设1-20，给定一个输入，假设4 3 5 6 如何判断输入是否是连续的
: 。 输入的可能不是有序的
: 我答，给个数组，1-20的，然后map进去，然后扫描数组，他说如何改进，我说用bit
: map，他说那如何判断bit map是否是连续的1呢，我说往右边移动，然后根据最后一位
: 判断，他说如何改进，我说考虑所有可能的bitmap情况一个个比较，这个我胡说的，自
: 己也没有想清楚。
: 后来他说如果要更加快更加快，如果不准用所有判断，只用一句话，怎么搞？
: 我不知道了，他提示我，给1-1000，怎么迅速判断一个数是否是质数？我说求出所有质
: 数然后看那个数是否是啊，他说，对，这个题目也这么搞，用一个lookup table
: 后来我在想怎么lookup table呢？难道把所有可能的情况都放在lookup table里面？
|
i**********e
发帖数: 1145 | 4 输入应该是数组吧？
这样的话最快也得 O(n) 呀。
直接循环，然后判定如果 n-1 == (max - min)，就输入是连续的。
【在 g***j 的大作中提到】
: 给定一个range，假设1-20，给定一个输入，假设4 3 5 6 如何判断输入是否是连续的
: 。 输入的可能不是有序的
: 我答，给个数组，1-20的，然后map进去，然后扫描数组，他说如何改进，我说用bit
: map，他说那如何判断bit map是否是连续的1呢，我说往右边移动，然后根据最后一位
: 判断，他说如何改进，我说考虑所有可能的bitmap情况一个个比较，这个我胡说的，自
: 己也没有想清楚。
: 后来他说如果要更加快更加快，如果不准用所有判断，只用一句话，怎么搞？
: 我不知道了，他提示我，给1-1000，怎么迅速判断一个数是否是质数？我说求出所有质
: 数然后看那个数是否是啊，他说，对，这个题目也这么搞，用一个lookup table
: 后来我在想怎么lookup table呢？难道把所有可能的情况都放在lookup table里面？
|
t******t
发帖数: 21 | 5 if no duplicates like 6,4,7,5,3,8
scan the input once find max min and count and then you can calculate if
they are continuous.
if duplicates are allowed, use hashmap to filter out duplicates and find max
min and count(don't count dup) in one pass.
【在 g***j 的大作中提到】
: 给定一个range，假设1-20，给定一个输入，假设4 3 5 6 如何判断输入是否是连续的
: 。 输入的可能不是有序的
: 我答，给个数组，1-20的，然后map进去，然后扫描数组，他说如何改进，我说用bit
: map，他说那如何判断bit map是否是连续的1呢，我说往右边移动，然后根据最后一位
: 判断，他说如何改进，我说考虑所有可能的bitmap情况一个个比较，这个我胡说的，自
: 己也没有想清楚。
: 后来他说如果要更加快更加快，如果不准用所有判断，只用一句话，怎么搞？
: 我不知道了，他提示我，给1-1000，怎么迅速判断一个数是否是质数？我说求出所有质
: 数然后看那个数是否是啊，他说，对，这个题目也这么搞，用一个lookup table
: 后来我在想怎么lookup table呢？难道把所有可能的情况都放在lookup table里面？
|
g***j
发帖数: 1275 | 6 对方要求一行搞定
max
【在 t******t 的大作中提到】
: if no duplicates like 6,4,7,5,3,8
: scan the input once find max min and count and then you can calculate if
: they are continuous.
: if duplicates are allowed, use hashmap to filter out duplicates and find max
: min and count(don't count dup) in one pass.
|
a*******y
发帖数: 1040 | 7 这个keep那个最小的值和sum
sum 应该等于那个最小的值*number of element + (1+2+3...+N） |
a*******y
发帖数: 1040 | 8 那个look up table应该就是这个东东（NxN)矩阵
【在 a*******y 的大作中提到】
: 这个keep那个最小的值和sum
: sum 应该等于那个最小的值*number of element + (1+2+3...+N）
|
f*****e
发帖数: 2992 | 9 那也得扫一遍啊，O(N)。
【在 a*******y 的大作中提到】
: 那个look up table应该就是这个东东（NxN)矩阵
|
f*****e
发帖数: 2992 | 10 一个lookup table 2^20个数(or bits in bitmap)，连续的为1，否则为0，比如
A[011110]=1,A[010110]=0。输入1,3,2,4就第1，3，2，4 bit为1。
A[1111] = 1，then连续。
【在 g***j 的大作中提到】
: 给定一个range，假设1-20，给定一个输入，假设4 3 5 6 如何判断输入是否是连续的
: 。 输入的可能不是有序的
: 我答，给个数组，1-20的，然后map进去，然后扫描数组，他说如何改进，我说用bit
: map，他说那如何判断bit map是否是连续的1呢，我说往右边移动，然后根据最后一位
: 判断，他说如何改进，我说考虑所有可能的bitmap情况一个个比较，这个我胡说的，自
: 己也没有想清楚。
: 后来他说如果要更加快更加快，如果不准用所有判断，只用一句话，怎么搞？
: 我不知道了，他提示我，给1-1000，怎么迅速判断一个数是否是质数？我说求出所有质
: 数然后看那个数是否是啊，他说，对，这个题目也这么搞，用一个lookup table
: 后来我在想怎么lookup table呢？难道把所有可能的情况都放在lookup table里面？
|
|
|
f*****e
发帖数: 2992 | 11 做这点小屁事要128kB内存不去也罢。
【在 f*****e 的大作中提到】
: 一个lookup table 2^20个数(or bits in bitmap)，连续的为1，否则为0，比如
: A[011110]=1,A[010110]=0。输入1,3,2,4就第1，3，2，4 bit为1。
: A[1111] = 1，then连续。
|
t******t
发帖数: 21 | 12 上岁数了, 已经不介意几行了. 另外,只收一行的钱,其他几行免费.
【在 g***j 的大作中提到】
: 对方要求一行搞定
:
: max
|
N**n
发帖数: 832 | 13 看hacker's delight，
1，数后缀0的个数
2，右移后缀0个数这么多
3，判断这个数+1是不是2的完全平方数
【在 f*****e 的大作中提到】
: 一个lookup table 2^20个数(or bits in bitmap)，连续的为1，否则为0，比如
: A[011110]=1,A[010110]=0。输入1,3,2,4就第1，3，2，4 bit为1。
: A[1111] = 1，then连续。
|
C***U
发帖数: 2406 | 14 你这个对么？
1 1 3
min = 1
max = 3
n = 2
【在 f*****e 的大作中提到】
: 记录一个low，一个max，所有扫描完了，max-low+1 = N就连续。否则不连续。
|
g**u
发帖数: 504 | 15 duplicate要先滤掉的，前面有人说了的
【在 C***U 的大作中提到】
: 你这个对么？
: 1 1 3
: min = 1
: max = 3
: n = 2
|
