【数位】【数论】【分类讨论】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∈ [ 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;
};

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

作者推荐

本文涉及知识点

LeetCode2999. 统计强大整数的数目

数论

代码

核心代码

测试用例

优化

热门文章

最新文章

相关电子书