作者推荐
本文涉及知识点
数位 数论
LeetCode2999. 统计强大整数的数目
给你三个整数 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 的后缀。
示例 1：
输入：start = 1, finish = 6000, limit = 4, s = “124”
输出：5
解释：区间 [1…6000] 内的强大数字为 124 ，1124 ，2124 ，3124 和 4124 。这些整数的各个数位都 <= 4 且 “124” 是它们的后缀。注意 5124 不是强大整数，因为第一个数位 5 大于 4 。
这个区间内总共只有这 5 个强大整数。
示例 2：
输入：start = 15, finish = 215, limit = 6, s = “10”
输出：2
解释：区间 [15…215] 内的强大整数为 110 和 210 。这些整数的各个数位都 <= 6 且 “10” 是它们的后缀。
这个区间总共只有这 2 个强大整数。
示例 3：
输入：start = 1000, finish = 2000, limit = 4, s = “3000”
输出：0
解释：区间 [1000…2000] 内的整数都小于 3000 ，所以 “3000” 不可能是这个区间内任何整数的后缀。
提示：
1 <= start <= finish <= 1015
1 <= limit <= 9
1 <= s.length <= floor(log10(finish)) + 1
s 数位中每个数字都小于等于 limit 。
s 不包含任何前导 0 。
数论
len1 = s.length s1 = 下届.right(len1) s2 = 上届.right(len1)
枚举合法数字的长度len2。
我们当前数字假定除掉作为后缀的s，余下的部分为x，x的len = len2- len1。统计x的可能数量。难点：上下界可能包括limit以外的数字。
分类讨论：
一，x就是下界的前缀。
二,x就是上界的前缀。
三，x同时是上下界的前缀，做特殊处理，此时情况四不会存在。return (s1<=s)&&(s <= s2);
四,x 在上下界前缀之间。
处理余下的三种情况：
一，下界的前缀不包括limit及以上数字且s1 <= s，数量+1。
二，上界的前缀不包括limit及以上数字且s <= s2，数量+1。
三，小于上界前缀的数量-小于下界前缀的数量-等于下届前缀的数量。加上s后，一定在上下界之间。
等于下届前缀的数量：如果下届前缀不包括limit及以上数字，为1；否则为0。
小于下界（上界）前缀t的数量：
小于t的数量必定有j位前缀相同,j∈ [ 0 , l e n ) \in[0,len)∈[0,len) 枚举j。
bitMin = (0==j)?1:0 最高位不能是0，其它位可以为0。
∑ j : 0 l e n − 1 ( m i n ( t [ j ] , l i m i t + 1 ) − b i t M i n ) × ( l i m i t + 1 ) l e n − j − 1 \sum_{j:0}^{len-1}(min(t[j],limit+1)-bitMin)\times (limit+1)^{len-j-1}∑j:0len−1(min(t[j],limit+1)−bitMin)×(limit+1)len−j−1
就是当前位的取值数量 乘以 后面各位的取值数量。如果s[j]>=limit，则不会存在(j+1)位及更多位前缀相等。提前退出循环。
代码
核心代码
class Solution { public: long long numberOfPowerfulInt(long long start, long long finish, int limit, string s) { m_s = s; m_limit = limit; const string strLow = std::to_string(start); const string strUp = std::to_string(finish); const int len0 = strLow.length(); const int len = strUp.length(); m_vUnit.emplace_back(1); for (int i = 1; i <= 15; i++) { m_vUnit.emplace_back(m_vUnit.back() * (limit+1)); } if (len0 == len) { return Do(strLow, strUp); } long long llRet = 0; llRet += Do(strLow, string(len0, limit+ '0')); for (int i = len0+1; i < len; i++) { llRet += Do(("1" + string(i - 1, '0')).c_str(), string(i, limit + '0').c_str()); } llRet +=Do (("1" + string(len - 1, '0')).c_str(), strUp.c_str()); return llRet; } long long Do(string strLow, string strUp) { const int len = strLow.length() - m_s.length(); if (len < 0 ) { return 0; } auto [llCnt1, bVilid1] = LessEqual(len, strLow); auto [llCnt2, bVilid2] = LessEqual(len, strUp); bool b1 = (strLow.substr(len) <= m_s) && (bVilid1); bool b2 = (strUp.substr(len) >= m_s) && (bVilid2); if (strLow.substr(0,len) == strUp.substr(0,len)) { return b1 && b2; } return (llCnt2 - llCnt1 - (bVilid1&&len)) + b1 + b2; } std::pair<long long, bool> LessEqual(int len,const string& s ) { bool bVilid = true; long long llCnt = 0; for (int i = 0; i < len; i++) {//计算小于数量 const int bitMin = (0 == i) ? 1 : 0; if (bVilid) { llCnt += (min(s[i] - '0', m_limit + 1) - bitMin) * m_vUnit[len - i - 1]; } if (s[i] > m_limit + '0') { bVilid = false; } } return make_pair(llCnt, bVilid); } vector<long long> m_vUnit; string m_s; int m_limit; };
测试用例
template<class T,class T2> void Assert(const T& t1, const T2& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { long long start, finish; int limit; string s; { Solution sln; start = 1, finish = 1000000000000000, limit = 5, s = "1000000000000000"; auto res = sln.numberOfPowerfulInt(start, finish, limit, s); Assert(1, res); } { Solution sln; start = 1829505, finish = 1955574, limit = 7, s = "11223"; auto res = sln.numberOfPowerfulInt(start, finish, limit, s); Assert(0, res); } { Solution sln; start = 5398, finish = 6415, limit = 8, s = "101"; auto res = sln.numberOfPowerfulInt(start, finish, limit, s); Assert(1, res); } { Solution sln; start = 1, finish = 6000, limit = 4, s = "124"; auto res = sln.numberOfPowerfulInt(start, finish, limit, s); Assert(5, res); } { Solution sln; start = 15, finish = 215, limit = 6, s = "10"; auto res = sln.numberOfPowerfulInt(start, finish, limit, s); Assert(2, res); } { Solution sln; start = 10, finish = 1844, limit = 5, s = "12"; auto res = sln.numberOfPowerfulInt(start, finish, limit, s); Assert(12, res); } { Solution sln; start = 1, finish = 2000, limit = 8, s = "1"; auto res = sln.numberOfPowerfulInt(start, finish, limit, s); Assert(162, res); } { Solution sln; start = 1829505, finish = 1255574165, limit =7, s = "11223"; auto res = sln.numberOfPowerfulInt(start, finish, limit, s); Assert(5470, res); } { Solution sln; start = 15398, finish = 1424153842, limit = 8, s = "101"; auto res = sln.numberOfPowerfulInt(start, finish, limit, s); Assert(783790, res); } }
优化
n位数，可以看成包括(m-n)个前置0的m位数。
class Solution { public: long long numberOfPowerfulInt(long long start, long long finish, int limit, string s) { m_s = s; m_limit = limit; string strLow = std::to_string(start); const string strUp = std::to_string(finish); if (strLow.length() < strUp.length()) { strLow = string(strUp.length() - strLow.length(), '0')+strLow; } m_vUnit.emplace_back(1); for (int i = 1; i <= 15; i++) { m_vUnit.emplace_back(m_vUnit.back() * (limit+1)); } return Do(strLow, strUp); } long long Do(string strLow, string strUp) { const int len = strLow.length() - m_s.length(); if (len < 0 ) { return 0; } auto [llCnt1, bVilid1] = LessEqual(len, strLow); auto [llCnt2, bVilid2] = LessEqual(len, strUp); bool b1 = (strLow.substr(len) <= m_s) && (bVilid1); bool b2 = (strUp.substr(len) >= m_s) && (bVilid2); if (strLow.substr(0,len) == strUp.substr(0,len)) { return b1 && b2; } return (llCnt2 - llCnt1 - (bVilid1&&len)) + b1 + b2; } std::pair<long long, bool> LessEqual(int len,const string& s ) { bool bVilid = true; long long llCnt = 0; for (int i = 0; i < len; i++) {//计算小于数量 if (bVilid) { llCnt += (min(s[i] - '0', m_limit + 1) - 0) * m_vUnit[len - i - 1]; } if (s[i] > m_limit + '0') { bVilid = false; } } return make_pair(llCnt, bVilid); } vector<long long> m_vUnit; string m_s; int m_limit; };
