我想在输入部分输入时根据范围列表（最小值，最大值）检查（数字）输入；换句话说，我需要一个优雅的算法来检查一个数字的前缀与一个范围（不使用正则表达式）。
示例测试用例：
1 is in ( 5, 9) -> false
6 is in ( 5, 9) -> true
1 is in ( 5, 11) -> true (as 10 and 11 are in the range)
1 is in ( 5, 200) -> true (as e.g. 12 and 135 are in the range)
11 is in ( 5, 12) -> true
13 is in ( 5, 12) -> false
13 is in ( 5, 22) -> true
13 is in ( 5, 200) -> true (as 130 is in the range)
2 is in (100, 300) -> true (as 200 is in the range)
你有什么主意吗？
我相信输入是可以接受的，当且仅当：
或者
例如，第一条规则是必需的13 is in range (135, 140)。例如，第二条规则是必需的2 is in range (1000, 3000)。
第二条规则可以通过一系列乘以 10 来有效地测试，直到缩放的输入超过上限。
一个迭代公式：
bool in_range(int input, int min, int max)
{
if (input <= 0)
return true; // FIXME handle negative and zero-prefixed numbers
int multiplier = 1;
while ((input + 1) * multiplier - 1 < min) // min <= [input]999
multiplier *= 10; // TODO consider overflow
return input * multiplier <= max; // [input]000 <= max
}
更简单的[编辑：更有效；见下文]方法是使用截断整数除法：
bool in_range(int input, int min, int max)
{
if (input <= 0)
return true;
while (input < min) {
min /= 10;
max /= 10;
}
return input <= max;
}
测试和分析：
#include <iostream>
#include <chrono>
bool ecatmur_in_range_mul(int input, int min, int max)
{
int multiplier = 1;
while ((input + 1) * multiplier - 1 < min) // min <= [input]999
multiplier *= 10; // TODO consider overflow
return input * multiplier <= max; // [input]000 <= max
}
bool ecatmur_in_range_div(int input, int min, int max)
{
while (input < min) {
min /= 10;
max /= 10;
}
return input <= max;
}
bool t12_isInRange(int input, int min, int max)
{
int multiplier = 1;
while(input*multiplier <= max)
{
if(input >= min / multiplier) return true;
multiplier *= 10;
}
return false;
}
struct algo { bool (*fn)(int, int, int); const char *name; } algos[] = {
{ ecatmur_in_range_mul, "ecatmur_in_range_mul"},
{ ecatmur_in_range_div, "ecatmur_in_range_div"},
{ t12_isInRange, "t12_isInRange"},
};
struct test { int input, min, max; bool result; } tests[] = {
{ 1, 5, 9, false },
{ 6, 5, 9, true },
{ 1, 5, 11, true }, // as 10 and 11 are in the range
{ 1, 5, 200, true }, // as e.g. 12 and 135 are in the range
{ 11, 5, 12, true },
{ 13, 5, 12, false },
{ 13, 5, 22, true },
{ 13, 5, 200, true }, // as 130 is in the range
{ 2, 100, 300, true }, // as 200 is in the range
{ 13, 135, 140, true }, // Ben Voigt
{ 13, 136, 138, true }, // MSalters
};
int main() {
for (auto a: algos)
for (auto t: tests)
if (a.fn(t.input, t.min, t.max) != t.result)
std::cout << a.name << "(" << t.input << ", " << t.min << ", " << t.max << ") != "
<< t.result << "\n";
for (auto a: algos) {
std::chrono::time_point<std::chrono::system_clock> start = std::chrono::system_clock::now();
for (auto t: tests)
for (int i = 1; i < t.max * 2; ++i)
for (volatile int j = 0; j < 1000; ++j) {
volatile bool r = a.fn(i, t.min, t.max);
(void) r;
}
std::chrono::time_point<std::chrono::system_clock> end = std::chrono::system_clock::now();
std::cout << a.name << ": "
<< std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count() << '\n';
}
}
令人惊讶的是（至少对我而言）迭代除法最快：
ecatmur_in_range_mul: 17331000
ecatmur_in_range_div: 14711000
t12_isInRange: 15646000
bool isInRange(int input, int min, int max)
{
int multiplier = 1;
while(input*multiplier <= max)
{
if(input >= min / multiplier) return true;
multiplier *= 10;
}
return false;
}
它通过了你所有的测试用例。
我在思考@Ben Voigt 漂亮解决方案的证明时想到了这个新的简单解决方案：
让我们回到我们进行数字比较的小学。问题就像：检查数字“ A ”是否在数字“ B ”和数字“ C ”的范围内
解决方案：在数字的左侧添加必要的零（所以我们在所有数字中都有相同的数字）我们从最左边的数字开始。将其与其他两个数字中的等效数字进行比较。
如果A中的数字小于B中的数字或大于C中的数字，则A不在范围内。
如果不是，我们使用 A 中的下一个数字以及B和C中的等价物重复该过程。
重要问题：我们为什么不马上停下来？为什么我们检查下一个数字？
重要答案：因为A的数字介于B和C的等价物之间，到目前为止还可以，但还没有足够的理由做出决定！（很明显吧？）
反过来，这意味着可能有一组数字会使A超出范围。
并且，同样地
可能有一组数字可以将A放在范围内
这是另一种说法A可能是范围内数字的前缀。
这不就是我们要找的吗？！:D
该算法的主干基本上是对每个输入事件的简单比较：
根据问题的需要，此处的 false 和 true 表示“到目前为止”的情况。
给定一个值n，从半开范围 [ n , n + 1) 开始，然后按数量级进行：
继续直到迭代的范围与目标范围重叠，或者两个范围不能再重叠。
#include <iostream>
bool overlaps(int a, int b, int c, int d) {
return a < c && c < b || c < a && a < d;
}
bool intersects(int first, int begin, int end) {
int last = first + 1;
++end;
while (first <= end) {
if (overlaps(first, last, begin, end))
return true;
first *= 10;
last *= 10;
}
return false;
}
int main(int argc, char** argv) {
std::cout << std::boolalpha
<< intersects( 1, 5, 9) << '\n'
<< intersects( 6, 5, 9) << '\n'
<< intersects( 1, 5, 11) << '\n'
<< intersects( 1, 5, 200) << '\n'
<< intersects(11, 5, 12) << '\n'
<< intersects(13, 5, 12) << '\n'
<< intersects(13, 5, 22) << '\n'
<< intersects(13, 5, 200) << '\n'
<< intersects( 2, 100, 300) << '\n'
<< intersects(13, 135, 140) << '\n';
}
使用范围对于防止遗漏案例是必要的。考虑n = 2 和目标范围 [21, 199]。2不在范围内，所以我们乘以10；20不在范围内，所以我们再乘以10；200 不在范围内，也没有更高的数字，因此朴素算法以假阴性终止。
一种简单的解决方案是生成范围内的所有 N 位前缀。所以，11 is in ( 5, 12)你想要 5 到 12 之间所有数字的两位前缀。显然，这只是 10、11 和 12。
一般来说，对于数字 X 到 Y，可能的 N 位前缀可以通过以下算法获得：
X = MIN(X, 10^(N-1) ) ' 9 has no 2-digit prefix so start at 10
Y = Y - (Y MOD 10^N) ' 1421 has the same 2 digit prefix as 1400
WHILE (X < Y)
LIST_PREFIX += PREFIX(N, X) ' Add the prefix of X to the list.
X += 10^(TRUNCATE(LOG10(X)) - N+1) ' For N=2, go from 1200 to 1300
我更喜欢使用已经实现的算法的方法。虽然许多其他解决方案使用递归除法10，但我认为最好使用具有O(1)复杂性的 10 基对数，这样整个解决方案的复杂度为O(1).
让我们把问题分成两部分。
第一部分将处理number * 10^n介于min和max至少一个之间的情况n。这将让我们检查例如 ifnumber = 12和min,max = 11225,13355，即x = 12000 = 12*10^3在minand之间max。如果此测试检查通过，则表示结果为True。
第二部分将处理ornumber开头的情况。例如，如果and ，第一个测试将失败，因为不在and之间（以及任何其他数字都将失败）。但是第二次测试会发现那是开始和返回。minmaxnumber = 12min,max = 12325,1455512000minmax12*10^nn1212325True
让我们检查一下，x = number*10^n等于或大于的第一个min是否小于或等于max(so min <= x <= max, where x is number*10^n for any integer n)。如果它大于max，那么所有其他xes 都会更大，因为我们取了最小的。
log(number*10^n) > log(min)
log(number) + log(10^n) > log(min)
log(number) + n > log(min)
n > log(min) - log(number)
n > log(min/number)
为了得到要比较的数字，我们只计算第一个满意的n：
n = ceil(log(min/number))
然后计算数字x：
x = number*10^n
我们应该检查我们的数字是否是任一边界的字面开头。
我们只是x从与 相同的数字开始计算number并在末尾用 s 填充0，具有与 相同的长度min：
magnitude = 10**(floor(log10(min)) - floor(log10(number)))
x = num*magnitude
然后检查min's 和x差异（在大小范围内）是否小于1和大于或等于0：
0 <= (min-x)/magnitude < 1
所以，如果numberis121和minis 132125，那么magnitudeis 1000，x = number*magnitude将会是121000。min - x给出132125-121000 = 11125，它应该小于1000（否则min开始会大于121），所以我们magnitude通过除以它的值并比较它来比较它1。如果minis 就可以，但如果 is 就不行121000，这就是为什么and 。min1220000 <=< 1
相同的算法适用于max。
将它全部合并到伪代码中给出了这个算法：
def check(num,min,max):
# num*10^n is between min and max
#-------------------------------
x = num*10**(ceil(log10(min/num)))
if x>=min and x<=max:
return True
# if num is prefix substring of min
#-------------------------------
magnitude = 10**(floor(log10(min)) - floor(log10(num)))
if 0 <= (min-num*magnitude)/magnitude < 1:
return True
# if num is prefix substring of max
#-------------------------------
magnitude = 10**(floor(log10(max)) - floor(log10(num)))
if 0 <= (max-num*magnitude)/magnitude < 1:
return True
return False
可以通过避免重复计算来优化此代码log10(num)。此外，在最终解决方案中，我将从浮点数范围转到整数范围 ( magnitude = 10**int(floor(log10(max)) - floor(log10(num))))，然后执行所有比较而不进行除法，即0 <= (max-num*magnitude)/magnitude < 1-> 0 <= max-num*magnitude < magnitude。这将减少舍入错误的可能性。
此外，也可以用 替换magnitude = 10**(floor(log10(min)) - floor(log10(num))) ，magnitude = 10**(floor(log10(min/num)))其中log10只计算一次。但我不能证明它总是会带来正确的结果，我也不能反驳它。如果有人能证明这一点，我将不胜感激。
测试（在 Python 中）：http: //ideone.com/N5R2j（您可以编辑输入以添加其他测试）。
(input >= lower_bound) && input <= upper_bound
OR
(f(input) >= lower_bound) && (f(input) <= upper_bound)
OR
(lower_bound - f(input) < pow(10, n_digits_upper_bound - n_digits_input)) &&
(lower_bound - f(input) > 0)
where
f(input) == (input * pow(10, n_digits_upper_bound - n_digits_input))
1 is in ( 5, 9) -> 1 * pow(10,0) -> same -> false
6 is in ( 5, 9) -> true
1 is in ( 5, 11) -> 1 * pow(10,1) -> 10 is in (5,11) -> true
1 is in ( 5, 200) -> 1 * pow(10,2) -> 100 is in (5, 200) -> true
11 is in ( 5, 12) -> true
13 is in ( 5, 12) -> 13 * pow(10,0) -> same -> false
13 is in ( 5, 22) -> true
13 is in ( 5, 200) -> true
2 is in (100, 300) -> 2 * pow(10,2) -> 200 is in (100,300) -> true
4 is in (100, 300) -> 4 * pow(10,2) -> 400 is in (100,300) -> false
13 is in (135, 140) -> 135 - 130 -> true
14 is in (135, 139) -> 135 - 140 -> false
Yes another answer. For input X and bounds MIN and MAX
WHILE (X < MIN)
IF X is a prefix of MIN
x = 10*x + next digit of MIN
ELSE
x = 10*x
RETURN (x>= MIN && x<=MAX)
This works by "typing" the next lowest digit. So the hard case 13 in (135, 140) adds a 5 to produce 135, not a zero.
无论您选择哪种实现方法，您都应该考虑构建大量单元测试。因为您提出的问题就像您为测试驱动开发 (TDD) 编写测试一样。所以我建议，当你在等待一个合适的算法从堆栈溢出中弹出时，编写你的单元测试：
如果您提供的示例没有在您的示例中产生结果，则使您的测试失败。写几个其他的极限测试用例来确定。然后，如果您碰巧使用了错误或错误的算法，您很快就会知道。一旦你的测试通过，你就会知道你已经达到了你的目标。
另外，它可以保护您免受将来的任何回归
所有困难情况都是下限的位数少于上限的情况。只需将范围分成两个（或三个）。如果 AB 是集合 A 和 B 的并集，则x in AB蕴含x in A或x in B。所以：
13 is in (5, 12)=>13 is in (5, 9)或13 is in (10, 12)
13 is in (5, 120)=>13 is in (5, 9)或13 is in (10, 99)或13 is in (100, 120)
然后，截断以匹配长度。IE
13 is in (5, 120)=>13 is in (5, 9)或13 is in (10, 99)或13 is in (100 , 120)
在第二次重写之后，它变成了一个简单的数字检查。请注意，如果您有范围10,99出现，那么您有所有可能的 2 位前缀并且实际上不需要检查，但这是一种优化。（我假设我们忽略前缀 00-09）
也许我没有考虑到这一点，但假设整数的 Min-Max 范围都是正数（即大于或等于零），这个代码块应该可以很好地解决问题：
bool CheckRange(int InputValue, int MinValue, int MaxValue)
{
// Assumes that:
// 1. InputValue >= MinValue
// 2. MinValue >= 0
// 3. MinValue <= MaxValue
//
if (InputValue < 0) // The input value is less than zero
return false;
//
if (InputValue > MaxValue) // The input value is greater than max value
return false;
//
if (InputValue == 0 && InputValue < MinValue)
return false; // The input value is zero and less than a non-zero min value
//
int WorkValue = InputValue; // Seed a working variable
//
while (WorkValue <= MaxValue)
{
if (WorkValue >= MinValue && WorkValue <= MaxValue)
return true; // The input value (or a stem) is within range
else
WorkValue *= 10; // Not in range, multiply by 10 to check stem again
}
//
return false;
}
我现在会删除这个答案，只是它显示了一个失败的方法。
检查后
Str(min).StartWith(input)，您需要以数字方式检查10^n*Val(input)范围内是否有任何内容，正如 Ben Voight 当前的回答所说。
由于 Ben Voigt 的评论而编辑：（我错过了他在当前答案中的第一点：前缀匹配到最小值是可以的。）
根据@Ben Voigt 的见解，我的解决方案是检查Min StartsWith当前输入。如果不是，PadRight则当前输入0的长度Max为字符串。然后，如果这个修改后的输入在词法上（即视为字符串）介于两者之间Min，Max那就没问题了。
伪代码：
Confirm input has only digits, striping leading 0s
(most easily done by converting it to an integer and back to a string)
check = Str(min).StartsWith(input)
If Not check Then
testInput = input.PadRight(Len(Str(max)), '0')
check = Str(min) <= testInput && testInput <= Str(max)
End If
好吧，派对有点晚了，但这里...
请注意，我们在这里讨论的是用户输入，因此仅// TODO: consider overflow. 验证用户输入是一场战争，偷工减料最终会导致 IED 引爆。（好吧，好吧，也许不是那么戏剧化，但仍然......）事实上，ecatmur 有用的测试工具中只有一种算法可以正确处理极端情况（），并且测试工具本身也会{23, 2147483644, 2147483646, false}进入无限循环t.max大的。
唯一通过的是 ecatmur_in_range_div，我认为它非常好。但是，可以通过添加一些检查来使其（稍微）更快：
bool in_range_div(int input, int min, int max)
{
if (input > max) return false;
if (input >= min) return true;
if (max / 10 >= min) return true;
while (input < min) {
min /= 10;
max /= 10;
}
return input <= max;
}
“取决于”多快；如果 min 和 max 是编译时常量，这将特别有用。我认为前两个测试很明显；第三个可以通过多种方式证明，但最简单的就是观察 ecatmur 循环的行为：当循环结束时，输入 >= min 但 < 10*min，因此如果 10*min < max，则输入必须小于最大值。
用除法而不是乘法来表达算术应该是一种习惯；我知道我们大多数人从小就认为分裂是缓慢的，必须避免。但是，除法与乘法不同，不会溢出。确实，每当您发现自己在写作时：
if (a * k < b) ...
或者
for (..., a < b, a *= k)
或这些主题的其他变体，您应该立即将其标记为整数溢出，并将其更改为等效除法。
实际上，除了一种重要（但常见）的情况外，加法也是如此：
if (a + k < b) ...
或者
a += k; if (a < b) ...
也是不安全的，除非k 为 1，并且您知道在加法之前 a < b。该异常使正常的 for 循环无需过多考虑即可工作。但请注意这一点，我曾经将其用作面试问题的一部分：
// enumerate every kth element of the range [a, b)
assert(a < b);
for (; a < b; a += k) { ... }
可悲的是，很少有候选人得到它。
int input = 15;
int lower_bound = 1561;
int upper_bound = 1567;
int ipow = 0;
while (lower_bound > 0) {
if (lower_bound > input) {
++ipow;
lower_bound = lower_bound / 10;
} else {
int i = pow(10, ipow) * input;
if (i < upper_bound) {
return true;
}
return false;
}
}
return false;