dede视频网站,wordpress 获取文章中的视频,合肥网站建设过程,seo难不难学Powered by:NEFU AB-IN
Link 文章目录 2376. 统计特殊整数题意思路代码 2376. 统计特殊整数
题意
如果一个正整数每一个数位都是 互不相同 的#xff0c;我们称它是 特殊整数 。
给你一个 正 整数 n #xff0c;请你返回区间 [1, n] 之间特殊整数的数目。
思路
详见灵神…Powered by:NEFU AB-IN
Link 文章目录 2376. 统计特殊整数题意思路代码 2376. 统计特殊整数
题意
如果一个正整数每一个数位都是 互不相同 的我们称它是 特殊整数 。
给你一个 正 整数 n 请你返回区间 [1, n] 之间特殊整数的数目。
思路
详见灵神视频 https://leetcode.cn/problems/count-special-integers/solutions/1746956/shu-wei-dp-mo-ban-by-endlesscheng-xtgx/
class Solution:def countSpecialNumbers(self, n: int) - int:# 将整数 n 转换为字符串表示方便逐位处理。s str(n)lru_cache(None) # 使用缓存机制来避免重复计算提高效率。def dfs(i, mask, is_limit, is_num):使用深度优先搜索DFS和动态规划计算特殊数字的数量。参数:i (int): 当前处理的位数在字符串 s 中的索引。mask (int): 位掩码用于表示目前已经使用的数字。每个位代表一个数字位被设置为1表示该数字已使用。集合和二进制的转换关系is_limit (bool): 表示前面填的数字是否都是 n 对应位上的如果为 true那么当前位至多为 int(s[i])否则至多为 9is_num (bool): 表示当前是否已经形成了一个有效的数字避免前导零。返回值:int: 从当前状态开始的有效特殊数字的数量。# 基础情况如果已经处理完所有位。if i len(s):# 如果已经形成了一个有效的数字is_num 为 True返回 1否则返回 0。return int(is_num)# 初始化当前状态下的结果。res 0# 如果还没有形成有效数字可以选择跳过当前位。if not is_num:# 递归处理下一位不形成数字。res dfs(i 1, mask, False, False)# 确定当前位的上限。# 如果 is_limit 为 True当前位的数字不能超过 s[i]# 否则当前位可以是 0 到 9 之间的任意数字。up int(s[i]) if is_limit else 9# 确定当前位的下限。# 如果已经形成了一个数字当前位可以从 0 开始# 否则为了避免前导零当前位只能从 1 开始。down 0 if is_num else 1# 尝试当前位的所有可能数字。for d in range(down, up 1):# 检查当前数字 d 是否已经使用过即 mask 中相应的位是否已设置。if not 1 d mask:# 递归处理下一位更新位掩码和限制条件。res dfs(i 1, mask | 1 d, # 将当前数字 d 加入位掩码。is_limit and d up, # 如果 d 达到上限更新 is_limit。True # 现在已经形成了一个有效数字。)return res# 从第一位开始 DFS位掩码为空限制条件由 n 决定尚未形成数字。return dfs(0, 0, True, False)
代码 Author: NEFU AB-IN
Date: 2024-08-10 20:54:06
FilePath: \LeetCode\2376\2376.py
LastEditTime: 2024-08-12 23:45:19import random
# 3.8.19 import
from ast import Pass
from collections import Counter, defaultdict, deque
from datetime import datetime, timedelta
from functools import lru_cache, reduce
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from itertools import combinations, compress, permutations, starmap, tee
from math import ceil, comb, fabs, floor, gcd, hypot, log, perm, sqrt
from string import ascii_lowercase, ascii_uppercase
from sys import exit, setrecursionlimit, stdin
from typing import Any, Callable, Dict, List, Optional, Tuple, TypeVar, Union# 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 x0, sizeN: [x() if callable(x) else x for _ in range(size)])array2d staticmethod(lambda x0, rowsN, colsM: [Arr.array(x, cols) for _ in range(rows)])graph staticmethod(lambda sizeN: [[] 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 countSpecialNumbers(self, n: int) - int:s str(n)lru_cache(None)def dfs(i, mask, is_limit, is_num):if i len(s):return int(is_num)res 0if not is_num:res dfs(i 1, mask, False, False)up int(s[i]) if is_limit else 9down 0 if is_num else 1for d in range(down, up 1):if not 1 d mask:res dfs(i 1, mask | 1 d, is_limit and d up, True)return resreturn dfs(0, 0, True, False)
