当前位置: 首页 > news >正文

Leetcode 2999. Count the Number of Powerful Integers

  • Leetcode 2999. Count the Number of Powerful Integers
    • 1. 解题思路
    • 2. 代码实现
  • 题目链接:10034. Count the Number of Powerful Integers

1. 解题思路

这一题的话其实还是一个典型的求不大于 N N N的特殊数字个数的问题。

这道题本质上进行一下替换还是要求如下问题:

对于任意一个数 n n n,求不大于 n n n的,所有位数都不超过 l i m i t limit limit,且最后几位数为 s s s的数的个数。

此时,由于最后几位数以及被限制死了为 s s s,于是我们只需要考虑 n n n的除了最后 s s s位之外的剩余部分(不妨设为 m m m),求其所有位都不超过 l i m i t limit limit的数的个数,即:

对于任意一个数 m m m,求不大于 m m m的,且所有位数都不超过 l i m i t limit limit的数的个数。

这个就是一个比较常规的题目了,我们通过一个动态规划即可给出答案。

唯一需要注意的是,需要考虑一下如果前面的位数恰好为 m m m时,拼接上后置位 s s s是否是一个满足条件的答案,这个情况可能会给结果带来一个1的偏差,需要额外讨论一下。

2. 代码实现

给出python代码实现如下:

class Solution:@lru_cache(None)def count(self, n, max_bit):if len(n) == 0:return 1elif len(n) == 1:return 1 + min(int(n), max_bit)d = int(n[0])if d > max_bit:ans =  (1+max_bit) * self.count("9" * (len(n)-1), max_bit)else:ans = d * self.count("9" * (len(n)-1), max_bit) + self.count(n[1:], max_bit)return ansdef numberOfPowerfulInt(self, start: int, finish: int, limit: int, s: str) -> int:if any(int(bit) > limit for bit in s):return 0def count_powerful(n):ns = str(n)m = len(s)if len(ns) < m or ns < s.rjust(len(ns), "0"):return 0ans = -1 if ns[:-m] + s > ns and all(int(d) <= limit for d in ns[:-m]) else 0return ans + self.count(ns[:-m], limit)return count_powerful(finish) - count_powerful(start-1)

提交代码评测得到:耗时45ms,占用内存20.6MB。

相关文章:

Leetcode 2999. Count the Number of Powerful Integers

Leetcode 2999. Count the Number of Powerful Integers 1. 解题思路2. 代码实现 题目链接&#xff1a;10034. Count the Number of Powerful Integers 1. 解题思路 这一题的话其实还是一个典型的求不大于 N N N的特殊数字个数的问题。 这道题本质上进行一下替换还是要求如…...

【Reading Notes】(2)

文章目录 FreestyleHip-hop dance and MusicProgrammerMaster Freestyle 都说人的成长有三个阶段&#xff0c;第一个阶段认为自己独一无二&#xff0c;天之骄子&#xff1b;第二个阶段发现自己原来如此渺小&#xff0c;如此普通&#xff0c;沮丧失望&#xff1b;第三阶段&#…...

【设计模式之美】SOLID 原则之一:怎么才算是单一原则、如何取舍单一原则

文章目录 一. 如何判断类的职责是否足够单一&#xff1f;二. 类的职责是否设计得越单一越好&#xff1f; 开始学习一些经典的设计原则&#xff0c;其中包括&#xff0c;SOLID、KISS、YAGNI、DRY、LOD 等。 本文主要学习单一职责原则的相关内容。 单一职责原则的定义&#xff1a…...

# [NOIP2015 普及组] 扫雷游戏#洛谷

题目背景 NOIP2015 普及组 T2 题目描述 扫雷游戏是一款十分经典的单机小游戏。在 n n n 行 m m m 列的雷区中有一些格子含有地雷&#xff08;称之为地雷格&#xff09;&#xff0c;其他格子不含地雷&#xff08;称之为非地雷格&#xff09;。玩家翻开一个非地雷格时&#…...

Unity中Shader的_Time精度问题

文章目录 前言一、U方向上优化二、V方向上优化在这里插入图片描述 三、最终代码1、效果2、Shader 前言 在Unity的Shader中&#xff0c;使用了_Time来达到UV的流动效果&#xff0c;普遍会出现一个问题。我们的UV值会随着时间一直增加&#xff08;uv值增加了&#xff0c;但是因为…...

听GPT 讲Rust源代码--compiler(15)

File: rust/compiler/rustc_arena/src/lib.rs 在Rust源代码中&#xff0c;rustc_arena/src/lib.rs文件定义了TypedArena&#xff0c;ArenaChunk&#xff0c;DroplessArena和Arena结构体&#xff0c;以及一些与内存分配和容器操作相关的函数。 cold_path<F: FnOnce,drop,new,…...

关键字联合体union的定义和使用

联合体的定义 联合体的定义和结构体相同。 联合体成员共用存储空间&#xff0c;联合体占用的空间最大长度的数据成员的长度。 union State {char sleep;char run;int suspend;double error; }state_u;以上例子&#xff0c;State表示联合体的名字&#xff0c;它相当于声明了一…...

基于GA-PSO遗传粒子群混合优化算法的VRPTW问题求解matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.本算法原理 4.1 遗传算法&#xff08;GA&#xff09;基本原理 4.2 粒子群优化&#xff08;PSO&#xff09;基本原理 4.3 算法优化策略 5.完整程序 1.程序功能描述 VRPTW是车辆路径问题&#xff08;VR…...

【leetcode100-033】【链表】排序链表

【题干】 给你链表的头结点 head &#xff0c;请将其按 升序 排列并返回 排序后的链表 。 【思路】 递归版归并法链表版&#xff5e;没什么特别好说的&#xff08;非递归版归并也是可以哒&#xff0c;但是马上要考试了今天懒得写了&#xff01;打个flag在这里也许哪天想起来…...

[Kubernetes]5. k8s集群StatefulSet详解,以及数据持久化(SC PV PVC)

前面通过deployment结合service来部署无状态的应用,下面来讲解通过satefulSet结合service来部署有状态的应用 一.StatefulSet详解 1.有状态和无状态区别 无状态: 无状态(stateless)、牲畜(cattle)、无名(nameless)、可丢弃(disposable) 有状态: 有状态(stateful)、宠物(pet)…...

数据库系统-甘晴void学习笔记

数据库系统笔记 计科210X 甘晴void 202108010XXX 教材&#xff1a;《数据库系统概论》第6版 &#xff08;图片来源于网络&#xff0c;侵删&#xff09; 文章目录 数据库系统<br>笔记第一篇 基础篇1 绪论1.1数据库系统概述1.2数据模型1.3数据库系统的结构(三级模式结构…...

Azure Machine Learning - 人脸识别任务概述与技术实战

Azure AI 人脸服务提供了可检测、识别和分析图像中的人脸的 AI 算法。 人脸识别软件在许多不同情形中都十分重要&#xff0c;例如识别、无接触访问控制和实现隐私的人脸模糊。你可以通过客户端库 SDK&#xff0c;或者直接调用 REST API 使用人脸服务。 目录 一、人脸识别服务场…...

强化学习的数学原理学习笔记 - 蒙特卡洛方法(Monte Carlo)

文章目录 概览&#xff1a;RL方法分类蒙特卡洛方法&#xff08;Monte Carlo&#xff0c;MC&#xff09;MC BasicMC Exploring Starts&#x1f7e6;MC ε-Greedy 本系列文章介绍强化学习基础知识与经典算法原理&#xff0c;大部分内容来自西湖大学赵世钰老师的强化学习的数学原理…...

DDIA 第十一章:流处理

本文是《数据密集型应用系统设计》&#xff08;DDIA&#xff09;的读书笔记&#xff0c;一共十二章&#xff0c;我已经全部阅读并且整理完毕。 采用一问一答的形式&#xff0c;并且用列表形式整理了原文。 笔记的内容大概是原文的 1/5 ~ 1/3&#xff0c;所以你如果没有很多时间…...

webpack知识点总结(高级应用篇)

除开公共基础配置之外&#xff0c;我们意识到两点: 1. 开发环境(modedevelopment),追求强大的开发功能和效率&#xff0c;配置各种方便开 发的功能;2. 生产环境(modeproduction),追求更小更轻量的bundle(即打包产物); 而所谓高级应用&#xff0c;实际上就是进行 Webpack 优化…...

均匀与准均匀 B样条算法

B 样条曲线的定义 p ( t ) ∑ i 0 n P i F i , k ( t ) p(t) \sum_{i0}{n} P_i F_{i, k}(t) p(t)i0∑​nPi​Fi,k​(t) 方程中 n 1 n1 n1 个控制点&#xff0c; P i P_i Pi​, i 0 , 1 , ⋯ n i0, 1, \cdots n i0,1,⋯n 要用到 n 1 n1 n1 个 k k k 次 B 样条基函数 …...

2023年12 月电子学会Python等级考试试卷(一级)答案解析

青少年软件编程(Python)等级考试试卷(一级) 分数:100 题数:37 一、单选题(共25题,共50分) 1. 下列程序运行的结果是?( ) print(hello) print(world) A. helloworld...

启发式算法解决TSP、0/1背包和电路板问题

1. Las Vegas 题目 设计一个 Las Vegas 随机算法&#xff0c;求解电路板布线问题。将该算法与分支限界算法结合&#xff0c;观察求解效率。 代码 python代码如下&#xff1a; # -*- coding: utf-8 -*- """ Date : 2024/1/4 Time : 16:21 Author : …...

阿里云新用户的定义与权益

随着云计算的普及&#xff0c;阿里云作为国内领先的云计算服务提供商&#xff0c;吸引了越来越多的用户。对于新用户来说&#xff0c;了解阿里云新用户的定义和相关权益非常重要&#xff0c;因为它关系到用户能否享受到更多的优惠和服务。 一、阿里云新用户的定义 阿里云新用户…...

go语言多线程操作

目录 引言 一、如何实现多线程 1. 线程的创建与管理: 2. 共享资源与同步: 3. 线程间通信: 4. 线程的生命周期管理: 5. 线程安全: 6. 考虑并发问题: 7. 性能与资源利用: 8. 特定语言或框架的工具和库: 二、go语言多线程 Goroutine 1. 轻量级: 2. 动态栈: 3. 调度:…...

GreatSQL社区2023全年技术文章总结

GreatSQL社区自成立以来一直致力于为广大的数据库爱好者提供一个交流与学习的平台。在2023年&#xff0c;我们见证了社区的蓬勃发展&#xff0c;见证了众多技术文章的诞生与分享。 此篇总结呈现GreatSQL社区2023年社区技术文章在CSDN发布的全部。这些文章涵盖了GreatSQL、MGR、…...

【论文阅读笔记】Stable View Synthesis 和 Enhanced Stable View Synthesis

目录 Stable View Synthesis摘要引言 Enhanced Stable View Synthesis 从Mip-NeRF360的对比实验中找到的两篇文献&#xff0c;使用了卷积神经网络进行渲染和新视角合成&#xff0c;特此记录一下 ToDo Stable View Synthesis paper&#xff1a;https://readpaper.com/pdf-ann…...

网络报文分析程序的设计与实现(2024)

1.题目描述 在上一题的基础上&#xff0c;参照教材中各层报文的头部结构&#xff0c;结合使用 wireshark 软件&#xff08;下载地址 https://www.wireshark.org/download.html#releases&#xff09;观察网络各层报文捕获&#xff0c;解析和分析的过程&#xff08;如下 图所示&a…...

贯穿设计模式-享元模式思考

写享元模式的时候&#xff0c;会想使用ConcurrentHashMap来保证并发&#xff0c;没有使用双重锁会不会有问题&#xff1f;但是在synchronize代码块里面需要尽量避免throw异常&#xff0c;希望有经验的同学能够给出解答&#xff1f; 1月6号补充&#xff1a;没有使用双重锁会有问…...

牛客刷题:BC45 小乐乐改数字(中等)

自我介绍&#xff1a;一个脑子不好的大一学生&#xff0c;c语言接触还没到半年&#xff0c;若涉及到效率等问题&#xff0c;各位都可以在评论区提出见解&#xff0c;谢谢啦。 该账号介绍&#xff1a;此帐号会发布游戏&#xff08;目前还只会简单小游戏&#xff09;&#xff0c…...

设计模式学习2

代理模式&#xff1a;Proxy 动机 “增加一层间接层”是软件系统中对许多复杂问题的一种常见解决方案。在面向对象系统中&#xff0c;直接食用某些对象会带来很多问题&#xff0c;作为间接层的proxy对象便是解决这一问题的常见手段。 2.伪代码&#xff1a; class ISubject{ pu…...

Rust:如何判断位置结构的JSON串的成员的数据类型

如何判断位置结构的JSON串的成员的数据类型&#xff0c;给一个Rust的例子&#xff0c;其中包含对数组的判断&#xff1f; 在Rust中&#xff0c;你可以使用serde_json库来处理JSON数据&#xff0c;并通过serde_json::Value类型的方法来判断JSON串中成员的数据类型。以下是一个示…...

Kafka(五)生产者

目录 Kafka生产者1 配置生产者bootstrap.serverskey.serializervalue.serializerclient.id""acksallbuffer.memory33554432(32MB)compression.typenonebatch.size16384(16KB)max.in.flight.requests.per.connection5max.request.size1048576(1MB)receive.buffer.byte…...

【Leetcode】242.有效的字母异位词

一、题目 1、题目描述 给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。 注意:若 s 和 t 中每个字符出现的次数都相同,则称 s 和 t 互为字母异位词。 示例1: 输入: s = "anagram", t = "nagaram" 输出: true示例2: 输入: …...

【数据库原理】(16)关系数据理论的函数依赖

一.函数依赖的概念 函数依赖是关系数据库中核心的概念&#xff0c;它指的是在属性集之间存在的一种特定的关系。这种关系表明&#xff0c;一个属性集的值可以唯一确定另一个属性集的值。 属性子集&#xff1a;在关系模式中&#xff0c;X和Y可以是单个属性&#xff0c;也可以是…...

wordpress果酱主题/百度首页入口

展开全部php要计算两个62616964757a686964616fe58685e5aeb931333366306538时间戳之间相差的日时分秒可以参考以下内容&#xff1a;//功能&#xff1a;计算两个时间戳之间相差的日时分秒//$begin_time 开始时间戳//$end_time 结束时间戳function timediff($begin_time,$end_tim…...

网站建设 自助建站/百度一下首页网页手机版

上一篇&#xff1a;《IDDD 实现领域驱动设计&#xff0d;CQRS&#xff08;命令查询职责分离&#xff09;和 EDA&#xff08;事件驱动架构&#xff09;》 学习架构知识&#xff0c;需要有一些功底和经验&#xff0c;要不然你会和我一样吃力&#xff0c;CQRS、EDA、ES、Saga 等等…...

网站开发需要哪些软件/营销型网站模板

分为局部和全局&#xff1a; 1、线程组右击 新建的 则为全局&#xff1a; 2、某个请求右击新建的&#xff0c;则为局部的&#xff1a;...

wordpress源码解析/如何写好软文推广

3.2 transport 层 TCP和UDP 3.2.1 TCP Transmission Control Protocol 3.2.1.1 TCP特性...

上海网站排名优化公司/个人网站设计模板

自从使用Vue2之后,就使用官方推荐的axios的插件来调用API,在使用过程中,如果服务器或者网络不稳定掉包了, 你们该如何处理呢? 下面我给你们分享一下我的经历。 具体原因 最近公司在做一个项目, 服务端数据接口用的是Php输出的API, 有时候在调用的过程中会失败, 在谷歌浏览器…...

手机网站头部/百度云资源搜索引擎

1.下载并安装5.5.0版本的Font Awesome 5字体文件。下载地址&#xff1a;下载之后将文件解压缩&#xff0c;打开里面的“otfs”文件夹&#xff0c;安装“Font Awesome 5 Brands-Regular-400.otf”、“Font Awesome 5 Free-Regular-400.otf”和“Font Awesome 5 Free-Solid-900.o…...