把数组排成最小的数 AcWing(JAVA)
输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。
例如输入数组 [3,32,321][3,32,321],则打印出这 33 个数字能排成的最小数字 321323321323。
数据范围
数组长度 [0,500][0,500]。
样例:
输入:[3, 32, 321]
输出:321323
注意:输出数字的格式为字符串。
解题思路: 首先假设数组内的数为 [a, b, c]。若定义一个新的排序方法即 ab > ba,即a在头部的拼接结果比b在头部的拼接结果大,那么就交换a,b在数组内的位置。以这种判断方式排列出来的新数组,从前往后拼接起来就是我们本题需要的最小数。
以下是证明上述排序方式是有意义的:
设a, b, c 的位数分别为n , m , k。
1.若 ab >= ba 且 ab <= ba是否能证明 ab = ba。
证明:由于ab与ba位数相同,在数值上比较本假设理应成立,所以此排序满足反对称性。
2.若 ab < ba 且 bc < cb,是否能证明 ac < ca。
证明:ab = a*10^m + b, ba = b*10^n + a,ac = a*10^k + c, ca = c*10^n + a;
由 ab < ba 得 a/b = (10^n - 1 )/(10^m - 1)
由 bc < cb 得b/c = (10^m - 1)/(10^k - 1)
只需证明 a/c = (10^n - 1)/(10^k - 1)
结论显然成立。即此排序方法满足传递性。
由于sort()方法核心是快速排序,快排核心就是反对称性(特定情况唯一)与 传递性(让数据有梯度)。所以此新定义得排序方法有意义。
最后我们只需证明我们排序后的数组就是最优数组即可:
设我们排序后的数组是 [a, b, c, d],那么最小数就是 abcd
利用反证法:
假设最小数是acbd,由于a,d所处位置一样所以比较bc,cb大小即可
由我们的新排序定义可知 bc < cb 所以 abcd < acbd,所以假设不成立。
即排序后的数组就是最优数组。
理论成立代码如下:
class Solution {public String printMinNumber(int[] nums) {Integer a[] = new Integer[nums.length];for(int i =0; i < nums.length; i ++) a[i] = nums[i];//只能转换成Integer类Arrays.sort(a, new Comparator<Integer>() {public int compare(Integer o1, Integer o2) {//新排序方法String a = "" + o1;String b = "" + o2;if(Integer.valueOf(a + b) > Integer.valueOf(b + a))return 1;//交换位置else return -1;//不换}});String s1 = "";for(int i = 0; i < a.length; i ++) s1 = s1 + a[i];return s1;}
}
相关文章:
把数组排成最小的数 AcWing(JAVA)
输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。 例如输入数组 [3,32,321][3,32,321],则打印出这 33 个数字能排成的最小数字 321323321323。 数据范围 数组长度 [0,500][0,500]。 样例&#x…...
4.3 PBR
1. 实验目的 熟悉PBR的应用场景掌握PBR的配置方法2. 实验拓扑 PBR实验拓扑如图4-8所示: 图4-8:PBR 3. 实验步骤 (1) IP地址的配置 R1的配置 <Huawei>system-view...
hmac — 加密消息签名和验证
hmac — 加密消息签名和验证 1.概述 它的全称叫做Hash-based Message Authentication Code: 哈希消息认证码,从名字中就可以看出来这个hmac基于哈希函数的,并且还得提供一个秘钥key,它的作用就是用来保证消息的完整性,不可篡改。…...
AWS攻略——使用ACL限制访问
文章目录确定出口IP修改ACL修改主网络ACL修改入站规则修改子网ACL创建子网ACL新增入站规则新增出站规则关联子网假如我们希望限制只有公司内部的IP可以SSH登录到EC2,则可以考虑使用ACL来实现。 我们延续使用《AWS攻略——创建VPC》的案例,在它的基础上做…...
【已解决】关于 luckysheet 设置纯文本,解决日期格式回显错误的办法
目录 一、现象 二、分析 三、思考过程 五、解决 六、参考链接 一、现象 在excel里面输入内容,如 2023-2-17 12:00 保存后,传回后端的数据被转化成了 数值类型,这显然是一种困扰。 如图所示 二、分析 查阅了文档和一些博客发现 Lucky…...
Jackson
first you need to add dependence: gradle: implementation com.fasterxml.jackson.core:jackson-databind:2.13.1 implementation com.fasterxml.jackson.datatype:jackson-datatype-jsr310:2.13.1原生Jackson的使用示例: /*** 原生Jackson的使用示例*/ public class Jacks…...
字节软件测试岗:惨不忍睹的三面,幸好做足了准备,月薪19k,已拿offer
我今年25岁,专业是电子信息工程本科,19年年末的时候去面试,统一投了测试的岗位,软件硬件都有,那时候面试的两家公司都是做培训的,当初没啥钱,他们以面试为谎言再推荐去培训这点让我特别难受。后…...
vue使用axios发送post请求携带json body参数,后端使用@RequestBody进行接收
前言 最近在做自己项目中,做一个非常简单的新增用户场景,但是使用原生axios发送post请求的时候,还是踩了不少坑的。 唉,说多了都是泪,小小一个新增业务,在自己前后端一起开发的时候,硬是搞了好…...
【python百炼成魔】python之列表详解
文章目录一. 列表的概念1.1 列表是什么?1.2 为什么要使用列表?1.3 列表的定义二. 列表的增删改查操作2.1 列表的读取2.2 列表的切片2.3 列表的查询操作2.3.1 not in ,in 表达式2.3.2 列表元素遍历2.4 列表元素的增加操作2.4.1 append()的相关用法2.4.2 e…...
如何学习 Web3
在本文中,我将总结您可以采取的步骤来学习 Web3。从哪儿开始?当我们想要开始新事物时,我们需要一些指导,以免在一开始就卡住。但我们都是不同的,我们有不同的学习方式。这篇文章基于我学习 Web3 的非常个人的经验。路线…...
大数据框架之Hadoop:MapReduce(一)MapReduce概述
1.1MapReduce定义 MapReduce是一个分布式计算框架,用于编写批处理应用程序,是用户开发“基于Hadoop的数据分析应用”的核心框架。 MapReduce核心功能是将用户编写的业务逻辑代码和自带默认组件整合成一个完整的分布式运算程序,并发运行在一…...
一文搞定python语法进阶
前言前面我们已经学习了Python的基础语法,了解了Python的分支结构,也就是选择结构、循环结构以及函数这些具体的框架,还学习了列表、元组、字典、字符串这些Python中特有的数据结构,还用这些语法完成了一个简单的名片管理系统。下…...
2019蓝桥杯真题数列求值(填空题) C语言/C++
题目描述 本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。 给定数列 1,1,1,3,5,9,17,⋯,从第 4 项开始,每项都是前 3 项的和。 求第 20190324 项的最后 4 位数字。 运行限制 最大运行时间:…...
spring中@Autowire和@Resource的区别在哪里?
介绍今天使用Idea写代码的时候,看到之前的项目中显示有warning的提示,去看了下,是如下代码?Autowire private JdbcTemplate jdbcTemplate;提示的警告信息Field injection is not recommended Inspection info: Spring Team recommends: &quo…...
算法训练营DAY54|583. 两个字符串的删除操作、72. 编辑距离
583. 两个字符串的删除操作 - 力扣(LeetCode)https://leetcode.cn/problems/delete-operation-for-two-strings/这道题也是对于编辑距离的铺垫题目,是可以操作两个字符串的删除,使得两个字符串的字符完全相同,这道题可…...
【Ctfshow_Web】信息收集和爆破
0x00 信息收集 web1 直接查看源码 web2 查看不了源码,抓包即可看到(JS拦截了F12) web3 抓包,发送repeater,在响应包中有Flag字段 web4 题目提示后台地址在robots,访问/robots.txt看到Disallow: /fl…...
基于机器学习的推荐算法研究与实现
摘要随着互联网的普及,人们可以通过搜索引擎、社交网络等方式获取大量的信息资源。但是,面对如此之多的信息,人们往往会感到迷失和困惑,无法快速准确地找到自己需要的信息。在这种情况下,推荐算法的出现为我们提供了一…...
(二十四)ATP应用测试平台——springboot集成fastdfs上传与下载功能
前言 本节内容我们主要介绍一下如何在springboot项目中集成fastdfs组件,实现文件的上传与下载。关于fastdfs服务中间键的安装过程,本节内容不做介绍。fastdfs是一个轻量级的分布式文件系统,也是我们文件存储中常常使用的组件之一,…...
linux好用命令+vs快捷键
linux好用命令 功能指令跳转到vim界面的最后一行shift键g复制当前路径下所有文件和目录(加-r才行)到target目录cp -r * /home/target删除指定文件rm -rf test.txt文件重命名(-i交互式提示)mv -i file1 file2移动某个内容…...
Git 构建分布式版本控制系统
版本控制概念Gitlab部署1.版本控制概念 1.1分类 (一)1 本地版本控制系统(传统模式) (二)2 集中化的版本控制系统 CVS、Subversion(SVN) (三)3 分布式…...
铭豹扩展坞 USB转网口 突然无法识别解决方法
当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...
YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...
vue3 字体颜色设置的多种方式
在Vue 3中设置字体颜色可以通过多种方式实现,这取决于你是想在组件内部直接设置,还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法: 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...
【算法训练营Day07】字符串part1
文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接:344. 反转字符串 双指针法,两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...
【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)
🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...
CMake控制VS2022项目文件分组
我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...
稳定币的深度剖析与展望
一、引言 在当今数字化浪潮席卷全球的时代,加密货币作为一种新兴的金融现象,正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而,加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下,稳定…...
Visual Studio Code 扩展
Visual Studio Code 扩展 change-case 大小写转换EmmyLua for VSCode 调试插件Bookmarks 书签 change-case 大小写转换 https://marketplace.visualstudio.com/items?itemNamewmaurer.change-case 选中单词后,命令 changeCase.commands 可预览转换效果 EmmyLua…...
基于stm32F10x 系列微控制器的智能电子琴(附完整项目源码、详细接线及讲解视频)
注:文章末尾网盘链接中自取成品使用演示视频、项目源码、项目文档 所用硬件:STM32F103C8T6、无源蜂鸣器、44矩阵键盘、flash存储模块、OLED显示屏、RGB三色灯、面包板、杜邦线、usb转ttl串口 stm32f103c8t6 面包板 …...
