当前位置：首页 > news >正文

【C++动态规划】2801. 统计范围内的步进数字数目|2367

news 2025/4/28 8:09:17

本文涉及知识点

C++动态规划

LeetCode2801. 统计范围内的步进数字数目

给你两个正整数 low 和 high ，都用字符串表示，请你统计闭区间 [low, high] 内的步进数字数目。
如果一个整数相邻数位之间差的绝对值都恰好是 1 ，那么这个数字被称为步进数字。
请你返回一个整数，表示闭区间 [low, high] 之间步进数字的数目。
由于答案可能很大，请你将它对 10⁹ + 7 取余后返回。
注意：步进数字不能有前导 0 。
示例 1：
输入：low = “1”, high = “11”
输出：10
解释：区间 [1,11] 内的步进数字为 1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 ，9 和 10 。总共有 10 个步进数字。所以输出为 10 。
示例 2：

输入：low = “90”, high = “101”
输出：2
解释：区间 [90,101] 内的步进数字为 98 和 101 。总共有 2 个步进数字。所以输出为 2 。

提示：

1 <= int(low) <= int(high) < 10¹⁰⁰
1 <= low.length, high.length <= 100
low 和 high 只包含数字。
low 和 high 都不含前导 0 。

数位dp

自定义状态0到9。自定义状态和当前值相差1，合法。其它非法。

代码

核心代码

template<int MOD = 1000000007>
class C1097Int
{
public:C1097Int(long long llData = 0) :m_iData(llData% MOD){}C1097Int  operator+(const C1097Int& o)const{return C1097Int(((long long)m_iData + o.m_iData) % MOD);}C1097Int& operator+=(const C1097Int& o){m_iData = ((long long)m_iData + o.m_iData) % MOD;return *this;}C1097Int& operator-=(const C1097Int& o){m_iData = (m_iData + MOD - o.m_iData) % MOD;return *this;}C1097Int  operator-(const C1097Int& o){return C1097Int((m_iData + MOD - o.m_iData) % MOD);}C1097Int  operator*(const C1097Int& o)const{return((long long)m_iData * o.m_iData) % MOD;}C1097Int& operator*=(const C1097Int& o){m_iData = ((long long)m_iData * o.m_iData) % MOD;return *this;}bool operator<(const C1097Int& o)const{return m_iData < o.m_iData;}C1097Int pow(long long n)const{C1097Int iRet = 1, iCur = *this;while (n){if (n & 1){iRet *= iCur;}iCur *= iCur;n >>= 1;}return iRet;}C1097Int PowNegative1()const{return pow(MOD - 2);}int ToInt()const{return m_iData;}
private:int m_iData = 0;;
};template<class ELE, class ResultType, ELE minEle, ELE maxEle>
class CLowUperr
{
public:CLowUperr(int iResutlCount):m_iResutlCount(iResutlCount){}void Init(const ELE* pLower, const ELE* pHigh, int iNum){m_vPre.assign(4, vector<ResultType>(m_iResutlCount));m_iNum = iNum;if (iNum <= 0){return;}InitPre(pLower, pHigh);m_iNum--;while (m_iNum--){pLower++;pHigh++;vector<vector<ResultType>> dp(4, vector<ResultType>(m_iResutlCount));OnInitDP(dp);//处理非边界for (auto tmp = minEle; tmp <= maxEle; tmp++){OnDo(dp[0], m_vPre[0], tmp);}//处理下边界OnDo(dp[1], m_vPre[1], *pLower);for (auto tmp = *pLower + 1; tmp <= maxEle; tmp++){OnDo(dp[0], m_vPre[1], tmp );}//处理上边界OnDo(dp[2], m_vPre[2], *pHigh );for (auto tmp = minEle; tmp < *pHigh; tmp++){OnDo(dp[0], m_vPre[2], tmp );}//处理上下边界if (*pLower == *pHigh){OnDo(dp[3], m_vPre[3], *pLower);}else{OnDo(dp[1], m_vPre[3], *pLower );for (auto tmp = *pLower + 1; tmp < *pHigh; tmp++){OnDo(dp[0], m_vPre[3], tmp );}OnDo(dp[2], m_vPre[3], *pHigh );}m_vPre.swap(dp);}}ResultType Total(int iMinIndex, int iMaxIndex){ResultType ret;for (int status = 0; status < 4; status++){for (int index = iMinIndex; index <= iMaxIndex; index++){ret += m_vPre[status][index];}}return ret;}
protected:int m_iNum;const int m_iResutlCount;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;}OnInitFirstEle(m_vPre[iStatus], cur);}}virtual void OnDo(vector<ResultType>& dp, const vector<ResultType>& vPre, ELE cur) = 0;virtual void OnInitFirstEle(vector<ResultType>& vPre,const ELE curValue){int curIndex = curValue - minEle;if (curIndex < m_iResutlCount){vPre[curIndex] = 1;}}virtual void OnInitDP(vector<vector<ResultType>>& dp){}vector<vector<ResultType>> m_vPre;
};class CMyCLowUperr :public CLowUperr<char, C1097Int<>, '0', '9'>
{
public:CMyCLowUperr():CLowUperr<char, C1097Int<>, '0', '9'>(10){}virtual void OnDo(vector<C1097Int<>>& dp, const vector<C1097Int<>>& vPre, char cur){int index = cur - '0';if (index > 0 ){dp[index] += vPre[index - 1];}if (index < 9){dp[index] += vPre[index + 1];}}
};
class Solution {
public:int countSteppingNumbers(string low, string high) {		if (low.length() == high.length()){Do(low, high);}else{Do(low, string(low.length(), '9'));for (int i = low.length() + 1; i < high.length(); i++){Do("1" + string(i - 1, '0'), string(i, '9'));}Do("1" + string(high.length() - 1, '0'), high);}return m_biRet.ToInt();}void Do(string low, string high){CMyCLowUperr lu;lu.Init(low.data(), high.data(), low.length());m_biRet += lu.Total(0, 9);}C1097Int<> m_biRet = 0;
};

单元测试

		string low,  high;TEST_METHOD(TestMethod11){low = "1", high = "11";auto res = Solution().countSteppingNumbers(low, high);AssertEx(10, res);}TEST_METHOD(TestMethod12){low = "90", high = "101";auto res = Solution().countSteppingNumbers(low, high);AssertEx(2, res);}TEST_METHOD(TestMethod13){low = "106", high = "121";auto res = Solution().countSteppingNumbers(low, high);AssertEx(1, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功