golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-04-22 11:42:42

func numberOf2sInRange(n int) int {
    s := strconv.Itoa(n)
    m := len(s)
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, m)
        for j := range dp[i] {
            dp[i][j] = -1
        }
    }
    var f func(int, int, bool) int
    f = func(i, cnt2 int, isLimit bool) (res int) {
        if i == m {
            return cnt2
        }
        if !isLimit {
            dv := &dp[i][cnt2]
            if *dv >= 0 {
                return *dv
            }
            defer func() { *dv = res }()
        }
        up := 9
        if isLimit {
            up = int(s[i] - '0')
        }
        for d := 0; d <= up; d++ { // 枚举要填入的数字 d
            c := cnt2
            if d == 2 {
                c++
            }
            res += f(i+1, c, isLimit && d == up)
        }
        return
    }
    return f(0, 0, true)
}

java 解法, 执行用时: 0 ms, 内存消耗: 38.3 MB, 提交时间: 2023-04-22 11:42:28

class Solution {
    char s[];
    int dp[][];

    public int numberOf2sInRange(int n) {
        s = Integer.toString(n).toCharArray();
        var m = s.length;
        dp = new int[m][m];
        for (var i = 0; i < m; i++) Arrays.fill(dp[i], -1);
        return f(0, 0, true);
    }

    int f(int i, int cnt2, boolean isLimit) {
        if (i == s.length) return cnt2;
        if (!isLimit && dp[i][cnt2] >= 0) return dp[i][cnt2];
        var res = 0;
        for (int d = 0, up = isLimit ? s[i] - '0' : 9; d <= up; ++d) // 枚举要填入的数字 d
            res += f(i + 1, cnt2 + (d == 2 ? 1 : 0), isLimit && d == up);
        if (!isLimit) dp[i][cnt2] = res;
        return res;
    }
}

python3 解法, 执行用时: 32 ms, 内存消耗: 15.1 MB, 提交时间: 2023-04-22 11:38:08

class Solution:
    def numberOf2sInRange(self, n: int) -> int:
        s = str(n)
        @cache
        def f(i: int, cnt2: int, is_limit: bool) -> int:
            if i == len(s):
                return cnt2
            res = 0
            up = int(s[i]) if is_limit else 9
            for d in range(up + 1):  # 枚举要填入的数字 d
                res += f(i + 1, cnt2 + (d == 2), is_limit and d == up)
            return res
        return f(0, 0, True)