PROBLEM

剑指 Offer 43. 1～n 整数中 1 出现的次数

难度 困难

MY ANSWER

无。

BETTER SOLUTION

逐位计算1出现的次数，类似滚动密码锁，固定住一位1，计算有多少个数与这个1组合。时间复杂度O(logn)，空间复杂度O(1)。每位分3种情况：

  • cur = 0

    Picture1.png

  • cur = 1

    Picture2.png

  • cur > 1

    Picture3.png

class Solution {
public:
    int countDigitOne(int n) {
       int cur = n % 10;
       int low = 0;
       int high = n / 10;
       long long digit = 1;
       int res = 0;
       while(cur != 0 || high != 0) {
           if(cur == 0) {
               res += high * digit;
           }
           else if(cur == 1) {
               res += high * digit + low + 1;
           }
           else {
               res += (high + 1) * digit;
           }
           low += cur * digit;
           cur = high % 10;
           high /= 10;
           digit *= 10;
       }
       return res;
    }
};

SUMMARY

理解滚动密码锁的思想。