本文涉及知識(shí)點(diǎn)
數(shù)位dp
動(dòng)態(tài)規(guī)劃匯總
LeetCode2827. 范圍中美麗整數(shù)的數(shù)目
給你正整數(shù) low ，high 和 k 。
如果一個(gè)數(shù)滿足以下兩個(gè)條件，那么它是 美麗的 ：
偶數(shù)數(shù)位的數(shù)目與奇數(shù)數(shù)位的數(shù)目相同。
這個(gè)整數(shù)可以被 k 整除。
請你返回范圍 [low, high] 中美麗整數(shù)的數(shù)目。
示例 1：
輸入：low = 10, high = 20, k = 3
輸出：2
解釋：給定范圍中有 2 個(gè)美麗數(shù)字：[12,18]
- 12 是美麗整數(shù)，因?yàn)樗?1 個(gè)奇數(shù)數(shù)位和 1 個(gè)偶數(shù)數(shù)位，而且可以被 k = 3 整除。
- 18 是美麗整數(shù)，因?yàn)樗?1 個(gè)奇數(shù)數(shù)位和 1 個(gè)偶數(shù)數(shù)位，而且可以被 k = 3 整除。
以下是一些不是美麗整數(shù)的例子： - 16 不是美麗整數(shù)，因?yàn)樗荒鼙?k = 3 整除。
- 15 不是美麗整數(shù)，因?yàn)樗钠鏀?shù)數(shù)位和偶數(shù)數(shù)位的數(shù)目不相等。
給定范圍內(nèi)總共有 2 個(gè)美麗整數(shù)。
示例 2：
輸入：low = 1, high = 10, k = 1
輸出：1
解釋：給定范圍中有 1 個(gè)美麗數(shù)字：[10] - 10 是美麗整數(shù)，因?yàn)樗?1 個(gè)奇數(shù)數(shù)位和 1 個(gè)偶數(shù)數(shù)位，而且可以被 k = 1 整除。
給定范圍內(nèi)總共有 1 個(gè)美麗整數(shù)。
示例 3：
輸入：low = 5, high = 5, k = 2
輸出：0
解釋：給定范圍中有 0 個(gè)美麗數(shù)字。 - 5 不是美麗整數(shù)，因?yàn)樗钠鏀?shù)數(shù)位和偶數(shù)數(shù)位的數(shù)目不相等。
提示：
0 < low <= high <= 109
0 < k <= 20
數(shù)位dp
直接使用封裝類，枚舉類型char,最小值’0’,最大值’9’，結(jié)果類型：int。
狀態(tài)數(shù)量：400。
i1 = 奇數(shù)數(shù)數(shù)量-偶數(shù)位數(shù)量+10，取值范圍
∈
\in
∈[1,19]
i2 = 當(dāng)前數(shù)字%k
狀態(tài)壓縮：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);
}
}
擴(kuò)展閱讀
視頻課程
有效學(xué)習(xí)：明確的目標(biāo) 及時(shí)的反饋 拉伸區(qū)（難度合適），可以先學(xué)簡單的課程，請移步CSDN學(xué)院，聽白銀講師（也就是鄙人）的講解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成戰(zhàn)斗了，為老板分憂，請學(xué)習(xí)C#入職培訓(xùn)、C++入職培訓(xùn)等課程
https://edu.csdn.net/lecturer/6176
相關(guān)
下載
想高屋建瓴的學(xué)習(xí)算法，請下載《喜缺全書算法冊》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想對大家說的話 |
|---|
| 聞缺陷則喜是一個(gè)美好的愿望，早發(fā)現(xiàn)問題，早修改問題，給老板節(jié)約錢。 |
| 子墨子言之：事無終始，無務(wù)多業(yè)。也就是我們常說的專業(yè)的人做專業(yè)的事。 |
| 如果程序是一條龍，那算法就是他的是睛 |
測試環(huán)境
操作系統(tǒng)：win7 開發(fā)環(huán)境： VS2019 C++17
或者 操作系統(tǒng)：win10 開發(fā)環(huán)境： VS2022 C++17
如無特殊說明，本算法用**C++**實(shí)現(xiàn)。文章來源：http://www.zghlxwxcb.cn/news/detail-848273.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-848273.html
到了這里，關(guān)于【動(dòng)態(tài)規(guī)劃】【 數(shù)位dp】2827. 范圍中美麗整數(shù)的數(shù)目的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
