劍指Offer——1~n整數中1出現的次數（JS實作）

題目描述

解題思路

• 本題如果采用暴力的方法一定會逾時
• 本題關鍵在于找規律
• 規律如下圖所示（cur>1,cur=1.cur<1三種情況）

解題代碼（模拟隊列）

var countDigitOne = function(n) {
    let flag = 0;

    const TotalBase = Math.pow(10,(String(n).split('').length) - 1);
    for (let i = 0; Math.pow(10,i) <= TotalBase; i++) {
        let base = Math.pow(10,i);
        let cur = Math.floor(n/base) % 10;
        let a = Math.floor(Math.floor(n/base) / 10);
        let b = n % base;
        if (cur < 1) {
            flag = flag + a * base;
        } else if (cur > 1) {
            flag = flag + (a + 1) * base;
        } else {
            flag = flag + a * base + b + 1;
        }
    }
    return flag;

};
      

精講UP主

www.bilibili.com/video/av458…

總結（本題給我們的啟示思路）

• 啟示一：學會通過數學規律的思想來解決本題