【C++动态规划数位dp】2376. 统计特殊整数|2120

本文涉及知识点

下载及打开打包代码的方法兼述单元测试
C++动态规划数位dp

LeetCode2376. 统计 特殊整数

如果一个正整数每一个数位都是互不相同的，我们称它是特殊整数。
给你一个正整数 n ，请你返回区间 [1, n] 之间特殊整数的数目。
示例 1：
输入：n = 20
输出：19
解释：1 到 20 之间所有整数除了 11 以外都是特殊整数。所以总共有 19 个特殊整数。
示例 2：
输入：n = 5
输出：5
解释：1 到 5 所有整数都是特殊整数。
示例 3：
输入：n = 135
输出：110
解释：从 1 到 135 总共有 110 个整数是特殊整数。
不特殊的部分数字为：22 ，114 和 131 。
提示：
1 <= n <= 2 * 10⁹

动态规划之数位dp

自定义状态：mask $\in$ [0,1 << 10)，mask&(1<<j) 表示数字j是否使用。

代码

核心代码

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 iEleCount){m_vPre.assign(4, vector<ResultType>(m_iCustomStatusCount));if (iEleCount <= 0){return;}InitPre(pLower, pHigh);iEleCount--;while (iEleCount--){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){}vector<vector<ResultType>> m_vPre;
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);}}};class CCharLowerUper : public CLowUperr<char, int, '0', '9'>{public:using CLowUperr<char, int, '0', '9'>::CLowUperr;int Total(){		int ans = 0;for (const auto& v : m_vPre) {ans += accumulate(v.begin(), v.end(), 0);}return ans;}protected:virtual void OnEnumFirstBit(vector<int>& vPre, const char curValue){const int index = curValue - '0';vPre[1<<index]++;}virtual void OnEnumOtherBit(vector<int>& dp, const vector<int>& vPre, char curValue){const int index = curValue - '0';for (int i = 0; i < vPre.size(); i++) {if (i & (1 << index)) { continue; }dp[i | (1 << index)] += vPre[i];}			}};class Solution {public:int countSpecialNumbers(int n) {string str = to_string(n);const int len = str.length();int ans = 0;for (int i = 1; i <= len; i++) {CCharLowerUper lu(1<<10);string strlower = "1" + string(i - 1, '0');string strUp = (len == i) ? str : string(i, '9');lu.Init(strlower.c_str(), strUp.c_str(), i);ans += lu.Total();}return ans;}};int n;

扩展阅读

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