我将为您分步解释：
第一步：
要解决X和Y之间的范围问题，通常可以先从0到X和0到Y-1进行计数，然后相减得到结果。例如，如果您有一个像f(N)这样的函数，用于计算0到N之间至少有一半数字相同的数字数量，则最终结果如下：
f(X) - f(Y-1)
long long f_less(int curDigit, int favNum, int favNumCountSoFar, int nonFavNum, int nonFavNumCountSoFar, int maxDigit){
if(curDigit == maxDigit ){
//for numbers with even maxDigit there may be a case when we have 2 favorite numbers
//and we should count them only once. like 522552
if(favNumCountSoFar*2 == maxDigit && favNumCountSoFar == nonFavNumCountSoFar) return 1;
if(2*favNumCountSoFar >= maxDigit) return 2;
return 0;
}
long long res = 0;
for(int i=(curDigit==0?1:0);i<=9;++i) //skip the leading zero
if(i==favNum)
res += f_less(curDigit+1, favNum, favNumCountSoFar + 1, nonFavNum, nonFavNumCountSoFar,maxDigit);
else
res += f_less(curDigit+1, favNum, favNumCountSoFar, i, (i==nonFavNum?nonFavNumCountSoFar+1:1),maxDigit);
return res;
}
并对0到9的所有数字进行调用：
long long res = 0;
for(int maxDigit = 1; maxDigit < NUMBER_OF_DIGITS(N); ++maxDigit)
for(int favNumber = 0; favNumber < 10; ++favNumber)
res += f_less(0, favNumber, 0, -1, 0, maxDigit);
第四步：
最后，我们需要计算 f_equal。在递归函数中，我们需要将数字保留为字符串，以便始终检查是否仍在小于 N 的范围内。以下是 f_equal 的实现（可以再次使用记忆化或进行自底向上的处理）：
string s = NUM_TO_STRING(N);
int maxDigit = s.size();
long long f_equal(int curDigit, int favNum, int favNumCountSoFar,int nonFavNum, int nonFavNumCountSoFar, bool isEqual){ //isEqual checks that whether our number is equal to N or it's lesser than it
if(curDigit == maxDigit ){
//for numbers with even maxDigit there may be a case when we have 2 favorite numbers
//and we should count them only once. like 522552
if(favNumCountSoFar*2 == maxDigit && favNumCountSoFar == nonFavNumCountSoFar) return 1;
if(2*favNumCountSoFar >= maxDigit) return 2;
return 0;
}
long long res = 0;
for(int i=(curDigit==0?1:0);i<=9;++i){ //skip the leading zero
if(isEqual && i>(s[curDigit]-'0')) break;
if(i==favNum)
res += f_equal(curDigit+1, favNum, favNumCountSoFar + 1, nonFavNum, nonFavNumCountSoFar, isEqual && (i==(s[curDigit]-'0')));
else
res += f_equal(curDigit+1, favNum, favNumCountSoFar, i, (i==nonFavNum?nonFavNumCountSoFar+1:1), isEqual && (i==(s[curDigit]-'0')));
}
return res;
}
并将其称为：
long long res = 0;
for(int favNumber = 0; favNumber < 10; ++favNumber)
res += f_equal(0, favNumber,0, -1, 0, true);
res/2。代码已经测试并且运行良好。L，并且该数字有 R 个位于 L 右侧的数字，我们可以通过以下方式计算出如何分配 d 数字的 (N / 2) 或更多个：import math, operator, collections
# Assumes L has at least one digit set
# f({'string':'12', 'digit_frequencies':[0,1,1,0,0,0,0,0,0,0], 'num_digit_frequencies': 2}, 6)
def f(L, N):
R = N - len(L['string'])
count = 0
counted = False
for digit_frequency in L['digit_frequencies']:
start = int(math.ceil(N / 2.0)) - digit_frequency
if start > R:
continue
for i in xrange(start, R + 1):
if not (N & 1) and not counted:
if L['num_digit_frequencies'] == 1 and not digit_frequency and i == N / 2:
count = count - choose(R, i)
if L['num_digit_frequencies'] == 2 and digit_frequency and not any([x > N / 2 for x in L['digit_frequencies']]) and i + digit_frequency == N / 2:
count = count - choose(R, i)
counted = True
m = 9**(R - i)
n = R - i + 1
k = i
count = count + m * choose(n + k - 1, k)
return count
# A brute-force function to confirm results
# check('12', 6)
def check(prefix, length):
result = [x for x in xrange(10**(length - 1), 10**length) if len(str(x)) == length and str(x).startswith(prefix) and isValid(str(x))]
print result
return len(result)
def isValid(str):
letters = collections.Counter(str)
return any([x >= math.ceil(len(str) / 2.0) for x in letters.values()])
# https://dev59.com/W2445IYBdhLWcg3wR4VO
def choose(n, r):
r = min(r, n-r)
if r == 0: return 1
numer = reduce(operator.mul, xrange(n, n-r, -1))
denom = reduce(operator.mul, xrange(1, r+1))
return numer//denom
...000000.000000...。0；因此所有整数都可以计算。0。同样适用于0和-1之间的数字。float getCount(int x, int y) {
if(x == y) return 0.0; // Special case (no numbers are between x and y)
return INFINITY; // The closest value to the correct answer that a computer can use
}
1231是否符合条件？你的例子不具有代表性。 - AnT stands with Russia