【数位dp】【动态规划】【状态压缩】【推荐】1012. 至少有 1 位重复的数字

作者推荐

视频算法专题

本文涉及知识点

动态规划汇总

LeetCode:1012. 至少有 1 位重复的数字

给定正整数 n，返回在 [1, n] 范围内具有 至少 1 位 重复数字的正整数的个数。
示例 1：
输入：n = 20
输出：1
解释：具有至少 1 位重复数字的正数（<= 20）只有 11 。
示例 2：
输入：n = 100
输出：10
解释：具有至少 1 位重复数字的正数（<= 100）有 11，22，33，44，55，66，77，88，99 和 100 。
示例 3：
输入：n = 1000
输出：262
提示：
1 <= n <= 10⁹

动态规划

动态规划的状态表示

自定义状态mask的含义：如果(1<<i)&mask 表示i已经使用，i取值范围[0,9]。每个状态有两个值：first，不含重复数字的数量；second，含重复数字的数量。

动态规划的转移方程

前一位的自定义状态mask，当前数字index。newMask = mask | ( 1 << index) m代码mask,m1代表newMask。如果之前的已经包括当前数字，则全部数字都是重复数字；否则，之前是重复数字，现在仍然是重复数字，之前不是重复数字，现在也不是。
$$\{\begin{array}{ll}dp[m1].second+=pre[m].first+pre[m].second& m==m1\\ dp[m1].first+=pre[m].firstdp[m1].second+=pre[m].second& else\end{array}$$

动态规划的初始值

对每个合法数字index。 pre[i<<index].first =1 。

动态规划的填表顺序

按封装类是按从高位到低位处理的。

动态规划的返回值

所有状态 second之和。

代码

核心代码

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)); 		if (iNum <= 0) 		{ 			return; 		} 		InitPre(pLower, pHigh); 		iNum--; 		while (iNum--) 		{ 			pLower++; 			pHigh++; 			vector<vector<ResultType>> dp(4, vector<ResultType>(m_iResutlCount)); 			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 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: 	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; 			} 			OnEnumFirstBit(m_vPre[iStatus], cur); 		} 	}  	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; };  class CCharLowerUper : public CLowUperr<char, pair<int, int>, '0', '9'> { public: 	CCharLowerUper():CLowUperr(1<<10) 	{  	} 	int Total() 	{ 		return Total(0, m_iResutlCount-1); 	} 	int Total(int iMinIndex, int iMaxIndex) 	{ 		int ret = 0; 		for (int index = iMinIndex; index <= iMaxIndex; index++) 		{ 			int cur = 0; 			for (int status = 0; status < 4; status++) 			{ 				cur += m_vPre[status][index].second; 			} 			ret += cur; 		} 		return ret; 	} protected:  	virtual void OnEnumFirstBit(vector<pair<int, int>>& vPre, const char curValue) 	{ 		const int index = curValue - '0'; 		vPre[1 << index].first = 1;	 	} 	virtual void OnEnumOtherBit(vector<pair<int, int>>& dp, const vector<pair<int, int>>& vPre, char curValue) 	{ 		const int index = curValue - '0'; 		for (int i = 0; i < m_iResutlCount; i++) 		{ 			const int iNewMask = (1 << index) | i; 			if (iNewMask == i ) 			{ 				dp[iNewMask].second += vPre[i].first + vPre[i].second; 			} 			else 			{ 				dp[iNewMask].first += vPre[i].first; 				dp[iNewMask].second +=  vPre[i].second; 			} 		} 	} };   class Solution { public: 	int numDupDigitsAtMostN(int n) { 		const string strN = std::to_string(n); 		const int len = strN.length(); 		int iRet = 0; 		for (int i = 1; i < len; i++) 		{ 			CCharLowerUper lu; 			lu.Init(("1" + string(i - 1, '0')).c_str(), string(i, '9').c_str(), i); 			iRet += lu.Total(); 		}  		CCharLowerUper lu; 		lu.Init(("1" + string(len - 1, '0')).c_str(), strN.c_str(), len); 		iRet += lu.Total(); 		return iRet; 	} }; 

测试用例

template<class T> void Assert(const T& t1, const T& 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() {	 	int n; 	{ 		Solution sln; 		n = 20; 		auto res = sln.numDupDigitsAtMostN(n); 		Assert(res, 1); 	} 	{ 		Solution sln; 		n = 100; 		auto res = sln.numDupDigitsAtMostN(n); 		Assert(res, 10); 	} 	{ 		Solution sln; 		n = 1000; 		auto res = sln.numDupDigitsAtMostN(n); 		Assert(res, 262); 	} } 

2023年1月版

int GetNotRepeateNum(int len, int iHasSel)
{
if (0 == len)
{
return 1;
}
if ((0 == iHasSel) && (1 == len))
{
return 10;
}
int iRet = 1;
if (iHasSel > 0)
{
for (int tmp = 10 - iHasSel; (tmp >= 2)&& len ; tmp–,len–)
{
iRet *= tmp;
}
}
else
{
iRet *= 9;
len–;
for (int tmp=9; (tmp>=2)&&len; len–,tmp–)
{
iRet *= tmp;
}
}
return iRet;
}
class Solution {
public:
int numDupDigitsAtMostN(int n) {
string s = std::to_string(n);
int iBitLen =s.length();
int iNotRepeatNum = 0;
for (int i = 1; i < iBitLen; i++)
{
iNotRepeatNum += GetNotRepeateNum(iBitLen-i, 0);
}
std::set setHasSel;
//位数相同，但最高为比n小
for (int i = 0; i < iBitLen; i++)
{
int iNum = s[i] - ‘0’;
if (1 + i == iBitLen)
{
iNum++;//最后一位可以相等
}
int iLessNum = iNum - std::distance(setHasSel.begin(), setHasSel.lower_bound(iNum));
if (0 == i && 1 != iBitLen)
{
iLessNum–;
}
if (iLessNum > 0 )
{
iNotRepeatNum += iLessNum * GetNotRepeateNum(iBitLen - i - 1, i + 1);
}
if (setHasSel.count(iNum))
{
break;
}
setHasSel.insert(iNum);
}
//扣掉0
return n - iNotRepeatNum + 1;
}
};

2023年8月版

class Solution {
public:
int numDupDigitsAtMostN(int n) {
auto str = std::to_string(n);
for (int i = 1; i < str.length(); i++)
{
Do(string(i, ‘9’));
}
Do(str);
return m_iRet;
}
void Do(const string& strUp)
{
int pre[2][1024] = { 0 };
{
const int iMax0 = strUp[0] - ‘0’;
for (int i = 1; i <= iMax0; i++)
{
pre[i == iMax0][1 << i ]++;
}
}
{
for (int i = 1; i < strUp.length(); i++)
{
int dp[2][1024] = { 0 };
//处理不在边界
for (int j = 0; j < 10; j++)
{
for (int pr = 0; pr < 1024; pr++)
{
int iMask = (pr & (1 << j)) ? 0 : (pr | (1 << j));
if (pr == 0)
{
iMask = 0;
}
dp[0][iMask] += pre[0][pr];
}
}
const int iMaxI = strUp[i] - ‘0’;
//处理在边界
for (int j = 0; j <= iMaxI; j++)
{
bool bUp = j == iMaxI;
for (int pr = 0; pr < 1024; pr++)
{
int iMask = (pr & (1 << j)) ? 0 : (pr | (1 << j));
if (pr == 0)
{
iMask = 0;
}
dp[bUp][iMask] += pre[1][pr];
}
}
memcpy(pre, dp, sizeof(dp));
}
}
m_iRet += pre[0][0] + pre[1][0];
}
int m_iRet = 0;
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。