C++数位算法：数字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;
}
};

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;
};