233. Number of Digit One
Đề Bài
Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.
Example 1:
Input: n = 13 Output: 6
Example 2:
Input: n = 0 Output: 0
Constraints:
0 <= n <= 109
Thuật Toán & Kỹ Thuật
⏱️ Thời gian
O(n²)
💾 Không gian
O(n)
Lời Giải
C++
0233-number-of-digit-one.cpp
class Solution {
private:
string num;
int m;
public:
int memo[12][2][12];
int dp(int i, bool tight, int cnt) {
if (i == m) {
return cnt;
}
if (memo[i][tight][cnt] != -1) {
return memo[i][tight][cnt];
}
int limit = tight ? (num[i] - '0') : 9;
int ans = 0;
for (int d = 0; d <= limit; ++d) {
bool newTight = tight and d == limit;
int newCnt = cnt + (d == 1);
ans += dp(i + 1, newTight, newCnt);
}
return memo[i][tight][cnt] = ans;
}
int countDigitOne(int n) {
num = to_string(n);
m = num.size();
memset(memo, -1, sizeof(memo));
return dp(0, true, 0);
}
};
Python
0233-number-of-digit-one.py
class Solution:
def countDigitOne(self, n: int) -> int:
nums = list(map(int, str(n)))
sz = len(nums)
@cache
def dp(i, cnt, tight):
if i == sz:
return cnt
limit = nums[i] if tight else 9
ans = 0
for d in range(limit + 1):
newCnt = cnt + (d == 1)
newTight = tight and d == nums[i]
ans += dp(i + 1, newCnt, newTight)
return ans
return dp(0, 0, True)