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. 代码实现 题目链接:10034. Count the Number of Powerful Integers 1. 解题思路 这一题的话其实还是一个典型的求不大于 N N N的特殊数字个数的问题。 这道题本质上进行一下替换还是要求如…...
【Reading Notes】(2)
文章目录 FreestyleHip-hop dance and MusicProgrammerMaster Freestyle 都说人的成长有三个阶段,第一个阶段认为自己独一无二,天之骄子;第二个阶段发现自己原来如此渺小,如此普通,沮丧失望;第三阶段&#…...
【设计模式之美】SOLID 原则之一:怎么才算是单一原则、如何取舍单一原则
文章目录 一. 如何判断类的职责是否足够单一?二. 类的职责是否设计得越单一越好? 开始学习一些经典的设计原则,其中包括,SOLID、KISS、YAGNI、DRY、LOD 等。 本文主要学习单一职责原则的相关内容。 单一职责原则的定义:…...
# [NOIP2015 普及组] 扫雷游戏#洛谷
题目背景 NOIP2015 普及组 T2 题目描述 扫雷游戏是一款十分经典的单机小游戏。在 n n n 行 m m m 列的雷区中有一些格子含有地雷(称之为地雷格),其他格子不含地雷(称之为非地雷格)。玩家翻开一个非地雷格时&#…...
Unity中Shader的_Time精度问题
文章目录 前言一、U方向上优化二、V方向上优化在这里插入图片描述 三、最终代码1、效果2、Shader 前言 在Unity的Shader中,使用了_Time来达到UV的流动效果,普遍会出现一个问题。我们的UV值会随着时间一直增加(uv值增加了,但是因为…...
听GPT 讲Rust源代码--compiler(15)
File: rust/compiler/rustc_arena/src/lib.rs 在Rust源代码中,rustc_arena/src/lib.rs文件定义了TypedArena,ArenaChunk,DroplessArena和Arena结构体,以及一些与内存分配和容器操作相关的函数。 cold_path<F: FnOnce,drop,new,…...
关键字联合体union的定义和使用
联合体的定义 联合体的定义和结构体相同。 联合体成员共用存储空间,联合体占用的空间最大长度的数据成员的长度。 union State {char sleep;char run;int suspend;double error; }state_u;以上例子,State表示联合体的名字,它相当于声明了一…...
基于GA-PSO遗传粒子群混合优化算法的VRPTW问题求解matlab仿真
目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.本算法原理 4.1 遗传算法(GA)基本原理 4.2 粒子群优化(PSO)基本原理 4.3 算法优化策略 5.完整程序 1.程序功能描述 VRPTW是车辆路径问题(VR…...
【leetcode100-033】【链表】排序链表
【题干】 给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。 【思路】 递归版归并法链表版~没什么特别好说的(非递归版归并也是可以哒,但是马上要考试了今天懒得写了!打个flag在这里也许哪天想起来…...
[Kubernetes]5. k8s集群StatefulSet详解,以及数据持久化(SC PV PVC)
前面通过deployment结合service来部署无状态的应用,下面来讲解通过satefulSet结合service来部署有状态的应用 一.StatefulSet详解 1.有状态和无状态区别 无状态: 无状态(stateless)、牲畜(cattle)、无名(nameless)、可丢弃(disposable) 有状态: 有状态(stateful)、宠物(pet)…...
数据库系统-甘晴void学习笔记
数据库系统笔记 计科210X 甘晴void 202108010XXX 教材:《数据库系统概论》第6版 (图片来源于网络,侵删) 文章目录 数据库系统<br>笔记第一篇 基础篇1 绪论1.1数据库系统概述1.2数据模型1.3数据库系统的结构(三级模式结构…...
Azure Machine Learning - 人脸识别任务概述与技术实战
Azure AI 人脸服务提供了可检测、识别和分析图像中的人脸的 AI 算法。 人脸识别软件在许多不同情形中都十分重要,例如识别、无接触访问控制和实现隐私的人脸模糊。你可以通过客户端库 SDK,或者直接调用 REST API 使用人脸服务。 目录 一、人脸识别服务场…...
强化学习的数学原理学习笔记 - 蒙特卡洛方法(Monte Carlo)
文章目录 概览:RL方法分类蒙特卡洛方法(Monte Carlo,MC)MC BasicMC Exploring Starts🟦MC ε-Greedy 本系列文章介绍强化学习基础知识与经典算法原理,大部分内容来自西湖大学赵世钰老师的强化学习的数学原理…...
DDIA 第十一章:流处理
本文是《数据密集型应用系统设计》(DDIA)的读书笔记,一共十二章,我已经全部阅读并且整理完毕。 采用一问一答的形式,并且用列表形式整理了原文。 笔记的内容大概是原文的 1/5 ~ 1/3,所以你如果没有很多时间…...
webpack知识点总结(高级应用篇)
除开公共基础配置之外,我们意识到两点: 1. 开发环境(modedevelopment),追求强大的开发功能和效率,配置各种方便开 发的功能;2. 生产环境(modeproduction),追求更小更轻量的bundle(即打包产物); 而所谓高级应用,实际上就是进行 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∑nPiFi,k(t) 方程中 n 1 n1 n1 个控制点, 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 随机算法,求解电路板布线问题。将该算法与分支限界算法结合,观察求解效率。 代码 python代码如下: # -*- coding: utf-8 -*- """ Date : 2024/1/4 Time : 16:21 Author : …...
阿里云新用户的定义与权益
随着云计算的普及,阿里云作为国内领先的云计算服务提供商,吸引了越来越多的用户。对于新用户来说,了解阿里云新用户的定义和相关权益非常重要,因为它关系到用户能否享受到更多的优惠和服务。 一、阿里云新用户的定义 阿里云新用户…...
go语言多线程操作
目录 引言 一、如何实现多线程 1. 线程的创建与管理: 2. 共享资源与同步: 3. 线程间通信: 4. 线程的生命周期管理: 5. 线程安全: 6. 考虑并发问题: 7. 性能与资源利用: 8. 特定语言或框架的工具和库: 二、go语言多线程 Goroutine 1. 轻量级: 2. 动态栈: 3. 调度:…...
Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...
从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)
设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...
Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级
在互联网的快速发展中,高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司,近期做出了一个重大技术决策:弃用长期使用的 Nginx,转而采用其内部开发…...
基于Docker Compose部署Java微服务项目
一. 创建根项目 根项目(父项目)主要用于依赖管理 一些需要注意的点: 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件,否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...
12.找到字符串中所有字母异位词
🧠 题目解析 题目描述: 给定两个字符串 s 和 p,找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义: 若两个字符串包含的字符种类和出现次数完全相同,顺序无所谓,则互为…...
如何在最短时间内提升打ctf(web)的水平?
刚刚刷完2遍 bugku 的 web 题,前来答题。 每个人对刷题理解是不同,有的人是看了writeup就等于刷了,有的人是收藏了writeup就等于刷了,有的人是跟着writeup做了一遍就等于刷了,还有的人是独立思考做了一遍就等于刷了。…...
基于 TAPD 进行项目管理
起因 自己写了个小工具,仓库用的Github。之前在用markdown进行需求管理,现在随着功能的增加,感觉有点难以管理了,所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD,需要提供一个企业名新建一个项目&#…...
uniapp手机号一键登录保姆级教程(包含前端和后端)
目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号(第三种)后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...
【JVM】Java虚拟机(二)——垃圾回收
目录 一、如何判断对象可以回收 (一)引用计数法 (二)可达性分析算法 二、垃圾回收算法 (一)标记清除 (二)标记整理 (三)复制 (四ÿ…...
【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)
LeetCode 3309. 连接二进制表示可形成的最大数值(中等) 题目描述解题思路Java代码 题目描述 题目链接:LeetCode 3309. 连接二进制表示可形成的最大数值(中等) 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...
