题目描述
给你三个整数 start
,finish
和 limit
。同时给你一个下标从 0 开始的字符串 s
,表示一个 正 整数。
如果一个 正 整数 x
末尾部分是 s
(换句话说,s
是 x
的 后缀),且 x
中的每个数位至多是 limit
,那么我们称 x
是 强大的。
请你返回区间 [start..finish]
内强大整数的 总数目 。
如果一个字符串 x
是 y
中某个下标开始(包括 0
),到下标为 y.length - 1
结束的子字符串,那么我们称 x
是 y
的一个后缀。比方说,25
是 5125
的一个后缀,但不是 512
的后缀。
样例
输入:start = 1, finish = 6000, limit = 4, s = "124"
输出:5
解释:区间 [1..6000] 内的强大数字为 124,1124,2124,3124 和 4124。
这些整数的各个数位都 <= 4 且 "124" 是它们的后缀。
注意 5124 不是强大整数,因为第一个数位 5 大于 4。
这个区间内总共只有这 5 个强大整数。
输入:start = 15, finish = 215, limit = 6, s = "10"
输出:2
解释:区间 [15..215] 内的强大整数为 110 和 210。这些整数的各个数位都 <= 6 且 "10" 是它们的后缀。
这个区间总共只有这 2 个强大整数。
输入:start = 1000, finish = 2000, limit = 4, s = "3000"
输出:0
解释:区间 [1000..2000] 内的整数都小于 3000,所以 "3000" 不可能是这个区间内任何整数的后缀。
限制
1 <= start <= finish <= 10^15
1 <= limit <= 9
1 <= s.length <= floor(log10(finish)) + 1
s
数位中每个数字都小于等于limit
。s
不包含任何前导 0。
算法
(数位统计) $O(\log finish)$
- 按照经典数位统计的思路,将区间
[start, finish]
拆分为[1, finish + 1) - [1, start)
独立计算。 - 对于给定的目标 $x$,从 $x$ 的最高位遍历到固定后缀的前一位,最高位可以填充 $0, 1, \dots$ 直到 $limit$ 或者当前数位减一。可以直接利用预处理的幂次数组,统计填充这些数字时贡献的答案数(当前位到固定后缀之间,每个位置都可以填充 $0$ 到 $limit$)。
- 当前位固定填充为原数字,并判断填充后,能否满足不大于 $limit$ 且拼上固定后缀小于目标值 $x$。如果不满足,则直接结束。
- 最后,别忘了固定后缀之前都填充了原始数字后,是否仍然小于目标值 $x$。如果满足,则答案累加 1。
时间复杂度
- 预处理的幂次数组时间复杂度为 $O(\log finish)$。
- 分解数字,并逐位累加答案的时间复杂度为 $O(\log finish)$。
- 故总时间复杂度为 $O(\log finish)$。
空间复杂度
- 需要 $O(\log finish)$ 的额外空间存储幂次数组,数位信息。
C++ 代码
#define LL long long
const int N = 16;
class Solution {
private:
LL power_l[N], power_10[N];
LL solve(LL x, int limit, const string &s) {
LL t = x;
vector<int> p;
while (t) {
p.push_back(t % 10);
t /= 10;
}
const int n = p.size(), m = s.size();
LL ss = 0;
for (int i = 0; i < m; i++)
ss = ss * 10 + s[i] - '0';
LL ans = 0, prev = 0;
for (int i = n - 1; i >= m; i--) {
ans += min(p[i], limit + 1) * power_l[i - m];
prev += p[i] * power_10[i];
if (p[i] > limit || prev + ss >= x)
return ans;
}
if (prev + ss < x)
++ans;
return ans;
}
public:
LL numberOfPowerfulInt(LL start, LL finish, int limit, string s) {
power_l[0] = power_10[0] = 1;
for (int i = 1; i < N; i++) {
power_l[i] = power_l[i - 1] * (limit + 1);
power_10[i] = power_10[i - 1] * 10;
}
return solve(finish + 1, limit, s) - solve(start, limit, s);
}
};