算法：1～n 整數(shù)中 1 出現(xiàn)的次數(shù)
2022-11-08 17:51 作者:做架構(gòu)師不做框架師 | 我要投稿
輸入一個(gè)整數(shù) n ，求1～n這n個(gè)整數(shù)的十進(jìn)制表示中1出現(xiàn)的次數(shù)。
例如，輸入12，1～12這些整數(shù)中包含1 的數(shù)字有1、10、11和12，1一共出現(xiàn)了5次。
示例
輸入：n = 12
輸出：5
限制
1 <= n < 2^31
方法：枚舉
當(dāng) cur = 0 時(shí)，此位 1 的個(gè)數(shù)的計(jì)算公式為：high * digit；
當(dāng) cur = 1 時(shí)，此位 1 的個(gè)數(shù)的計(jì)算公式為：high * digit + low + 1；
當(dāng) cur > 1 時(shí)，此位 1 的個(gè)數(shù)的計(jì)算公式為：(high +1) * digit。
代碼如下：
復(fù)雜度分析
時(shí)間復(fù)雜度 ： O(logn) 。
空間復(fù)雜度 ： O(1) ，幾個(gè)變量使用常數(shù)大小的額外空間。
END
聰明出于勤奮，天才在于積累，贈(zèng)友人。
好兄弟可以點(diǎn)贊并關(guān)注我的公眾號(hào)“javaAnswer”，全部都是干貨。
標(biāo)簽：
