📘 題目敘述
給你一個整數 n，請計算從 0 到 n（包含 n）之間，所有數字的十進位表示中，數字 1 出現的總次數。
條件限制
0 <= n <= 10^9
🧠 解題思路
這題如果真的一個一個數去數 1 會太慢，所以要用「按位數統計」的方式。
我的做法是固定看某一個位數 k（1、10、100...），問：
從 0 到 n，這個位數上出現
1的次數有多少？
只要把每一個位數的貢獻加起來，就是總答案。
對於某個位數 k（代表目前在看的是個位/十位/百位...）
我把 n 拆成三段：
high：更高位（n / (k*10)）now：目前這一位（(n / k) % 10）low：更低位（n % k）
然後用固定公式算這一位的貢獻：
-
先加上
high * k代表「完整跑完 high 個循環」時，這一位固定會有k次是 1 -
再看
now是什麼：- 如果
now == 1代表這一輪還會多出low + 1次（從 0 到 low） - 如果
now > 1代表這一輪已經超過 1 的區間，所以會再多k次 - 如果
now == 0不額外增加
- 如果
我用 k *= 10 逐位往上算，直到超過 n。
所有變數
count：累積答案，表示 0 到 n 之間數字 1 出現的總次數k：目前正在統計的位數（1、10、100...）high：n在目前位數左邊的高位部分now：n在目前位數的數字low：n在目前位數右邊的低位部分
🪜 主要流程步驟
1. 用 k 表示目前統計的位數，從個位開始一路往上
我用 k = 1 開始，代表先統計個位。
每次結束後做 k *= 10，依序處理十位、百位、千位……
2. 對每個位數，把 n 拆成 high / now / low
對固定的 k：
high = n / (k * 10)now = (n / k) % 10low = n % k
這三個值就完整描述了 n 在這個位數附近的結構。
3. 先加上 high * k，代表完整循環帶來的 1 次數
不管 now 是多少，這一位的 1 會先有：
high * k
這是因為每 0~(k*10-1) 的循環裡，該位數會有連續 k 個數是 1。
4. 再根據 now 的值處理「最後不完整那段」
- 若
now == 1：加low + 1 - 若
now > 1：加k - 若
now == 0：不加
5. 累加完所有位數後回傳 count
當 k > n 時代表所有位數都處理完了，回傳 count。
⏱️ 複雜度
-
時間複雜度：
O(log10 n)只跑 n 的位數次（最多 10 次） -
空間複雜度：
O(1)
💻 程式碼實作
class Solution {
public:
int countDigitOne(int n) {
int count = 0;
for (long long k = 1; k <= n; k *= 10) {
long long high = n / (k * 10); // 高位數
long long now = (n / k) % 10; // 現在
long long low = n % k; // 低位數
count += high * k;
if (now == 1) {
count += (low + 1); // 0~low這些
} else if (now > 1) {
count += k;
}
}
return count;
}
};
🔗 題目連結
https://leetcode.com/problems/number-of-digit-one/