h******8
发帖数: 55 | 1 从这里看到的，没看到好的solution. 大家讨论一下？
* 把一个字符串转换成32bit的整数
* 一个range的序列（链表或数组），如[1,3], [2,6], [8,10]，[15,18]
写程序合并有重叠的range，比如上面的序列合并为[1,6], [8,10], [15,18]
如果这个序列不是静态的，而是一个数据流，如何 处理？
Ppl mentioned interval tree, but I do not think it would work here.
* implement the merge of two int arrays A and B, using the similar way as
merge-sort
Further question:
if A's size is over the max possible value of the int array, how do u
handlethat? suppose you have enough memory (do some math here, e.g. 2^ 30, 2
^ 40.... headache) | g*********s
发帖数: 1782 | 2
interval tree works.
u always check if the latest interval has overlap with the intervals in the
tree. if not, do insert. if overlap is found, merge the overlapped one and
check the interval again. in the extreme case u only have one interval left
finally.
【在 h******8 的大作中提到】
: 从这里看到的，没看到好的solution. 大家讨论一下？
: * 把一个字符串转换成32bit的整数
: * 一个range的序列（链表或数组），如[1,3], [2,6], [8,10]，[15,18]
: 写程序合并有重叠的range，比如上面的序列合并为[1,6], [8,10], [15,18]
: 如果这个序列不是静态的，而是一个数据流，如何 处理？
: Ppl mentioned interval tree, but I do not think it would work here.
: * implement the merge of two int arrays A and B, using the similar way as
: merge-sort
: Further question:
: if A's size is over the max possible value of the int array, how do u
| g*****i
发帖数: 2162 | 3 * 把一个字符串转换成32bit的整数
题目是要把字符串和整数11对应吗?
假设有k个character是可以用在字符串里面的,把字符串看成k进制的数字,每个字符对应一个数字(要character set转化成number set)然后转成2进制.
【在 h******8 的大作中提到】
: 从这里看到的，没看到好的solution. 大家讨论一下？
: * 把一个字符串转换成32bit的整数
: * 一个range的序列（链表或数组），如[1,3], [2,6], [8,10]，[15,18]
: 写程序合并有重叠的range，比如上面的序列合并为[1,6], [8,10], [15,18]
: 如果这个序列不是静态的，而是一个数据流，如何 处理？
: Ppl mentioned interval tree, but I do not think it would work here.
: * implement the merge of two int arrays A and B, using the similar way as
: merge-sort
: Further question:
: if A's size is over the max possible value of the int array, how do u
| h******8
发帖数: 55 | 4 There could be multiple intervals that has overlapping with the current one.
How could you do the merging stuff?
the
left
【在 g*********s 的大作中提到】
:
: interval tree works.
: u always check if the latest interval has overlap with the intervals in the
: tree. if not, do insert. if overlap is found, merge the overlapped one and
: check the interval again. in the extreme case u only have one interval left
: finally.
| g***s
发帖数: 3811 | 5 找到最左边的那个。然后开始跟next元素合并到没有重合。
one.
【在 h******8 的大作中提到】
: There could be multiple intervals that has overlapping with the current one.
: How could you do the merging stuff?
:
: the
: left
| h******8
发帖数: 55 | 6 首先肯定不会是1-1map. 32位整数是有限的，字符串是无限的。
我觉得就是构造hash函数。但是要求collision概率小。而且hash table利用率高。我
想到的是用素数为底。
对应一个数字(要character set转化成number set)然后转成2进制.
【在 g*****i 的大作中提到】
: * 把一个字符串转换成32bit的整数
: 题目是要把字符串和整数11对应吗?
: 假设有k个character是可以用在字符串里面的,把字符串看成k进制的数字,每个字符对应一个数字(要character set转化成number set)然后转成2进制.
| g***s
发帖数: 3811 | 7 http://stackoverflow.com/questions/299304/why-does-javas-hashco
as-a-multiplier
【在 h******8 的大作中提到】
: 首先肯定不会是1-1map. 32位整数是有限的，字符串是无限的。
: 我觉得就是构造hash函数。但是要求collision概率小。而且hash table利用率高。我
: 想到的是用素数为底。
:
: 对应一个数字(要character set转化成number set)然后转成2进制.
| g**e
发帖数: 6127 | 8 如果要快，用7不是更好？ 7*i == (i<<3)-i 只用左移三位，如果要大质数，127也行呀
【在 g***s 的大作中提到】
: http://stackoverflow.com/questions/299304/why-does-javas-hashco
: as-a-multiplier
| g***s
发帖数: 3811 | 9 a better link:
http://computinglife.wordpress.com/2008/11/20/why-do-hash-funct
prime-numbers/
行呀
【在 g**e 的大作中提到】
: 如果要快，用7不是更好？ 7*i == (i<<3)-i 只用左移三位，如果要大质数，127也行呀
|
|
