本文涉及知识点
下载及打开打包代码的方法兼述单元测试
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 * 109
动态规划之数位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;
