佛山市企业网站建设哪家好,温州免费建站模板,网站建设费 无形资产,我要学习网站建设作者推荐
动态规划的时间复杂度优化
本文涉及知识点
数位 数论
LeetCode2999. 统计强大整数的数目
给你三个整数 start #xff0c;finish 和 limit 。同时给你一个下标从 0 开始的字符串 s #xff0c;表示一个 正 整数。 如果一个 正 整数 x 末尾部分是 s #xff08…作者推荐
动态规划的时间复杂度优化
本文涉及知识点
数位 数论
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余下的部分为xx的len len2- len1。统计x的可能数量。难点上下界可能包括limit以外的数字。 分类讨论 一x就是下界的前缀。 二,x就是上界的前缀。 三x同时是上下界的前缀做特殊处理此时情况四不会存在。return (s1s)(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 (0j)?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],limit1)-bitMin)\times (limit1)^{len-j-1} ∑j:0len−1(min(t[j],limit1)−bitMin)×(limit1)len−j−1 就是当前位的取值数量 乘以 后面各位的取值数量。如果s[j]limit则不会存在(j1)位及更多位前缀相等。提前退出循环。
代码
核心代码
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() * (limit1));}if (len0 len){return Do(strLow, strUp);}long long llRet 0;llRet Do(strLow, string(len0, limit 0));for (int i len01; 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 - (bVilid1len)) b1 b2;}std::pairlong 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);}vectorlong long m_vUnit;string m_s;int m_limit;
};测试用例
templateclass T,class T2
void Assert(const T t1, const T2 t2)
{assert(t1 t2);
}templateclass T
void Assert(const vectorT v1, const vectorT 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() * (limit1));}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 - (bVilid1len)) b1 b2;}std::pairlong 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);}vectorlong long m_vUnit;string m_s;int m_limit;
};
