1.题目基本信息

1.1.题目描述

给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。

1.2.题目地址

https://leetcode.cn/problems/number-of-digit-one/description/

2.解题方法

2.1.解题思路

数位dp

2.2.解题步骤

第一步，构建深搜函数。递归任务：i为当前需要填的位置，cnt1为当前前缀数中1的个数，isLimit为i位能填的数字是否受s[i]值的限制；返回在当前前缀数状态下，能找到的数中1的个数

• 1.1.递归出口

• 1.2.确定当前位的上限

• 1.3.枚举当前位的数字

3.解题代码

python代码

class Solution:
    def countDigitOne(self, n: int) -> int:
        # 思路：数位dp
        s = str(n)
        # 第一步，构建深搜函数。递归任务：i为当前需要填的位置，cnt1为当前前缀数中1的个数，isLimit为i位能填的数字是否受s[i]值的限制；返回在当前前缀数状态下，能找到的数中1的个数
        @cache
        def dfs(i:int, cnt1:int, isLimit:bool) -> int:
            # 1.1.递归出口
            if i == len(s):
                return cnt1
            # 1.2.确定当前位的上限
            ans = 0
            up = int(s[i]) if isLimit else 9
            # 1.3.枚举当前位的数字
            for d in range(up + 1):
                ans += dfs(i + 1, cnt1 + int(d == 1), isLimit and d == int(s[i]))
            return ans
        return dfs(0, 0, True)

c++代码

#include <string>

class Solution {
public:
    int length = 0;
    string s = "";
    unordered_map<string, int> cache;

    int dfs(int i, int cnt1, bool isLimit) {
        string key = to_string(i) + "-" + to_string(cnt1) + "-" + to_string(isLimit);
        if (cache.find(key) != cache.end()) {
            return cache[key];
        }
        // cout << key << endl;
        if (i == length) {
            return cnt1;
        }
        int ans = 0;
        int up = isLimit ? s[i] - '0' : 9;
        for (int d = 0; d < up + 1; d++) {
            ans += dfs(i + 1, cnt1 + bool(d == 1), isLimit && (d == up));
        }
        cache[key] = ans;
        return ans;
    }

    int countDigitOne(int n) {
        s = to_string(n);
        length = s.size();
        cout << length;
        return dfs(0, 0, true);
    }
};

4.执行结果