【数位】【数论】【分类讨论】2999. 统计强大整数的数目

作者推荐

动态规划的时间复杂度优化

本文涉及知识点

数位 数论

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 <= 10¹⁵
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$\in [0,len)$ 枚举j。
bitMin = (0==j)?1:0 最高位不能是0，其它位可以为0。
${\sum }_{j:0}^{len-1}(min(t[j],limit+1)-bitMin)\times (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;
};