233. 数字 1 的个数-CSDN博客

本文链接：https://blog.csdn.net/qq_45859188/article/details/141167847

Link

文章目录

233. 数字 1 的个数

233. 数字 1 的个数

题意

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

思路

套用模板
定义 dfs(i,cnt,isLimit) 表示在前 i 位有 cnt个 1 的前提下，我们能构造出的数中的 1 的个数总和。

cnt表示的是当前dp状态积攒了多少个1
此时可以不加is_num，这题统计的是 1 的个数，有没有前导零都不影响答案。如果统计的是 0 的个数就需要 is_num 了。

代码

from typing import Any, Callable, Dict, List, Optional, Tuple, TypeVar, Union
from sys import exit, setrecursionlimit, stdin
from string import ascii_lowercase, ascii_uppercase
from math import ceil, comb, fabs, floor, gcd, hypot, log, perm, sqrt
from itertools import combinations, compress, permutations, starmap, tee
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from functools import lru_cache, reduce
from datetime import datetime, timedelta
from collections import Counter, defaultdict, deque
import random
# 3.8.19 import

# Constants
TYPE = TypeVar('TYPE')
N = int(2e5 + 10)
M = int(20)
INF = int(1e12)
OFFSET = int(100)
MOD = int(1e9 + 7)

# Set recursion limit
setrecursionlimit(int(2e9))


class Arr:
    array = staticmethod(lambda x=0, size=N: [x() if callable(x) else x for _ in range(size)])
    array2d = staticmethod(lambda x=0, rows=N, cols=M: [Arr.array(x, cols) for _ in range(rows)])
    graph = staticmethod(lambda size=N: [[] for _ in range(size)])


class Math:
    max = staticmethod(lambda a, b: a if a > b else b)
    min = staticmethod(lambda a, b: a if a < b else b)


class IO:
    input = staticmethod(lambda: stdin.readline().rstrip("\r\n"))
    read = staticmethod(lambda: map(int, IO.input().split()))
    read_list = staticmethod(lambda: list(IO.read()))


class Std:
    pass

# ————————————————————— Division line ——————————————————————


class Solution:
    def countDigitOne(self, n: int) -> int:

        s = str(n)

        @lru_cache(None)
        def dfs(i, cnt, is_limit, is_num):
            if i == len(s):
                return cnt
            res = 0
            if not is_num:
                res = dfs(i + 1, cnt, False, False)

            up = int(s[i]) if is_limit else 9
            down = 0 if is_num else 1

            for d in range(down, up + 1):
                res += dfs(i + 1, cnt + (d == 1), is_limit and d == up, True)
            return res

        return dfs(0, 0, True, False)