【动态规划数位dp】2827. 范围中美丽整数的数目|2324

闻缺陷则喜何志丹

1060人浏览 · 2024-03-19 17:00:00

闻缺陷则喜何志丹 · 2024-03-19 17:00:00 发布

本文涉及知识点

LeetCode2827. 范围中美丽整数的数目

给你正整数 low ，high 和 k 。
如果一个数满足以下两个条件，那么它是美丽的：
偶数数位的数目与奇数数位的数目相同。
这个整数可以被 k 整除。
请你返回范围 [low, high] 中美丽整数的数目。
示例 1：
输入：low = 10, high = 20, k = 3
输出：2
解释：给定范围中有 2 个美丽数字：[12,18]

12 是美丽整数，因为它有 1 个奇数数位和 1 个偶数数位，而且可以被 k = 3 整除。
18 是美丽整数，因为它有 1 个奇数数位和 1 个偶数数位，而且可以被 k = 3 整除。
以下是一些不是美丽整数的例子：
16 不是美丽整数，因为它不能被 k = 3 整除。
15 不是美丽整数，因为它的奇数数位和偶数数位的数目不相等。
给定范围内总共有 2 个美丽整数。
示例 2：
输入：low = 1, high = 10, k = 1
输出：1
解释：给定范围中有 1 个美丽数字：[10]
10 是美丽整数，因为它有 1 个奇数数位和 1 个偶数数位，而且可以被 k = 1 整除。
给定范围内总共有 1 个美丽整数。
示例 3：
输入：low = 5, high = 5, k = 2
输出：0
解释：给定范围中有 0 个美丽数字。
5 不是美丽整数，因为它的奇数数位和偶数数位的数目不相等。
提示：
0 < low <= high <= 10⁹
0 < k <= 20

数位DP 2025

本题答案= $\sim high中符合条件的数量$ - $\sim low中符合条件的数目$ + lower是否符合
自定义状态：包括2部分，m1前n位奇数数量-偶数数量，m2前n位 $\mod k$ 。
结束合法状态和初始合法状态：m1=m2=0。

代码

		template<class ELE, class ResultType>
class IUpperDPCall
{
public:
	virtual void OnEnum(int n,vector<ResultType>& dp, const vector<ResultType>& vNext, ELE curValue, int iCustomStatusCount) = 0;
	virtual void OnInitEnd(vector<ResultType>& dp, vector<ResultType>& upDp) = 0;
};

template<class ELE, class ResultType>
class CUperrDP
{
public:
	CUperrDP(int iCustomStatusCount, IUpperDPCall<ELE, ResultType>& call, ELE minEle, ELE maxEle)
		:m_iCustomStatusCount(iCustomStatusCount),m_call(call),m_minEle(minEle),m_maxEle(maxEle)
	{
	}
	void Init(const ELE* pHigh, int iEleCount)
	{
		m_vDP.assign(iEleCount + 1, vector<ResultType>(m_iCustomStatusCount));
		m_vDpUpper = m_vDP;
		m_call.OnInitEnd(m_vDP.back(), m_vDpUpper.back());
		//预处理增加的一位
		for (int i = iEleCount - 1;i > 0;i--) {
			m_call.OnEnum(i,m_vDpUpper[i], m_vDpUpper[i + 1], pHigh[i],m_iCustomStatusCount);
			for (auto j = m_minEle; j < pHigh[i];j++) {
				m_call.OnEnum(i,m_vDpUpper[i], m_vDP[i + 1], j, m_iCustomStatusCount);
			}
			for (auto j = m_minEle; j <= m_maxEle;j++) {
				m_call.OnEnum(i,m_vDP[i], m_vDP[i + 1], j, m_iCustomStatusCount);
			}
		}
		m_call.OnEnum(0,m_vDpUpper[0], m_vDpUpper[1], pHigh[0], m_iCustomStatusCount);
		for (auto j = m_minEle; j < pHigh[0];j++) {
			m_call.OnEnum(0,m_vDP[0], m_vDP[1], j, m_iCustomStatusCount);
		}
	}
	ResultType Sum(int iMinCustomStatu, int iMaxCustomStatu) {
		ResultType ret = 0;
		for (int i = iMinCustomStatu; i <= iMaxCustomStatu;i++) {
			ret += m_vDP[0][i] + m_vDpUpper[0][i];
		}
		return ret;
	}
	ResultType Sum() {
		return Sum(0, m_iCustomStatusCount - 1);
	}
	vector<vector<ResultType>> m_vDP, m_vDpUpper;
	const ELE m_minEle, m_maxEle;
protected:
	const int m_iCustomStatusCount;
	IUpperDPCall<ELE, ResultType>& m_call;
};

template<class ELE, class ResultType>
class CUperrDP2
{
public:
	CUperrDP2(int iCustomStatusCount, IUpperDPCall<ELE, ResultType>& call, ELE minEle, ELE maxEle, ELE firstMinEle) 
		:m_iCustomStatusCount(iCustomStatusCount), m_call(call), m_minEle(minEle),m_maxEle(maxEle),m_firstMinEle(firstMinEle)
	{
	}
	void Init(const ELE* pHigh, int iEleCount)
	{
		m_vDP.assign(iEleCount + 1, vector<ResultType>(m_iCustomStatusCount));
		m_vDpUpper = m_vDP;
		m_vFirstDP = m_vDP;
		m_call.OnInitEnd(m_vDP.back(), m_vDpUpper.back());
		//预处理增加的一位
		for (int i = iEleCount - 1;i > 0;i--) {
			m_call.OnEnum(i,m_vDpUpper[i], m_vDpUpper[i + 1], pHigh[i], m_iCustomStatusCount);
			for (auto j = m_minEle; j < pHigh[i];j++) {
				m_call.OnEnum(i,m_vDpUpper[i], m_vDP[i + 1], j, m_iCustomStatusCount);
			}
			for (auto j = m_minEle; j <= m_maxEle;j++) {
				m_call.OnEnum(i,m_vDP[i], m_vDP[i + 1], j, m_iCustomStatusCount);
			}
			for (auto j = m_firstMinEle; j <= m_maxEle;j++) {
				m_call.OnEnum(i,m_vFirstDP[i], m_vDP[i + 1], j, m_iCustomStatusCount);
			}
		}
		m_call.OnEnum(0,m_vFirstDP[0], m_vDpUpper[1], pHigh[0], m_iCustomStatusCount);
		for (auto j = m_firstMinEle; j < pHigh[0];j++) {
			m_call.OnEnum(0,m_vFirstDP[0], m_vDP[1], j, m_iCustomStatusCount);
		}
	}
	ResultType Sum(int iMinCustomStatu, int iMaxCustomStatu) {
		ResultType ret = 0;
		for (int i = 0;i + 1 < m_vFirstDP.size();i++) {
			ret += accumulate(m_vFirstDP[i].begin() + iMinCustomStatu, m_vFirstDP[i].begin() + iMaxCustomStatu + 1, (ResultType)0);
		}
		return ret;
	}
	ResultType Sum() {
		return Sum(0, m_iCustomStatusCount - 1);
	}
	vector<vector<ResultType>> m_vDP, m_vDpUpper,m_vFirstDP;
	ELE m_minEle, m_maxEle, m_firstMinEle;
protected:
	const int m_iCustomStatusCount;
	IUpperDPCall<ELE, ResultType>& m_call;
};
        template<class ELE, class ResultType>
		class CCall :public IUpperDPCall<ELE, ResultType>
		{
		public:
			CCall(int k):m_iK(k) {}
			virtual void OnInitEnd(vector<ResultType>& dp, vector<ResultType>& upDp)
			{
				const int inx = m_iK * 10 + 0;
				dp[inx] = upDp[inx] = 1;
			}
			virtual void OnEnum(int n, vector<ResultType>& dp, const vector<ResultType>& vNext, ELE curValue, int iCustomStatusCount)
			{
				const int cur = curValue - '0';
				for (int pre = 0; pre < iCustomStatusCount;pre++) {
					int i1 = pre / m_iK, i2 = pre % m_iK;
					if (cur & 1) {
						i1++;
					}
					else {
						i1--;
					}
					if ((i1 < 0) || (i1 > 19)) { continue; }
					i2 = (10*i2+cur) % m_iK;
					dp[pre] += vNext[m_iK * i1 + i2];
				}
			}
			int m_iK;
		};
		class Solution {
		public:
			int numberOfBeautifulIntegers(int low, int high, int k) {
				CCall<char, int> call(k);
				CUperrDP2<char, int> dp1(20 * k, call, '0', '9', '1'), dp2(20 * k, call, '0', '9', '1');
				string str1 = to_string(low);
				string str2 = to_string(high);
				dp1.Init(str1.c_str(), str1.length());
				dp2.Init(str2.c_str(), str2.length());
				int cnt = 0;
				for (int tmp = low; tmp;tmp /= 10) {
					if ((tmp % 10) & 1) { cnt++; }
					else {
						cnt--;
					}
				}
				bool is = (0 == cnt) && (0 == low % k);
				const int inx = k * 10;
				const auto ans = dp2.Sum(inx, inx) - dp1.Sum(inx, inx)+ is;
				return ans;
			}
		};

数位dp

直接使用封装类，枚举类型char,最小值’0’,最大值’9’，结果类型：int。
状态数量：400。
i1 = 奇数数数量-偶数位数量+10，取值范围 $\in$ [1,19]
i2 = 当前数字%k
状态压缩：20*i1+i2

代码

核心代码


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 iNum)
	{
		m_vPre.assign(4, vector<ResultType>(m_iCustomStatusCount));
		if (iNum <= 0)
		{
			return;
		}
		InitPre(pLower, pHigh);
		iNum--;
		while (iNum--)
		{
			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);
		}
	}
protected:
	const int m_iCustomStatusCount;
	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 CMy : public CLowUperr<char, int, '0', '9'>
{
public:
	typedef  int ResultType;
	typedef  char ELE;
	CMy(int k) :CLowUperr<char, int, '0', '9'>(400), m_iK(k)
	{

	}
	virtual void OnEnumOtherBit(vector<ResultType>& dp, const vector<ResultType>& vPre, ELE curValue)
	{
		const int index = curValue - '0';
		for (int iPreMask = 0; iPreMask < m_iCustomStatusCount; iPreMask++)
		{
			const int preK = iPreMask % 20;
			const int pre01 = iPreMask / 20 ;
			const int k = (preK*10+index) % m_iK;
			int i01 = (index & 1) ? 1 : -1;
			if ((pre01 + i01 < 0) || (pre01 + i01 >= 20))
			{
				continue;
			}
			const int mask = Mask(pre01+i01-10, k);
			dp[mask] += vPre[iPreMask];
		}
	}

	virtual void OnEnumFirstBit(vector<ResultType>& vPre, const ELE curValue)
	{
		const int index = curValue - '0';
		const int k = index % m_iK;
		int i01 = (index & 1) ? 1 : -1;
		const int mask = Mask(i01,k);
		vPre[mask]++;
	}
	int Result()const
	{
		int iRet = 0;
		for (int status = 0; status < 4; status++)
		{
			iRet += m_vPre[status][200];
		}
		return iRet;
	}
protected:
	int Mask(int i01, int k) {	return (i01 + 10) * 20 + k;	}
	const int m_iK;
};
class Solution {
public:
	int numberOfBeautifulIntegers(int low, int high, int iK) {
		string strLow = std::to_string(low);
		string strHigh = std::to_string(high);
		int iRet = 0;
		const int len1 = strLow.length();
		const int len2 = strHigh.length();
		if (len1 == len2)
		{
			return Do(strLow, strHigh, iK);
		}
		iRet += Do(strLow, string(len1, '9'),iK);
		for (int i = len1 + 1; i < len2; i++)
		{
			iRet += Do("1" + string(i - 1, '0'), string(i, '9'), iK);
		}
		iRet += Do("1" + string(len2 - 1, '0'), strHigh, iK);
		return iRet;
	}
	int Do(const string strLow,const string& strHigh,int k)
	{
		CMy my(k);
		my.Init(strLow.data(), strHigh.data(), strLow.length());
		return my.Result();
	}
};

测试用例


template<class T, class T2>
void Assert(const T& t1, const T2& 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 low = 1, high = 10, k = 1;
	{
		low = 1, high = 10, k = 1;
		auto res = Solution().numberOfBeautifulIntegers(low, high, k);
		Assert(1, res);
	}
	{
		low = 5, high = 5, k = 2;
		auto res = Solution().numberOfBeautifulIntegers(low, high, k);
		Assert(0, res);
	}
	{
		low = 10, high = 20, k = 3;
		auto res = Solution().numberOfBeautifulIntegers(low, high, k);
		Assert(2, res);
	}
	
}

扩展阅读

视频课程

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

如何你想快

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

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