本文涉及知识点
数位 数论
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 。
分析
当时没用数位dp的原因是：没想到如何处理 limit。
其实办法很简单，枚举到大于limit的直接抛弃。
代码
核心代码
class KMP { public: virtual int Find(const string& s, const string& t) { CalLen(t); m_vSameLen.assign(s.length(), 0); for (int i1 = 0, j = 0; i1 < s.length(); ) { for (; (j < t.length()) && (i1 + j < s.length()) && (s[i1 + j] == t[j]); j++); //i2 = i1 + j 此时s[i1,i2)和t[0,j)相等 s[i2]和t[j]不存在或相等 m_vSameLen[i1] = j; //t[0,j)的结尾索引是j-1，所以最长公共前缀为m_vLen[j-1]，简写为y 则t[0,y)等于t[j-y,j)等于s[i2-y,i2) if (0 == j) { i1++; continue; } const int i2 = i1 + j; j = m_vLen[j - 1]; i1 = i2 - j;//i2不变 } for (int i = 0; i < m_vSameLen.size(); i++) {//多余代码是为了增加可测试性 if (t.length() == m_vSameLen[i]) { return i; } } return -1; } vector<int> m_vSameLen;//m_vSame[i]记录 s[i...]和t[0...]最长公共前缀，增加可调试性 static vector<int> Next(const string& s) {// j = vNext[i] 表示s[0,i]的最大公共前后缀是s[0,j] const int len = s.length(); vector<int> vNext(len, -1); for (int i = 1; i < len; i++) { int next = vNext[i - 1]; while ((-1 != next) && (s[next + 1] != s[i])) { next = vNext[next]; } vNext[i] = next + (s[next + 1] == s[i]); } return vNext; } protected: void CalLen(const string& str) { m_vLen.resize(str.length()); for (int i = 1; i < str.length(); i++) { int next = m_vLen[i - 1]; while (str[next] != str[i]) { if (0 == next) { break; } next = m_vLen[next-1]; } m_vLen[i] = next + (str[next] == str[i]); } } int m_c; vector<int> m_vLen;//m_vLen[i] 表示t[0,i]的最长公共前后缀 }; template<class ELE, class ResultType, ELE minEle, ELE maxEle> class CLowUperr { public: CLowUperr(int iCustomStatusCount) :m_iCustomStatusCount(iCustomStatusCount) { } void Init(const ELE* pLower, const ELE* pHigh, int iNum) { m_vPre.assign(4, vector<ResultType>(m_iCustomStatusCount)); if (iNum <= 0) { return; } InitPre(pLower, pHigh); iNum--; while (iNum--) { pLower++; pHigh++; vector<vector<ResultType>> dp(4, vector<ResultType>(m_iCustomStatusCount)); OnInitDP(dp); //处理非边界 for (auto tmp = minEle; tmp <= maxEle; tmp++) { OnEnumOtherBit(dp[0], m_vPre[0], tmp); } //处理下边界 OnEnumOtherBit(dp[1], m_vPre[1], *pLower); for (auto tmp = *pLower + 1; tmp <= maxEle; tmp++) { OnEnumOtherBit(dp[0], m_vPre[1], tmp); } //处理上边界 OnEnumOtherBit(dp[2], m_vPre[2], *pHigh); for (auto tmp = minEle; tmp < *pHigh; tmp++) { OnEnumOtherBit(dp[0], m_vPre[2], tmp); } //处理上下边界 if (*pLower == *pHigh) { OnEnumOtherBit(dp[3], m_vPre[3], *pLower); } else { OnEnumOtherBit(dp[1], m_vPre[3], *pLower); for (auto tmp = *pLower + 1; tmp < *pHigh; tmp++) { OnEnumOtherBit(dp[0], m_vPre[3], tmp); } OnEnumOtherBit(dp[2], m_vPre[3], *pHigh); } m_vPre.swap(dp); } } ResultType Sum(int iMinMask,int iMaxMask)const { ResultType iRet = 0; for (int status = 0; status < 4; status++) { for (int mask = iMinMask; mask <= iMaxMask; mask++) { iRet += m_vPre[status][mask]; } } return iRet; } protected: const int m_iCustomStatusCount; virtual void OnEnumOtherBit(vector<ResultType>& dp, const vector<ResultType>& vPre, ELE curValue) = 0; virtual void OnEnumFirstBit(vector<ResultType>& vPre, const ELE curValue) = 0; virtual void OnInitDP(vector<vector<ResultType>>& dp) { } private: void InitPre(const ELE* const pLower, const ELE* const pHigh) { for (ELE cur = *pLower; cur <= *pHigh; cur++) { int iStatus = 0; if (*pLower == cur) { iStatus = *pLower == *pHigh ? 3 : 1; } else if (*pHigh == cur) { iStatus = 2; } OnEnumFirstBit(m_vPre[iStatus], cur); } } vector<vector<ResultType>> m_vPre; }; class CMyLowUperr : public CLowUperr<char, long long, '0', '9'> { public: typedef long long ResultType; typedef char ELE; CMyLowUperr(int limit,const string& strEnd) :CLowUperr<char, long long, '0', '9'>(strEnd.length()+1),m_chLimit('0'+limit), m_strEnd(strEnd) { m_vNext = KMP::Next(strEnd); } virtual void OnEnumOtherBit(vector<ResultType>& dp, const vector<ResultType>& vPre, ELE curValue) { if (curValue > m_chLimit) { return; } for (int preMask = 0; preMask < m_iCustomStatusCount; preMask++) { const int mask = CalSameLen(preMask, curValue); dp[mask] += vPre[preMask]; } } virtual void OnEnumFirstBit(vector<ResultType>& vPre, const ELE curValue) { if (curValue > m_chLimit) { return; } const int mask = CalSameLen(0, curValue); vPre[mask]++; } protected: int CalSameLen(int oldLen, const ELE curValue) { while ((oldLen >= m_vNext.size()) || (curValue != m_strEnd[oldLen])) { if (0 == oldLen) { break; } oldLen = m_vNext[oldLen - 1]+1; } return oldLen + (curValue == m_strEnd[oldLen]); } const char m_chLimit; vector<int> m_vNext; const string m_strEnd; }; class CNumBitHelp { public: CNumBitHelp(int limit, string strEnd):m_iLimt(limit),m_strEnd(strEnd) { } long long DoAllLen(long long low, long long high) { string strLow = std::to_string(low); string strHigh = std::to_string(high); long long iRet = 0; const int len1 = strLow.length(); const int len2 = strHigh.length(); if (len1 == len2) { return Do(strLow, strHigh); } iRet += Do(strLow, string(len1, '9')); for (int i = len1 + 1; i < len2; i++) { iRet += Do("1" + string(i - 1, '0'), string(i, '9')); } iRet += Do("1" + string(len2 - 1, '0'), strHigh); return iRet; } protected: long long Do(const string strLow, const string& strHigh) { CMyLowUperr my(m_iLimt,m_strEnd); my.Init(strLow.data(), strHigh.data(), strLow.length()); return my.Sum(m_strEnd.length(), m_strEnd.length()); } const int m_iLimt; const string m_strEnd; }; class Solution { public: long long numberOfPowerfulInt(long long start, long long finish, int limit, string s) { CNumBitHelp hlp(limit, s); return hlp.DoAllLen(start, finish); } };
测试用例
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() { int start = 1, finish = 6000, limit = 4; string s = "124"; { start = 1, finish = 6000, limit = 4; s = "124"; auto res = Solution().numberOfPowerfulInt(start, finish, limit, s); Assert(5, res); } { start = 15, finish = 215, limit = 6, s = "10"; auto res = Solution().numberOfPowerfulInt(start, finish, limit, s); Assert(2, res); } { start = 1000, finish = 2000, limit = 4, s = "3000"; auto res = Solution().numberOfPowerfulInt(start, finish, limit, s); Assert(0, res); } }
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关
下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
