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

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.下一个更大的数值平衡数 力扣题目链接&#xff1a;https://leetcode.cn/problems/next-greater-numerically-balanced-number/ 如果整数 x 满足&#xff1a;对于每个数位 d &#xff0c;这个数位 恰好 在 x 中出现 d 次。那么整数 x 就是一个 数值平衡数 。…...

多线程(初阶七:阻塞队列和生产者消费者模型)

目录 一、阻塞队列的简单介绍 二、生产者消费者模型 1、举个栗子&#xff1a; 2、引入生产者消费者模型的意义&#xff1a; &#xff08;1&#xff09;解耦合 &#xff08;2&#xff09;削峰填谷 三、模拟实现阻塞队列 1、阻塞队列的简单介绍 2、实现阻塞队列 &#…...

区间价值 --- 题解--动态规划

目录 区间价值 题目描述 输入描述: 输出描述: 输入 输出 备注: 思路&#xff1a; 代码&#xff1a; 区间价值 J-区间价值_牛客竞赛动态规划专题班习题课 (nowcoder.com) 时间限制&#xff1a;C/C 2秒&#xff0c;其他语言4秒 空间限制&#xff1a;C/C 262144K&…...

计算机毕业设计 基于大数据的心脏病患者数据分析管理系统的设计与实现 Java实战项目 附源码+文档+视频讲解

博主介绍&#xff1a;✌从事软件开发10年之余&#xff0c;专注于Java技术领域、Python人工智能及数据挖掘、小程序项目开发和Android项目开发等。CSDN、掘金、华为云、InfoQ、阿里云等平台优质作者✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精…...

20:kotlin 类和对象 --泛型(Generics)

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

我对迁移学习的一点理解(系列2)

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

Spring MVC学习随笔-控制器(Controller)开发详解:控制器跳转与作用域(二)视图模板、静态资源访问

学习视频&#xff1a;孙哥说SpringMVC&#xff1a;结合Thymeleaf&#xff0c;重塑你的MVC世界&#xff01;&#xff5c;前所未有的Web开发探索之旅 衔接上文Spring MVC学习随笔-控制器(Controller)开发详解&#xff1a;控制器跳转与作用域&#xff08;一&#xff09; SpingMVC中…...

原型模式(Prototype Pattern)

1 基本概念 1.1 大佬文章 设计模式是什么鬼&#xff08;原型&#xff09; 详解设计模式&#xff1a;原型模式-腾讯云开发者社区-腾讯云 1.2 知识汇总 &#xff08;1&#xff09;原型模式&#xff1a;先 new 一个实例&#xff0c;该实例符合需求&#xff0c;之后再根据这个实…...

IM通信技术快速入门:短轮询、长轮询、SSE、WebSocket

文章目录 1. 引言2. 短轮询&#xff08;Short Polling&#xff09;2.1 原理2.2 代码示例2.2.1 服务器端&#xff08;Node.js&#xff09;2.2.2 客户端&#xff08;HTML JavaScript&#xff09; 3. 长轮询&#xff08;Long Polling&#xff09;3.1 原理3.2 代码示例3.2.1 服务器…...

04_W5500_TCP_Server

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

入门Redis学习总结

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

SpringSecurity6 | 自定义登录页面

✅作者简介&#xff1a;大家好&#xff0c;我是Leo&#xff0c;热爱Java后端开发者&#xff0c;一个想要与大家共同进步的男人&#x1f609;&#x1f609; &#x1f34e;个人主页&#xff1a;Leo的博客 &#x1f49e;当前专栏&#xff1a; Java从入门到精通 ✨特色专栏&#xf…...

从单向链表中删除指定值的节点

输入一个单向链表和一个节点的值&#xff0c;从单向链表中删除等于该值的节点&#xff0c;删除后如果链表中无节点则返回空指针。 链表的值不能重复。构造过程&#xff0c;例如输入一行数据为:6 2 1 2 3 2 5 1 4 5 7 2 2则第一个参数6表示输入总共6个节点&#xff0c;第二个参数…...

Vue2与Vue3的语法对比

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

实时动作识别学习笔记

目录 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 编写目的 本次测试报告&#xff0c;为自动化测试框架性能测试总结报告。目的在于总结我们课程所压测的目标系统的性能点、优化历史和可优化方向。 1.2 项目背景 我们公开课的性能测试目标系统。主要是用于我们课程自动化测试框架功能的实现&#xff0c;以及…...

【SpringBoot】解析Springboot事件机制,事件发布和监听

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

华为ensp实验——基于全局地址池的DHCP组网实验

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

如何选择一款安全可靠的跨网安全数据交换系统?

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

OpenLayers 可视化之热力图

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 热力图&#xff08;Heatmap&#xff09;又叫热点图&#xff0c;是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍

文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结&#xff1a; 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析&#xff1a; 实际业务去理解体会统一注…...

自然语言处理——Transformer

自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效&#xff0c;它能挖掘数据中的时序信息以及语义信息&#xff0c;但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN&#xff0c;但是…...

SpringTask-03.入门案例

一.入门案例 启动类&#xff1a; package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...

分布式增量爬虫实现方案

之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面&#xff0c;避免重复抓取&#xff0c;以节省资源和时间。 在分布式环境下&#xff0c;增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路&#xff1a;将增量判…...

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...

短视频矩阵系统文案创作功能开发实践,定制化开发

在短视频行业迅猛发展的当下&#xff0c;企业和个人创作者为了扩大影响力、提升传播效果&#xff0c;纷纷采用短视频矩阵运营策略&#xff0c;同时管理多个平台、多个账号的内容发布。然而&#xff0c;频繁的文案创作需求让运营者疲于应对&#xff0c;如何高效产出高质量文案成…...

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...

纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...