【数位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。如果之前的已经包括当前数字，则全部数字都是重复数字；否则，之前是重复数字，现在仍然是重复数字，之前不是重复数字，现在也不是。
{ d p [ m 1 ] . s e c o n d + = p r e [ m ] . f i r s t + p r e [ m ] . s e c o n d m = = m 1 d p [ m 1 ] . f i r s t + = p r e [ m ] . f i r s t d p [ m 1 ] . s e c o n d + = p r e [ m ] . s e c o n d e l s e

$$\begin{cases} dp[m1].second += pre[m].first + pre[m].second & m==m1\\ dp[m1].first+= pre[m].first \quad dp[m1].second += pre[m].second & else \\ \end{cases}$$ {dp[m1].second+=pre[m].first+pre[m].seconddp[m1].first+=pre[m].firstdp[m1].second+=pre[m].second​m==m1else​

动态规划的初始值

对每个合法数字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;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168

测试用例

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);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

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++**实现。