java - 面试问题:优化一种函数，该函数可以找到给定范围内包含x或y的数字数量，但不能同时找到两者？

Question

问题是这样的：
你能写一个方法来找出包含6或8的数字的数量吗包含两个数字的数字不应计算在内。例如
3628个
不是有效数字
，但是
3528个
是
最初，我考虑将数字转换成字符串，并检查它是否包含两个数字中的任何一个。最后我想出了这样的办法。我以为用算术运算计算会更快这段代码通过了6个测试用例中的4个。但是有一个2秒的时间限制，最后两个测试用例的范围是52位和64位整数，这使得计算时间更长，这也是我使用long的原因。我考虑了一下，但没想到一个更有效的解决办法。你能进一步优化这个问题吗？有可能符合2秒的时限吗？

    public static long countNums(int start, int end) {
    long nums = 0;

    for (long i = start; i < end; i++) {

        boolean six = false;
        boolean eight = false;
        long curr = i;

        while (curr != 0) {

            if (curr % 10 == 6) {
                six = true;
            }
            if (curr % 10 == 8) {
                eight = true;
            }
            if (six && eight) {
                break;
            }
            curr /= 10;
        }

        if ((six && !eight) || (eight && !six)) {
            nums++;
        }

    }

    return nums;
}

Answer 1

在对这个问题的各种回答中提出了一些想法，这些想法肯定会使用非常少的CPU时间解决这个问题成为可能我们可以将它们放在一起产生一个非常有效的解决方案，其时间复杂度在（较大）参数的长度上是线性的。
我们可以从一些观察开始。
首先，对于任何需要满足某个谓词p的区间内整数计数的问题，我们可以使用半开区间和恒等式来简化该问题[注1]：

Count(P, [lo, hi) ) = Count(P, [0, hi) ) - Count(P, [0, lo) )

所以我们只需要考虑从0开始的间隔。
其次，在这个特殊的问题中，我们还可以假设hi和lo是相同的长度（数字），因为lo可以用前导零来写。这是可能的，因为0不是一个“特殊”数字，所以在数字的开头加一个0不会改变谓词的真值。
第三，由于这里我们要处理两个不同的谓词（“contains a 6”和“contains an 8”），因此记住包含/排除原则很有用：

Count(P or Q) = Count(P) + Count(Q) - Count(P and Q)

以及“排除或”原则：

Count(P xor Q) = Count(P or Q) - Count(P and Q)

[注2]
在这之后，让我们从解决由给定长度的所有数字组成的区间的计数问题开始。
这很容易计算。我们从那个时间间隔内的一些简单的计数问题开始。我们将从谓词n和Count(P, [0, 10n) )开始，这对于十进制扩展分别包含6或8的数字是正确的我们知道这个区间正好有10n个整数。如果我们排除一个数字值（Has6或Has8），那么我们在每个位置留下9个可能的数字，从而导致计数为9n。因此，6和8都是10n−9n。
同样，我们可以将Count(Has6)计算为10n-8n，因为当我们列出既没有6也没有8的数字时，每个位置只有8个可能的数字（8n个可能），其余的数字有6或8或两者。
这样，我们可以使用包含/排除原则来计算：
Count(Has8)
因此

Count(Has6 xor Has8) = Count(Has6 or Has8) − Count(Has6 and Has8)
                    = Count(Has6 or Has8) − (Count(Has6) + Count(Has8) - Count(Has6 or Has8))
                    = 2 * Count(Has6 or Has8) − 2 * Count(Has6)
                    = 2 * ((10n − 8n) − (10n − 9n))
                    = 2 * (9n − 8n)

利用这个非常简单的公式，我们可以计算从0开始的任何范围内的间隔数。假设我们有Count(Has6 or Has8)范围，其中Count(Has6 and Has8) = Count(Has6) + Count(Has8) - Count(Has6 or Has8)和[0, ab...)是数字。我们可以将其划分为a范围：

[00000, 10000)
[10000, 20000)
...
[(a-1)0000, a0000)
[a0000, ab...)

对于第一组范围，有两种可能性。如果第一个数字既不是6也不是8，那么可以忽略它，并且可以使用上面的公式2*（9n−1−8n−1）计算剩余b位数的计数。另一方面，如果第一个数字是6或8，则该范围的计数为9n-1，因为不包含其他特殊数字的所有整数都被计数。
对于最后一个范围，我们还有两种可能性。如果a不是特殊的，我们可以忽略它并添加间隔n-1的计数（概念上使用递归调用）。如果a是特殊的，那么我们需要计算[0000, b000)中没有其他特殊数字的整数数，这可以通过使用类似的一次一位数算法来实现（如下所示）。
在伪代码中：

count(lo, hi):
  Return count_to(hi) - count_to(lo).

count_to(hi):
  Let n be the number of digits in hi.
  If n is 0, return 0.
  Let d be the first digit of hi.
  Let rest be the rest of hi (without its first digit).
  If d is 0, 1, 2, 3, 4 or 5:
    Return d * 2 * (9 ** (n - 1) - 8 ** (n - 1))
           + count_to(rest).
  If d is 7:
    Return 6 * 2 * (9 ** (n - 1) - 8 ** (n - 1))
           + 9 ** (n - 1) 
           + count_to(rest).
  If d is 9:
    Return 7 * 2 * (9 ** (n - 1) - 8 ** (n - 1))
           + 2 * 9 ** (n - 1) 
           + count_to(rest).
  If d is 6:
    Return 6 * 2 * (9 ** (n - 1) - 8 ** (n - 1))
           + count_without(rest, 8).
  If d is 8:
    Return 7 * 2 * (9 ** (n - 1) - 8 ** (n - 1))
           + 9 ** (n - 1) 
           + count_without(rest, 6).

count_without(hi, avoid):
  Let n be the number of digits in hi.
  If n is 0, return 0.
  Let d be the first digit of hi.
  Let rest be the rest of hi (without its first digit).
  If d is less than avoid:
    Return d * 9 ** (n - 1)
           + count_without(rest, avoid)
  If d is equal to avoid:
    Return d * 9 ** (n - 1)
  If d is greater than avoid:
    Return (d - 1) * 9 ** (n - 1)
           + count_without(rest, avoid)

由于递归调用都可以使用累加器参数转换为尾部调用，因此我们可以将递归转换为原始数字上的简单循环。或者，更好地说，有两个循环：一个循环在不包含任何特殊数字的前缀上，第二个循环在发现特殊数字时开始，循环在数字的其余部分，避免另一个特殊数字。
下面是一个经过测试的C语言实现：

/* The following were generated with a little C program, not included. */
static const unsigned maxPow10 = 20;
static const unsigned long long pow8[] = {
                     1ULL,                    8ULL,                   64ULL,                  512ULL,                 4096ULL,
                 32768ULL,               262144ULL,              2097152ULL,             16777216ULL,            134217728ULL,
            1073741824ULL,           8589934592ULL,          68719476736ULL,         549755813888ULL,        4398046511104ULL,
        35184372088832ULL,      281474976710656ULL,     2251799813685248ULL,    18014398509481984ULL,   144115188075855872ULL
};
static const unsigned long long pow9[] = {
                     1ULL,                    9ULL,                   81ULL,                  729ULL,                 6561ULL,
                 59049ULL,               531441ULL,              4782969ULL,             43046721ULL,            387420489ULL,
            3486784401ULL,          31381059609ULL,         282429536481ULL,        2541865828329ULL,       22876792454961ULL,
       205891132094649ULL,     1853020188851841ULL,    16677181699666569ULL,   150094635296999121ULL,  1350851717672992089ULL
};  
static const unsigned long long pow10[] = {
                     1ULL,                   10ULL,                  100ULL,                 1000ULL,                10000ULL,
                100000ULL,              1000000ULL,             10000000ULL,            100000000ULL,           1000000000ULL,
           10000000000ULL,         100000000000ULL,        1000000000000ULL,       10000000000000ULL,      100000000000000ULL,
      1000000000000000ULL,    10000000000000000ULL,   100000000000000000ULL,  1000000000000000000ULL, 10000000000000000000ULL
};            

/* Return the number of integers in the range [0, lim % 10**n) which
 * do not have the digit avoid in their decimal representation.
 * (lim % 10**n is the last n digits of lim).
 */
static unsigned long long countWithout(unsigned long long lim, int n, int avoid) {
  unsigned long long count = 0;
  while (n) {
    /* isolate the nth last digit of lim and decrement n */
    unsigned digit = lim / pow10[--n] % 10;
    /* For each starting digit less than digit except avoid,
     * add 9**n qualifying integers. If the avoided digit is
     * encountered, stop.
     */
    count += (digit <= avoid ? digit : digit - 1) * pow9[n];
    if (digit == avoid) break;
  }
  return count;
}

static unsigned long long countTo(unsigned long long lim) {
  unsigned long long count = 0;
  unsigned n = maxPow10;
  /* Loop over the digits in lim until a 6 or an 8 is encountered or all of the
   * digits have been processed. For each digit position, add the appropriate
   * number of qualifying numbers which start with a smaller digit, using either
   * the xor formula 2 * (9**n - 8**n) or the exclusion formula 9**n, depending
   * on whether the starting digit is special or not. Once a special digit is
   * encountered, use countWithout to process the rest of the digits.
   */
  while (n) {
    unsigned digit = lim / pow10[--n] % 10;
    switch (digit) {
      default:count += digit * (2 * (pow9[n] - pow8[n]));
              break;
      case 6: count += 6 * (2 * (pow9[n] - pow8[n]));
              return count + countWithout(lim, n, 8);
      case 7: count += 6 * (2 * (pow9[n] - pow8[n])) + pow9[n];
              break;
      case 8: count += 7 * (2 * (pow9[n] - pow8[n])) + pow9[n];
              return count + countWithout(lim, n, 6);
      case 9: count += 7 * (2 * (pow9[n] - pow8[n])) + 2 * pow9[n];
              break;
    }
  }
  return count;
}

unsigned long long countBetween(unsigned long long lo, unsigned long long hi) {
  return hi > lo ? countTo(hi) - countTo(lo) : 0;
}

笔记
如果我们需要在一个封闭的时间间隔内计数，我们可以尝试使用另一个明显的标识：

Count(P, [lo, hi] ) = Count(P, [lo, hi + 1) )

但是，由于如果a是最大的可表示整数，那么[0000, b000)将溢出，因此如果hi + 1满足谓词，我们最好先计算hi，然后再加1。
把这两个放在一起可以让我们：

Count(P xor Q) = Count(P) + Count(Q) - 2*Count(P and Q)

这很有趣，但在这个问题上没有直接的用处。