作者推荐
本文涉及知识点
LeetCode:233数字 1 的个数
给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。
示例 1：
输入：n = 13
输出：6
示例 2：
输入：n = 0
输出：0
提示：
0 <= n <= 109
数位dp的封装类
本题比较简单，主要讲封装类。m_vPre记录上一位所有状态，程序结束时，记录的是最后一位的所有状态。
m_vPre是二维向量，一维长度4，分别表示4种边界状态，下标0记录 非上下界，下标1记录下界，下标2记录上界，3记录同时上下界。二维长度由构造函数的参数iResutlCount决定。ResultType类记录状态。
| ELE | 枚举的元素类型 |
| minEle | 元素最小值 |
| maxEle | 元素最大值 |
| pLower | 下界 |
| pHigh | 上界 |
| iNum | 上下界的长度 |
使用的时完成OnEnumFirstBit和OnEnumOtherBit，OnEnumFirstBit会不重复不遗漏的枚举第一位的 元素和边界状态。
OnEnumOtherBit，此函数会不重复不遗漏的依次枚举其它位的元素和边界状态。
只会枚举在范围内的状态，不会枚举非法状态。
pre和dp 是对应边界状态的状态，所以是一维向量。
注意 : 同一位 同一元素 同一状态 可能枚举两次，这不会造成重复计算。因为是两层枚举，第一层枚举：前一元素的边界状态；第二层枚举：当前元素。
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; };
本题代码
核心代码
//pair<int, int> first记录在范围内符合要求的子串数量 second 记录1的数量 class CCharLowerUper : public CLowUperr<char, pair<int, int>, '0', '9'> { public: using CLowUperr<char, pair<int, int>, '0', '9'>::CLowUperr; 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; std::cout << " index:" << index << " " << cur << std::endl; } return ret; } protected: virtual void OnEnumFirstBit(vector<pair<int, int>>& vPre, const char curValue) { const int index = curValue - '0'; vPre[index].first =1 ; vPre[index].second = 1 == index; } 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 < 10; i++) { dp[index].first += vPre[i].first; dp[index].second += vPre[i].second; if (1 == index) { dp[index].second += vPre[i].first; } } } }; class Solution { public: int countDigitOne(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(10); lu.Init(("1" + string(i - 1, '0')).c_str(),string(i,'9').c_str(),i); iRet += lu.Total(0, 9); } CCharLowerUper lu(10); lu.Init(("1" + string(len - 1, '0')).c_str(), strN.c_str(), len); iRet += lu.Total(0, 9); 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() { vector<int> nums; { Solution sln; int n = 30; auto res = sln.countDigitOne(n); Assert(13, res); } { Solution sln; int n=13; auto res = sln.countDigitOne(n); Assert(6, res); } { Solution sln; int n = 0; auto res = sln.countDigitOne(n); Assert(0, res); } }
2023年1月版
class Solution { public: int countDigitOne(int n) { int iNum = 0; int iMul = 1; for (int i = 0; i < 9; i++) { iNum += n / (iMul * 10) *iMul; int tmp = n % (iMul * 10); if (tmp >= iMul) { if (tmp >= iMul * 2) { tmp = iMul * 2 - 1; } iNum += tmp - (iMul - 1); } iMul *= 10; } if (1000 * 1000 * 1000 == n) { iNum++; } return iNum; } };
2023年8月
class CTest : public CLowUperr<char,int,‘0’,‘9’> { public: CTest():CLowUperr(10) { } // 通过 CLowUperr 继承 virtual void OnDo(vector<vector>& dp, int preStatus, int curStatus, int cur) override { dp[curStatus][cur] += m_vPreCan[preStatus]; m_vCurOneNum[curStatus] += m_vPreOneNum[preStatus]; } virtual void OnInitDP(vector<vector>& dp) { for (int i = 0; i < 4; i++) { m_vPreCan[i] = std::accumulate(MACRO_BEGIN_END(m_vPre[i]), 0); m_vPreOneNum[i] = m_vCurOneNum[i] + m_vPre[i][1]; } memset(m_vCurOneNum, 0, sizeof(m_vCurOneNum)); } int Total() { int iRet = 0; for (int i = 0; i < 4; i++) { iRet += m_vCurOneNum[i] + m_vPre[i][1]; } return iRet; } int m_vPreCan[4] = { 0 };//前四中状态的可能 int m_vPreOneNum[4] = { 0 };//前面4种状态1的数量 int m_vCurOneNum[4] = { 0 };//前面4种状态1的数量 }; class Solution { public: int countDigitOne(int n) { string str = std::to_string(n); int len = 1; for (; len < str.length(); len++) { Do(“1” + string(len - 1, ‘0’), string(len, ‘9’)); } Do(“1” + string(len - 1, ‘0’), str); return m_iRet; } void Do(string s1, string s2) { CTest test; test.Init(s1.data(), s2.data(), s1.length()); m_iRet += test.Total(); } int m_iRet; };
