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

Table of Contents

作者推荐

视频算法专题

本文涉及知识点

动态规划汇总

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。如果之前的已经包括当前数字，则全部数字都是重复数字；否则，之前是重复数字，现在仍然是重复数字，之前不是重复数字，现在也不是。
【数位dp】【动态规划】【状态压缩】【推荐】1012. 至少有 1 位重复的数字

动态规划的初始值

对每个合法数字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

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

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

原文链接：https://blog.csdn.net/he_zhidan/article/details/136099603