我有几个数字范围.这些范围不重叠 - 因为它们不重叠,逻辑结果是任何时候任何数字都不能成为多个范围的一部分.每个范围都是连续的(单个范围内没有孔,所以8到16的范围实际上包含8到16之间的所有数字),但两个范围之间可能存在空洞(例如范围从64开始到128,下一个范围从256开始并转到384),因此某些数字可能根本不属于任何范围(在此示例中,数字129到255不属于任何范围).
我得到一个号码,需要知道该号码属于哪个范围......如果它属于任何范围.否则我需要知道它不属于任何范围.当然速度很重要; 我不能简单地检查所有范围是O(n),因为可能有数千个范围.
一个简单的解决方案是将所有数字保存在已排序的数组中并对其运行二进制搜索.这至少会给我O(log n).当然二进制搜索必须稍微修改,因为它必须始终检查范围的最小和最大数量.如果要查找的数字介于两者之间,我们找到了正确的范围,否则我们必须搜索当前范围之下或之上的范围.如果最后只剩下一个范围并且数字不在该范围内,则该数字根本不在范围内,我们可以返回"未找到"结果.
范围也可以在某种树形结构中链接在一起.这基本上就像是带有二分搜索的排序列表.优点是修改树比修改数组(添加/删除范围)更快,但不像我们浪费一些额外的时间来保持树平衡,树可能会在一段时间内变得非常不平衡,这将导致比排序数组上的二进制搜索慢得多.
人们可以争论哪种解决方案更好或更差,因为实际上搜索和修改操作的数量几乎是平衡的(每秒执行的搜索和添加/删除操作数量相同).
对于这类问题,是否有比排序列表或树更好的数据结构？也许在最好的情况下可能比O(log n)更好,在最坏的情况下可能比O(log n)更好？
此处可能有用的一些其他信息如下:所有范围始终以2的幂的倍数开始和结束.它们总是以相同的2的幂开始和结束(例如,它们以4的倍数或8的倍数或16的倍数开始/结束,依此类推).在运行时,2的功率不能改变.在添加第一个范围之前,必须设置2的幂,并且所有已添加的范围必须以此值的倍数开始/结束,直到应用程序终止.我认为这可以用于优化,好像它们都以例如8的倍数开始,我可以忽略所有比较操作的前3位,其他位将告诉我范围(如果有的话).
我读到了关于树和树的范围.这些是问题的最佳解决方案吗？有没有更好的解决方案？问题听起来类似于malloc实现必须做的事情(例如,每个freed内存块属于一系列可用内存,malloc实现必须找到哪一个),那么通常如何解决这个问题呢？
这条线
p *1..10
完全一样的事情
(1..10).each { |x| puts x }
它给你以下输出:
$ ruby -e "p *1..10"
1
2
3
4
5
6
7
8
9
10
例如,与textmate合作时,这是一个很好的捷径,但是星号是做什么的？这是如何运作的？在网上找不到任何东西......
在给定边界之间制作包含均匀间隔数字(不仅仅是整数)的任意长度列表的pythonic方法是什么？例如:
my_func(0,5,10) # ( lower_bound , upper_bound , length )
# [ 0, 0.5, 1, 1.5, 2, 2.5, 3, 3.5, 4, 4.5 ]
请注意,该Range()函数仅处理整数.还有这个:
def my_func(low,up,leng):
list = []
step = (up - low) / float(leng)
for i in range(leng):
list.append(low)
low = low + step
return list
看起来太复杂了.有任何想法吗？
我需要一个MySQL表来保存2011-01-01和2011-12-31之间的所有日期.我创建了一个包含一个列名为"_date"的表,类型为DATE.
使用什么查询可以用所有期望的日期填充表格(而不必手动输入)？
编辑修复了toro2k的评论.
Range#include?并且Range#cover?似乎在源代码看作是不同的1,2,和它们在不同的效率.
t = Time.now
500000.times do
("a".."z").include?("g")
end
puts Time.now - t # => 0.504382493
t = Time.now
500000.times do
("a".."z").cover?("g")
end
puts Time.now - t # => 0.454867868
看源代码,Range#include?似乎比复杂Range#cover?.为什么不能Range#include?简单地说别名是Range#cover?什么？
我需要填充一个表,该表将存储2个给定日期之间的日期范围:09/01/11 - 10/10/11
所以在这种情况下,表格将从09年1月1日开始并存储每天直到它到达10/10/11我想知道在SQL Server中是否有一种灵活的方式 - 我目前正在使用SQL Server 2008 . 谢谢
为什么会(1..5).each迭代1,2,3,4,5,但(5..1)不会？它返回Range.
1.9.2p290 :007 > (1..5).each do |i| puts i end
1
2
3
4
5
=> 1..5
1.9.2p290 :008 > (5..1).each do |i| puts i end
=> 5..1
我有一个方法可以获得这个类的许多对象
class Range<T>
{
public T Start;
public T End;
}
在我的情况T是DateTime,但让我们使用int的简便性.我想要一种方法,将这些范围折叠成覆盖相同"区域"但不重叠的区域.
所以,如果我有以下范围
该方法应该给我
猜猜它会被称为联盟？我想方法签名看起来像这样:
public static IEnumerable<Range<T>> Collapse<T>(
this IEnumerable<Range<T>>,
IComparable<T> comparer)
{
...
}
我在这里看了一些类似的其他问题,但我还没有找到它的实现.这个答案和同一问题的其他一些答案描述了算法,但我不太清楚我是否理解算法.也不是特别擅长实现算法,所以我希望有人可以帮助我.
为什么这段代码有效
std::vector<int> intVector(10);
for(auto& i : intVector)
std::cout << i;
这不是吗？
std::vector<bool> boolVector(10);
for(auto& i : boolVector)
std::cout << i;
在后一种情况下,我收到一个错误
错误:从'std :: _ Bit_iterator :: reference {aka std :: _ Bit_reference}'类型的右值开始,无效初始化'std :: _ Bit_reference&'类型的非const引用
Run Code Online (Sandbox Code Playgroud)for(auto& i : boolVector)
我有一个列表中的范围，如：
ranges = [(1, 50), (49, 70), (75, 85), (84, 88), (87, 92)]
我想找到可以从这些构建的最长范围（当它们相互重叠时）。
预期输出：
[(1, 70), (75, 92)]
我有一个解决方案，但是它太复杂了，我相信一定有一个更简单的解决方案来解决这个问题
我的解决方案：
def overlap(x, y):
return range(max(x[0], y[0]), min(x[-1], y[-1]) + 1)
ranges = [(1, 50), (49, 70), (75, 85), (84, 88), (87, 92)]
beg, end = min([x[0] for x in ranges]), 0
for i in ranges:
if i[0] == beg:
end = i[1]
while beg:
for _ in ranges:
for i in ranges:
if i[1] > end and …