当前位置：网站首页>剑指 Offer 43. 1～n 整数中 1 出现的次数（递归、数学）

剑指 Offer 43. 1～n 整数中 1 出现的次数（递归、数学）

2022-08-09 12:45:00 【养猪去】

举个例子： n = 2304 。答案为四个部分之和：

  1. 所有小于等于2304的正整数中，个位出现1的次数.
  2. 所有小于等于2304的正整数中，十位出现1的次数.
  3. 所有小于等于2304的正整数中，百位出现1的次数.
  4. 所有小于等于2304的正整数中，千位出现1的次数.

循环地计算每个位上出现的1的次数。（个位、十位、百位、…）

class Solution {
    
    public int countDigitOne(int n) {
    
        // mulk 表示 10^k
        // 在下面的代码中，可以发现 k 并没有被直接使用到（都是使用 10^k）
        // 但为了让代码看起来更加直观，这里保留了 k
        long mulk = 1;
        int ans = 0;
        // 1234 567
        for (int k = 0; n >= mulk; ++k) {
    
            ans += (n / (mulk * 10)) * mulk + Math.min(Math.max(n % (mulk * 10) - mulk + 1, 0), mulk);
            mulk *= 10;
        }
        return ans;
    }
}
原网站

版权声明
本文为[养猪去]所创，转载请带上原文链接，感谢
https://song-yang-ji.blog.csdn.net/article/details/121528130

边栏推荐

猜你喜欢

随机推荐