LeetCode 2048. 下一个更大的数值平衡数
【LetMeFly】2048.下一个更大的数值平衡数
力扣题目链接:https://leetcode.cn/problems/next-greater-numerically-balanced-number/
如果整数 x
满足:对于每个数位 d
,这个数位 恰好 在 x
中出现 d
次。那么整数 x
就是一个 数值平衡数 。
给你一个整数 n
,请你返回 严格大于 n
的 最小数值平衡数 。
示例 1:
输入:n = 1 输出:22 解释: 22 是一个数值平衡数,因为: - 数字 2 出现 2 次 这也是严格大于 1 的最小数值平衡数。
示例 2:
输入:n = 1000 输出:1333 解释: 1333 是一个数值平衡数,因为: - 数字 1 出现 1 次。 - 数字 3 出现 3 次。 这也是严格大于 1000 的最小数值平衡数。 注意,1022 不能作为本输入的答案,因为数字 0 的出现次数超过了 0 。
示例 3:
输入:n = 3000 输出:3133 解释: 3133 是一个数值平衡数,因为: - 数字 1 出现 1 次。 - 数字 3 出现 3 次。 这也是严格大于 3000 的最小数值平衡数。
提示:
0 <= n <= 106
方法一:枚举
我们可以很方便地写一个函数用来判断一个数 n n n是否为“数值平衡数”。
只需要取出这个数的每一位并统计出现次数,从0到10遍历,如果出现次数不等于这个数就返回false,否则返回true。
接下来从给定的 n n n的下一个数开始枚举,直到枚举到了“数值平衡数”为止。
- 时间复杂度:不易计算,但是能过(方法二中也可以看出无论给定n是多少,枚举量都不超过557778)
- 空间复杂度 O ( 1 ) O(1) O(1)
AC代码
C++
class Solution {
private:bool isok(int n) {int cnt[10] = {0};while (n) {cnt[n % 10]++;n /= 10;}for (int i = 0; i <= 9; i++) {if (cnt[i] && cnt[i] != i) {return false;}}return true;}public:int nextBeautifulNumber(int n) {while (!isok(++n));return n;}
};
Python
class Solution:def ok(self, n: int) -> bool:cnt = [0] * 10while n:cnt[n % 10] += 1n //= 10for i in range(10):if cnt[i] and cnt[i] != i:return Falsereturn Truedef nextBeautifulNumber(self, n: int) -> int:while True:n += 1if self.ok(n):return n
方法二:打表
方法一中我们实现了“判断一个数是否为数值平衡数的函数”,因此我们可以写一个简单的程序,预先将所有可能用到的“数值平衡数”存下来:
#include <bits/stdc++.h>
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << #x << " = " << x << endl
#define fi(i, l, r) for (int i = l; i < r; i++)
#define cd(a) scanf("%d", &a)
typedef long long ll;bool isok(int n) {int cnt[10] = {0};while (n) {cnt[n % 10]++;n /= 10;}for (int i = 0; i <= 9; i++) {if (cnt[i] && cnt[i] != i) {return false;}}return true;
}int main() {vector<int> ok;int n = 0;while (++n) {if (isok(n)) {ok.push_back(n);if (n > 1000000) {break;}}}for (int t : ok) {cout << t << ", ";}puts("");return 0;
}
上述代码不重要,反正只要能得到下面的这个表就好:
1, 22, 122, 212, 221, 333, 1333, 3133, 3313, 3331, 4444, 14444, 22333, 23233, 23323, 23332, 32233, 32323, 32332, 33223, 33232, 33322, 41444, 44144, 44414, 44441, 55555, 122333, 123233, 123323, 123332, 132233, 132323, 132332, 133223, 133232, 133322, 155555, 212333, 213233, 213323, 213332, 221333, 223133, 223313, 223331, 224444, 231233, 231323, 231332, 232133, 232313, 232331, 233123, 233132, 233213, 233231, 233312, 233321, 242444, 244244, 244424, 244442, 312233, 312323, 312332, 313223, 313232, 313322, 321233, 321323, 321332, 322133, 322313, 322331, 323123, 323132, 323213, 323231, 323312, 323321, 331223, 331232, 331322, 332123, 332132, 332213, 332231, 332312, 332321, 333122, 333212, 333221, 422444, 424244, 424424, 424442, 442244, 442424, 442442, 444224, 444242, 444422, 515555, 551555, 555155, 555515, 555551, 666666, 1224444
这是从1到1224444的所有“数值平衡数”。有了这张表,不论给你的n等于几,你都可以通过二分等方式在极短的时间内找到第一个大于n的“数值平衡数”。
- 时间复杂度 log l e n ( B i a o ) \log len(Biao) loglen(Biao),其中表的大小 l e n ( B i a o ) = 110 len(Biao)=110 len(Biao)=110
- 空间复杂度 O ( l e n ( B i a o ) ) O(len(Biao)) O(len(Biao))
AC代码
C++
const int ok[] = {1, 22, 122, 212, 221, 333, 1333, 3133, 3313, 3331, 4444, 14444, 22333, 23233, 23323, 23332, 32233, 32323, 32332, 33223, 33232, 33322, 41444, 44144, 44414, 44441, 55555, 122333, 123233, 123323, 123332, 132233, 132323, 132332, 133223, 133232, 133322, 155555, 212333, 213233, 213323, 213332, 221333, 223133, 223313, 223331, 224444, 231233, 231323, 231332, 232133, 232313, 232331, 233123, 233132, 233213, 233231, 233312, 233321, 242444, 244244, 244424, 244442, 312233, 312323, 312332, 313223, 313232, 313322, 321233, 321323, 321332, 322133, 322313, 322331, 323123, 323132, 323213, 323231, 323312, 323321, 331223, 331232, 331322, 332123, 332132, 332213, 332231, 332312, 332321, 333122, 333212, 333221, 422444, 424244, 424424, 424442, 442244, 442424, 442442, 444224, 444242, 444422, 515555, 551555, 555155, 555515, 555551, 666666, 1224444};class Solution {
public:int nextBeautifulNumber(int n) {return *upper_bound(ok, ok + sizeof(ok) / sizeof(int), n);}
};
Python
# from bisect import bisect_rightok = [1, 22, 122, 212, 221, 333, 1333, 3133, 3313, 3331, 4444, 14444, 22333, 23233, 23323, 23332, 32233, 32323, 32332, 33223, 33232, 33322, 41444, 44144, 44414, 44441, 55555, 122333, 123233, 123323, 123332, 132233, 132323, 132332, 133223, 133232, 133322, 155555, 212333, 213233, 213323, 213332, 221333, 223133, 223313, 223331, 224444, 231233, 231323, 231332, 232133, 232313, 232331, 233123, 233132, 233213, 233231, 233312, 233321, 242444, 244244, 244424, 244442, 312233, 312323, 312332, 313223, 313232, 313322, 321233, 321323, 321332, 322133, 322313, 322331, 323123, 323132, 323213, 323231, 323312, 323321, 331223, 331232, 331322, 332123, 332132, 332213, 332231, 332312, 332321, 333122, 333212, 333221, 422444, 424244, 424424, 424442, 442244, 442424, 442442, 444224, 444242, 444422, 515555, 551555, 555155, 555515, 555551, 666666, 1224444]class Solution:def nextBeautifulNumber(self, n: int) -> int:return ok[bisect_right(ok, n)]
同步发文于CSDN,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/134900679
相关文章:
LeetCode 2048. 下一个更大的数值平衡数
【LetMeFly】2048.下一个更大的数值平衡数 力扣题目链接:https://leetcode.cn/problems/next-greater-numerically-balanced-number/ 如果整数 x 满足:对于每个数位 d ,这个数位 恰好 在 x 中出现 d 次。那么整数 x 就是一个 数值平衡数 。…...

多线程(初阶七:阻塞队列和生产者消费者模型)
目录 一、阻塞队列的简单介绍 二、生产者消费者模型 1、举个栗子: 2、引入生产者消费者模型的意义: (1)解耦合 (2)削峰填谷 三、模拟实现阻塞队列 1、阻塞队列的简单介绍 2、实现阻塞队列 &#…...
区间价值 --- 题解--动态规划
目录 区间价值 题目描述 输入描述: 输出描述: 输入 输出 备注: 思路: 代码: 区间价值 J-区间价值_牛客竞赛动态规划专题班习题课 (nowcoder.com) 时间限制:C/C 2秒,其他语言4秒 空间限制:C/C 262144K&…...

计算机毕业设计 基于大数据的心脏病患者数据分析管理系统的设计与实现 Java实战项目 附源码+文档+视频讲解
博主介绍:✌从事软件开发10年之余,专注于Java技术领域、Python人工智能及数据挖掘、小程序项目开发和Android项目开发等。CSDN、掘金、华为云、InfoQ、阿里云等平台优质作者✌ 🍅文末获取源码联系🍅 👇🏻 精…...

20:kotlin 类和对象 --泛型(Generics)
类可以有类型参数 class Box<T>(t: T) {var value t }要创建类实例,需提供类型参数 val box: Box<Int> Box<Int>(1)如果类型可以被推断出来,可以省略 val box Box(1)通配符 在JAVA泛型中有通配符?、? extends E、? super E&…...

我对迁移学习的一点理解(系列2)
文章目录 我对迁移学习的一点理解 我对迁移学习的一点理解 源域和目标域是相对的概念,指的是在迁移学习任务中涉及到的两个不同的数据集或领域。 源域(Source Domain)通常指的是已经进行过训练和学习的数据集,它被用来提取特征、…...

Spring MVC学习随笔-控制器(Controller)开发详解:控制器跳转与作用域(二)视图模板、静态资源访问
学习视频:孙哥说SpringMVC:结合Thymeleaf,重塑你的MVC世界!|前所未有的Web开发探索之旅 衔接上文Spring MVC学习随笔-控制器(Controller)开发详解:控制器跳转与作用域(一) SpingMVC中…...
原型模式(Prototype Pattern)
1 基本概念 1.1 大佬文章 设计模式是什么鬼(原型) 详解设计模式:原型模式-腾讯云开发者社区-腾讯云 1.2 知识汇总 (1)原型模式:先 new 一个实例,该实例符合需求,之后再根据这个实…...

IM通信技术快速入门:短轮询、长轮询、SSE、WebSocket
文章目录 1. 引言2. 短轮询(Short Polling)2.1 原理2.2 代码示例2.2.1 服务器端(Node.js)2.2.2 客户端(HTML JavaScript) 3. 长轮询(Long Polling)3.1 原理3.2 代码示例3.2.1 服务器…...

04_W5500_TCP_Server
上一节我们完成了TCP_Client实验,这节使用W5500作为服务端与TCP客户端进行通信。 目录 1.W5500服务端要做的: 2.代码分析: 3.测试: 1.W5500服务端要做的: 服务端只需要打开socket,然后监听端口即可。 2…...

入门Redis学习总结
记录之前刚学习Redis 的笔记, 主要包括Redis的基本数据结构、Redis 发布订阅机制、Redis 事务、Redis 服务器相关及采用Spring Boot 集成Redis 实现增删改查基本功能 一:常用命令及数据结构 1.Redis 键(key) # 设置key和value 127.0.0.1:6379> set …...

SpringSecurity6 | 自定义登录页面
✅作者简介:大家好,我是Leo,热爱Java后端开发者,一个想要与大家共同进步的男人😉😉 🍎个人主页:Leo的博客 💞当前专栏: Java从入门到精通 ✨特色专栏…...
从单向链表中删除指定值的节点
输入一个单向链表和一个节点的值,从单向链表中删除等于该值的节点,删除后如果链表中无节点则返回空指针。 链表的值不能重复。构造过程,例如输入一行数据为:6 2 1 2 3 2 5 1 4 5 7 2 2则第一个参数6表示输入总共6个节点,第二个参数…...

Vue2与Vue3的语法对比
Vue2与Vue3的语法对比 Vue.js是一款流行的JavaScript框架,通过它可以更加轻松地构建Web用户界面。随着Vue.js的不断发展,Vue2的语法已经在很多应用中得到了广泛应用。而Vue3于2020年正式发布,带来了许多新的特性和改进,同时也带来…...

实时动作识别学习笔记
目录 yowo v2 yowof 判断是在干什么,不能获取细节信息 yowo v2 https://github.com/yjh0410/YOWOv2/blob/master/README_CN.md ModelClipmAPFPSweightYOWOv2-Nano1612.640ckptYOWOv2-Tiny...
5G常用简称
名称缩写全称非周期 信道状态信息参考信号aperidoc CSIAperidoc Channel State Information缓冲区状态报告BSRBuffer Status Report小区特定无线网络标识CS-RNTICell-Specific Radio Network Temporary Identifier主小区组MCGMaster Cell groupMCG的节点MNMasternode主小区PCel…...

自动化测试框架性能测试报告模板
一、项目概述 1.1 编写目的 本次测试报告,为自动化测试框架性能测试总结报告。目的在于总结我们课程所压测的目标系统的性能点、优化历史和可优化方向。 1.2 项目背景 我们公开课的性能测试目标系统。主要是用于我们课程自动化测试框架功能的实现,以及…...

【SpringBoot】解析Springboot事件机制,事件发布和监听
解析Springboot事件机制,事件发布和监听 一、Spring的事件是什么二、使用步骤2.1 依赖处理2.2 定义事件实体类2.3 定义事件监听类2.4 事件发布 三、异步调用3.1 启用异步调用3.2 监听器方法上添加 Async 注解 一、Spring的事件是什么 Spring的事件监听(…...

华为ensp实验——基于全局地址池的DHCP组网实验
目录 前言实验目的实验内容实验结果 前言 该实验基于华为ensp,版本号是1.3.00.100 V100R003C00SPC100,只供学习和参考,不作任何商业用途。 具体的DHCP命令可以看系列文章链接,计算机网络实验(华为eNSP模拟器ÿ…...

如何选择一款安全可靠的跨网安全数据交换系统?
随着网络和数据安全的重视程度增加,为了有效地保护内部的核心数据资产,普遍会采用内外网隔离的策略。像国内的政府机构、金融、能源电力、航空航天、医院等关乎国计民生的行业和领域均已进行了网络的隔离,将内部划分成不同的网段,…...

Linux应用开发之网络套接字编程(实例篇)
服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端
🌟 什么是 MCP? 模型控制协议 (MCP) 是一种创新的协议,旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议,它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...
【解密LSTM、GRU如何解决传统RNN梯度消失问题】
解密LSTM与GRU:如何让RNN变得更聪明? 在深度学习的世界里,循环神经网络(RNN)以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而,传统RNN存在的一个严重问题——梯度消失&#…...

cf2117E
原题链接:https://codeforces.com/contest/2117/problem/E 题目背景: 给定两个数组a,b,可以执行多次以下操作:选择 i (1 < i < n - 1),并设置 或,也可以在执行上述操作前执行一次删除任意 和 。求…...

React19源码系列之 事件插件系统
事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

在WSL2的Ubuntu镜像中安装Docker
Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包: for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...
OpenLayers 分屏对比(地图联动)
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能,和卷帘图层不一样的是,分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

C++ 设计模式 《小明的奶茶加料风波》
👨🎓 模式名称:装饰器模式(Decorator Pattern) 👦 小明最近上线了校园奶茶配送功能,业务火爆,大家都在加料: 有的同学要加波霸 🟤,有的要加椰果…...