题目
给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。
示例 1：
输入：n = 13
输出：6
示例 2：
输入：n = 0
输出：0
提示：
0 <= n <= 109
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; };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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
