C++数位算法：数字1的个数

题目

给定一个整数 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;
 };

扩展阅读

相关下载

想高屋建瓴的学习算法，请下载《闻缺陷则喜算法册》doc版

之。 |
|如果程序是一条龙，那算法就是他的是睛|

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17