<linkrel="dns-prefetch"href="http://yoursite.com">

<title>1049 Counting Ones (30分) | 鲍锋雄的博客</title>

<metaname="viewport"content="width=device-width, initial-scale=1, maximum-scale=1">

<metaname="description"content="题目大意： 给一个数N，统计从1到N的所有数字中1出现的次数。 解题思路： 这道题是《编程之美》上面的一道题（第2.4节），需要通过分析来总结规律，然后总结出公式，如果暴力去“数”1的个数，显然会超时。但如果通过公式来算的话，时间复杂度就直接降到O(1)O(1)O(1)。具体分析过程比较复杂，详情参见《编程之美》2.4节“1的数目”，这里只给出结论——从右往左拆解数，逐位分析每个位出现1的数目，然">

<metaname="description"content="题目大意： 给一个数N，统计从1到N的所有数字中1出现的次数。 解题思路： 这道题是《编程之美》上面的一道题（第2.4节），需要通过分析来总结规律，然后总结出公式，如果暴力去“数”1的个数，显然会超时。但如果通过公式来算的话，时间复杂度就直接降到O(1)。具体分析过程比较复杂，详情参见《编程之美》2.4节“1的数目”，这里只给出结论——从右往左拆解数，逐位分析每个位出现1的数目，然后统计其规律与左">

<metaproperty="og:type"content="article">

<metaproperty="og:title"content="1049 Counting Ones (30分)">

<metaproperty="og:url"content="http://yoursite.com/2020/04/06/1049%20Counting%20Ones%20(30%E5%88%86)/index.html">

<metaproperty="og:site_name"content="鲍锋雄的博客">

<metaproperty="og:description"content="题目大意： 给一个数N，统计从1到N的所有数字中1出现的次数。 解题思路： 这道题是《编程之美》上面的一道题（第2.4节），需要通过分析来总结规律，然后总结出公式，如果暴力去“数”1的个数，显然会超时。但如果通过公式来算的话，时间复杂度就直接降到O(1)O(1)O(1)。具体分析过程比较复杂，详情参见《编程之美》2.4节“1的数目”，这里只给出结论——从右往左拆解数，逐位分析每个位出现1的数目，然">

<metaproperty="og:description"content="题目大意： 给一个数N，统计从1到N的所有数字中1出现的次数。 解题思路： 这道题是《编程之美》上面的一道题（第2.4节），需要通过分析来总结规律，然后总结出公式，如果暴力去“数”1的个数，显然会超时。但如果通过公式来算的话，时间复杂度就直接降到O(1)。具体分析过程比较复杂，详情参见《编程之美》2.4节“1的数目”，这里只给出结论——从右往左拆解数，逐位分析每个位出现1的数目，然后统计其规律与左">

<metaproperty="og:locale"content="en_US">

<metaproperty="og:image"content="https://i.loli.net/2020/04/05/HVrRT4YhQvzeIkx.png">

<metaproperty="article:published_time"content="2020-04-06T06:04:51.977Z">

<metaproperty="article:modified_time"content="2020-04-06T06:05:41.490Z">

<metaproperty="article:modified_time"content="2020-06-16T07:18:40.772Z">

<metaproperty="article:author"content="bfx">

<metaproperty="article:tag"content="PAT刷题记录">

<metaname="twitter:card"content="summary">

<divclass="article-entry"itemprop="articleBody">

<p><strong>题目大意</strong>： 给一个数N，统计从1到N的所有数字中1出现的次数。</p>

<p><strong>解题思路</strong>： 这道题是《编程之美》上面的一道题（第2.4节），需要通过分析来总结规律，然后总结出公式，如果暴力去“数”1的个数，显然会超时。但如果通过公式来算的话，时间复杂度就直接降到O(1)O(1)O(1)。具体分析过程比较复杂，详情参见《编程之美》2.4节“1的数目”，这里只给出结论——从右往左拆解数，逐位分析每个位出现1的数目，然后统计其规律与左右数存在的关系，最后累加，即为结果。</p>

<p><strong>解题思路</strong>： 这道题是《编程之美》上面的一道题（第2.4节），需要通过分析来总结规律，然后总结出公式，如果暴力去“数”1的个数，显然会超时。但如果通过公式来算的话，时间复杂度就直接降到O(1)。具体分析过程比较复杂，详情参见《编程之美》2.4节“1的数目”，这里只给出结论——从右往左拆解数，逐位分析每个位出现1的数目，然后统计其规律与左右数存在的关系，最后累加，即为结果。</p>

<p><imgsrc="https://i.loli.net/2020/04/05/HVrRT4YhQvzeIkx.png"alt="20181220100453559.png"></p>

<figureclass="highlight c++"><table><tr><tdclass="gutter"><pre><spanclass="line">1</span><br><spanclass="line">2</span><br><spanclass="line">3</span><br><spanclass="line">4</span><br><spanclass="line">5</span><br><spanclass="line">6</span><br><spanclass="line">7</span><br><spanclass="line">8</span><br><spanclass="line">9</span><br><spanclass="line">10</span><br><spanclass="line">11</span><br><spanclass="line">12</span><br><spanclass="line">13</span><br><spanclass="line">14</span><br><spanclass="line">15</span><br><spanclass="line">16</span><br><spanclass="line">17</span><br><spanclass="line">18</span><br><spanclass="line">19</span><br><spanclass="line">20</span><br><spanclass="line">21</span><br><spanclass="line">22</span><br><spanclass="line">23</span><br><spanclass="line">24</span><br><spanclass="line">25</span><br><spanclass="line">26</span><br><spanclass="line">27</span><br><spanclass="line">28</span><br><spanclass="line">29</span><br><spanclass="line">30</span><br><spanclass="line">31</span><br></pre></td><tdclass="code"><pre><spanclass="line"><spanclass="meta">#<spanclass="meta-keyword">include</span><spanclass="meta-string">&lt;bits/stdc++.h&gt;</span></span></span><br><spanclass="line"><spanclass="keyword">using</span><spanclass="keyword">namespace</span><spanclass="built_in">std</span>;</span><br><spanclass="line"></span><br><spanclass="line"><spanclass="comment">/*</span></span><br><spanclass="line"><spanclass="comment">找规律题，计算每一位对应的1的个数，然后相加，每一位的1的计算情况分三种情况：</span></span><br><spanclass="line"><spanclass="comment">1.如果当前位数字为0，那么该位的1的个数由更高位的数字确定。比如2120，个位为1的个数为212 * 1 = 212（个位的单位为1）。</span></span><br><spanclass="line"><spanclass="comment">2.如果当前位数字为1，那么该位的1的个数不但由高位决定，还由低位数字决定。比如2120百位为1，那么百位数字1的个数为2 * 100 + 20 + 1 = 221个（百位的单位为100）。</span></span><br><spanclass="line"><spanclass="comment">3.如果当前位数字大于1，那么该位数字1的个数为（高位数+ 1） * 位数单位。比如2120十位为2，那么十位数字1的个数为（21 + 1） * 10 = 220个（十位的单位为10）</span></span><br><spanclass="line"><spanclass="comment">*/</span></span><br><spanclass="line"></span><br><spanclass="line"><spanclass="function"><spanclass="keyword">int</span><spanclass="title">main</span><spanclass="params">(<spanclass="keyword">int</span> argc,<spanclass="keyword">char</span><spanclass="keyword">const</span> *argv[])</span></span></span><br><spanclass="line"><spanclass="function"></span>&#123;</span><br><spanclass="line"><spanclass="keyword">int</span> N;</span><br><spanclass="line"><spanclass="built_in">cin</span> &gt;&gt; N;</span><br><spanclass="line"><spanclass="keyword">int</span> digit =<spanclass="number">1</span>, left, right, ans =<spanclass="number">0</span>;</span><br><spanclass="line"><spanclass="keyword">while</span> (N / digit) &#123;</span><br><spanclass="line"><spanclass="keyword">int</span> now = N / digit %<spanclass="number">10</span>;</span><br><spanclass="line">left = N / (digit *<spanclass="number">10</span>);</span><br><spanclass="line">right = N % digit;</span><br><spanclass="line"><spanclass="keyword">if</span> (now ==<spanclass="number">0</span>)</span><br><spanclass="line">ans += left * digit;</span><br><spanclass="line"><spanclass="keyword">else</span><spanclass="keyword">if</span> (now ==<spanclass="number">1</span>)</span><br><spanclass="line">ans += left * digit + right +<spanclass="number">1</span>;</span><br><spanclass="line"><spanclass="keyword">else</span></span><br><spanclass="line">ans += (left +<spanclass="number">1</span>) * digit;</span><br><spanclass="line">digit *=<spanclass="number">10</span>;</span><br><spanclass="line">&#125;</span><br><spanclass="line"><spanclass="built_in">cout</span> &lt;&lt; ans &lt;&lt;<spanclass="built_in">endl</span>;</span><br><spanclass="line"></span><br><spanclass="line"><spanclass="keyword">return</span><spanclass="number">0</span>;</span><br><spanclass="line">&#125;</span><br></pre></td></tr></table></figure>

<divclass="article-entry"itemprop="articleBody">

<p><strong>题目大意</strong>： 给一个数N，统计从1到N的所有数字中1出现的次数。</p>

<p><strong>解题思路</strong>： 这道题是《编程之美》上面的一道题（第2.4节），需要通过分析来总结规律，然后总结出公式，如果暴力去“数”1的个数，显然会超时。但如果通过公式来算的话，时间复杂度就直接降到O(1)O(1)O(1)。具体分析过程比较复杂，详情参见《编程之美》2.4节“1的数目”，这里只给出结论——从右往左拆解数，逐位分析每个位出现1的数目，然后统计其规律与左右数存在的关系，最后累加，即为结果。</p>

<p><strong>解题思路</strong>： 这道题是《编程之美》上面的一道题（第2.4节），需要通过分析来总结规律，然后总结出公式，如果暴力去“数”1的个数，显然会超时。但如果通过公式来算的话，时间复杂度就直接降到O(1)。具体分析过程比较复杂，详情参见《编程之美》2.4节“1的数目”，这里只给出结论——从右往左拆解数，逐位分析每个位出现1的数目，然后统计其规律与左右数存在的关系，最后累加，即为结果。</p>

<p><imgsrc="https://i.loli.net/2020/04/05/HVrRT4YhQvzeIkx.png"alt="20181220100453559.png"></p>

<figureclass="highlight c++"><table><tr><tdclass="gutter"><pre><spanclass="line">1</span><br><spanclass="line">2</span><br><spanclass="line">3</span><br><spanclass="line">4</span><br><spanclass="line">5</span><br><spanclass="line">6</span><br><spanclass="line">7</span><br><spanclass="line">8</span><br><spanclass="line">9</span><br><spanclass="line">10</span><br><spanclass="line">11</span><br><spanclass="line">12</span><br><spanclass="line">13</span><br><spanclass="line">14</span><br><spanclass="line">15</span><br><spanclass="line">16</span><br><spanclass="line">17</span><br><spanclass="line">18</span><br><spanclass="line">19</span><br><spanclass="line">20</span><br><spanclass="line">21</span><br><spanclass="line">22</span><br><spanclass="line">23</span><br><spanclass="line">24</span><br><spanclass="line">25</span><br><spanclass="line">26</span><br><spanclass="line">27</span><br><spanclass="line">28</span><br><spanclass="line">29</span><br><spanclass="line">30</span><br><spanclass="line">31</span><br></pre></td><tdclass="code"><pre><spanclass="line"><spanclass="meta">#<spanclass="meta-keyword">include</span><spanclass="meta-string">&lt;bits/stdc++.h&gt;</span></span></span><br><spanclass="line"><spanclass="keyword">using</span><spanclass="keyword">namespace</span><spanclass="built_in">std</span>;</span><br><spanclass="line"></span><br><spanclass="line"><spanclass="comment">/*</span></span><br><spanclass="line"><spanclass="comment">找规律题，计算每一位对应的1的个数，然后相加，每一位的1的计算情况分三种情况：</span></span><br><spanclass="line"><spanclass="comment">1.如果当前位数字为0，那么该位的1的个数由更高位的数字确定。比如2120，个位为1的个数为212 * 1 = 212（个位的单位为1）。</span></span><br><spanclass="line"><spanclass="comment">2.如果当前位数字为1，那么该位的1的个数不但由高位决定，还由低位数字决定。比如2120百位为1，那么百位数字1的个数为2 * 100 + 20 + 1 = 221个（百位的单位为100）。</span></span><br><spanclass="line"><spanclass="comment">3.如果当前位数字大于1，那么该位数字1的个数为（高位数+ 1） * 位数单位。比如2120十位为2，那么十位数字1的个数为（21 + 1） * 10 = 220个（十位的单位为10）</span></span><br><spanclass="line"><spanclass="comment">*/</span></span><br><spanclass="line"></span><br><spanclass="line"><spanclass="function"><spanclass="keyword">int</span><spanclass="title">main</span><spanclass="params">(<spanclass="keyword">int</span> argc,<spanclass="keyword">char</span><spanclass="keyword">const</span> *argv[])</span></span></span><br><spanclass="line"><spanclass="function"></span>&#123;</span><br><spanclass="line"><spanclass="keyword">int</span> N;</span><br><spanclass="line"><spanclass="built_in">cin</span> &gt;&gt; N;</span><br><spanclass="line"><spanclass="keyword">int</span> digit =<spanclass="number">1</span>, left, right, ans =<spanclass="number">0</span>;</span><br><spanclass="line"><spanclass="keyword">while</span> (N / digit) &#123;</span><br><spanclass="line"><spanclass="keyword">int</span> now = N / digit %<spanclass="number">10</span>;</span><br><spanclass="line">left = N / (digit *<spanclass="number">10</span>);</span><br><spanclass="line">right = N % digit;</span><br><spanclass="line"><spanclass="keyword">if</span> (now ==<spanclass="number">0</span>)</span><br><spanclass="line">ans += left * digit;</span><br><spanclass="line"><spanclass="keyword">else</span><spanclass="keyword">if</span> (now ==<spanclass="number">1</span>)</span><br><spanclass="line">ans += left * digit + right +<spanclass="number">1</span>;</span><br><spanclass="line"><spanclass="keyword">else</span></span><br><spanclass="line">ans += (left +<spanclass="number">1</span>) * digit;</span><br><spanclass="line">digit *=<spanclass="number">10</span>;</span><br><spanclass="line">&#125;</span><br><spanclass="line"><spanclass="built_in">cout</span> &lt;&lt; ans &lt;&lt;<spanclass="built_in">endl</span>;</span><br><spanclass="line"></span><br><spanclass="line"><spanclass="keyword">return</span><spanclass="number">0</span>;</span><br><spanclass="line">&#125;</span><br></pre></td></tr></table></figure>