Go&java算法之最大数示例详解

2024-12-12 16:43:14

最大数

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。

注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

示例 1：

输入：nums = [10,2]

输出："210"

示例 2：

输入：nums = [3,30,34,5,9]

输出："9534330"

提示：

1 <= nums.length <= 100

0 <= nums[i] <= 109

方法一：排序（java）

要想组成最大的整数，一种直观的想法是把数值大的数放在高位。

于是我们可以比较输入数组的每个元素的最高位，最高位相同的时候比较次高位

以此类推，完成排序，然后把它们拼接起来。这种排序方式对于输入数组没有相同数字开头的时候是有效的

class Solution {
    public String largestNumber(int[] nums) {
        int n = nums.length;
        // 转换成包装类型，以便传入 Comparator 对象（此处为 lambda 表达式）
        Integer[] numsArr = new Integer[n];
        for (int i = 0; i &lt; n; i++) {
            numsArr[i] = nums[i];
        }
        Arrays.sort(numsArr, (x, y) -&gt; {
            long sx = 10, sy = 10;
            while (sx &lt;= x) {
                sx *= 10;
            }
            while (sy &lt;= y) {
                sy *= 10;
            }
            return (int) (-sy * x - y + sx * y + x);
        });
        if (numsArr[0] == 0) {
            return "0";
        }
        StringBuilder ret = new StringBuilder();
        for (int num : numsArr) {
            ret.append(num);
        }
        return ret.toString();
    }
}

时间复杂度：O(nlognlogm)

空间复杂度：O(logn)

方法一：排序（go）

具体的方法思路已经在上文中表述，详情请看上文内容。

1.核心为插入排序

2.比大小的函数，相加的两种string结果，然后比较各位大小。

3.将排序的结果累加

func largestNumber(nums []int) string {
    sort.Slice(nums, func(i, j int) bool {
        x, y := nums[i], nums[j]
        sx, sy := 10, 10
        for sx &lt;= x {
            sx *= 10
        }
        for sy &lt;= y {
            sy *= 10
        }
        return sy*x+y &gt; sx*y+x
    })
    if nums[0] == 0 {
        return "0"
    }
    ans := []byte{}
    for _, x := range nums {
        ans = append(ans, strconv.Itoa(x)...)
    }
    return string(ans)
}

时间复杂度：O(nlognlogm)

空间复杂度：O(logn)

以上就是Go&java算法之最大数示例详解的详细内容，更多关于Go java算法最大数的资料请关注我们其它相关文章！

Go Java算法之比较版本号方法详解

目录比较版本号方法一:字符串切割(Java) 方法二:双指针(Go) 比较版本号给你两个版本号 version1 和 version2 ,请你比较它们. 版本号由一个或多个修订号组成,各修订号由一个 '.' 连接.每个修订号由多位数字组成,可能包含前导零 .每个版本号至少包含一个字符. 修订号从左到右编号,下标从 0 开始,最左边的修订号下标为 0 ,下一个修订号下标为 1 ,以此类推.例如,2.5.33 和 0.1 都是有效的版本号. 比较版本号时,请按从左到右的顺序依次比较它们的
Go Java算法之外观数列实现方法示例详解

目录外观数列方法一:遍历生成(Java) 方法二:递归(Go) 外观数列给定一个正整数 n ,输出外观数列的第 n 项. 「外观数列」是一个整数序列,从数字 1 开始,序列中的每一项都是对前一项的描述. 你可以将其视作是由递归公式定义的数字字符串序列: countAndSay(1) = "1" countAndSay(n) 是对 countAndSay(n-1) 的描述,然后转换成另一个数字字符串. 前五项如下: 1.1 —— 第一项是数字 1 2.11 —— 描述前一项,这个数
Go和Java算法详析之分数到小数

目录分数到小数方法一:模拟竖式计算(Java) 方法一:模拟竖式计算(Go) 总结分数到小数给定两个整数,分别表示分数的分子 numerator 和分母 denominator,以字符串形式返回小数 . 如果小数部分为循环小数,则将循环的部分括在括号内. 如果存在多个答案,只需返回任意一个 . 对于所有给定的输入,保证答案字符串的长度小于 104 . 示例 1: 输入:numerator = 1, denominator = 2 输出:"0.5" 示例 2: 输入:num
Go Java算法之交错字符串示例详解

目录交错字符串方法一:动态规划(Java) 方法一:动态规划(GO) 交错字符串给定三个字符串 s1.s2.s3,请你帮忙验证 s3 是否是由 s1 和 s2 交错组成的. 两个字符串 s 和 t 交错的定义与过程如下,其中每个字符串都会被分割成若干非空子字符串: s = s1 + s2 + ... + sn t = t1 + t2 + ... + tm |n - m| <= 1 交错是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 +
Go Java算法重复的DNA序列详解

目录重复的DNA序列方法一:哈希表(Java) 方法二:哈希表——优化(Go) 方法思路: 重复的DNA序列 DNA序列由一系列核苷酸组成,缩写为 'A', 'C', 'G' 和 'T'.. 例如,"ACGAATTCCG" 是一个 DNA序列 . 在研究 DNA 时,识别 DNA 中的重复序列非常有用. 给定一个表示 DNA序列的字符串 s ,返回所有在 DNA 分子中出现不止一次的长度为 10 的序列(子字符串).你可以按任意顺序返回答案. 示例 1: 输入:s = &
Go Java算法之从英文中重建数字示例详解

目录从英文中重建数字 Java实现 Go实现从英文中重建数字给你一个字符串 s ,其中包含字母顺序打乱的用英文单词表示的若干数字(0-9).按升序返回原始的数字. 示例 1: 输入:s = "owoztneoer" 输出:"012" 示例 2: 输入:s = "fviefuro" 输出:"45" 提示: 1 <= s.length <= 105 s[i] 为 ["e","g&
Go&java算法之最大数示例详解

目录最大数方法一:排序(java) 方法一:排序(go) 最大数给定一组非负整数 nums,重新排列每个数的顺序(每个数不可拆分)使之组成一个最大的整数. 注意:输出结果可能非常大,所以你需要返回一个字符串而不是整数. 示例 1: 输入:nums = [10,2] 输出:"210" 示例 2: 输入:nums = [3,30,34,5,9] 输出:"9534330" 提示: 1 <= nums.length <= 100 0 <= nums[
java数据结构算法稀疏数组示例详解

目录一.什么是稀疏数组二.场景用法 1.二维数组转稀疏数组思路 2.稀疏数组转二维数组思路 3.代码实现一.什么是稀疏数组当一个数组a中大部分元素为0,或者为同一个值,那么可以用稀疏数组b来保存数组a. 首先,稀疏数组是一个数组,然后以一种特定的方式来保存上述的数组a,具体处理方法: 记录数组a一共有几行几列记录a中有多少个不同的值最后记录不同值的元素所在行列,以及具体的值,放在一个小规模的数组里,以缩小程序的规模. 这个小规模的数组,就是稀疏数组. 举个栗子,左侧是一个二维数组,一
Java实现无向图的示例详解

目录基本概念图的定义无向图的定义无向图的 API 无向图的实现方式邻接矩阵边的数组邻接表数组无向图的遍历深度优先搜索广度优先搜索后记基本概念图的定义一个图是由点集V={vi} 和 VV 中元素的无序对的一个集合E={ek} 所构成的二元组,记为G=(V,E),V中的元素vi叫做顶点,E中的元素 ek叫做边. 对于V中的两个点 u,v,如果边(u,v) 属于E,则称 u,v两点相邻,u,v称为边(u,v)的端点. 我们可以用m(G)=|E| 表示图G中的边数,用n(G)
java 算法之冒泡排序实例详解

java 算法之冒泡排序实例详解无人不知无人不晓的冒泡排序,据说是模仿泡泡从水中浮起跑到水面的过程. 在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒.即: 每当两相邻的数比较后发现它们的排序与排序要求相反时,就将它们互换. 来看一下代码: package cn.songxinqiang.study.algorithm.sort; import java.util.Arrays; /** * 冒泡排序 * * <p>
Java反射框架Reflections示例详解

MAVEN 坐标 <dependency> <groupId>org.reflections</groupId> <artifactId>reflections</artifactId> <version>0.9.10</version> </dependency> Reflections 的作用 Reflections通过扫描classpath,索引元数据,并且允许在运行时查询这些元数据. 获取某个类型的所有
C语言编程题杨氏矩阵算法快速上手示例详解

目录题目概要一.解题思路二.具体代码题目概要有一个数字矩阵,矩阵的每行从左到右都是递增的,矩阵从上到下都是递增的,请编写程序在这样的矩阵中查找某个数字是否存在? 一.解题思路对于查找一个数组中元素是否存在,很多同学第一想法就是从头到尾遍历一遍.这样的想法优点是代码简单且无脑容易上手,但是这样的缺点也很明显,比如是m *n的数组,你从头到尾遍历,最坏情况要找m *n次.题目给的相关条件比如从左向右递增,从上向下递增你也完全没有使用,这样的暴力求解显然不是我们想看到的我们来介绍一种方法
Java设计模式之单例模式示例详解

目录 0.概述 1.饿汉式 1.1 饿汉式单例实现 1.2 破坏单例的几种情况 1.3 预防单例的破坏 2.枚举饿汉式 2.1 枚举单例实现 2.2 破坏单例 3.懒汉式 4.双检锁懒汉式 5.内部类懒汉式 6.JDK中单例的体现 0.概述为什么要使用单例模式? 在我们的系统中,有一些对象其实我们只需要一个,比如说:线程池.缓存.对话框.注册表.日志对象.充当打印机.显卡等设备驱动程序的对象.事实上,这一类对象只能有一个实例,如果制造出多个实例就可能会导致一些问题的产生,比如:程序的行为异常.
java基础之注解示例详解

目录定义作用注解与注释的区别 JDK内置的标准注解自定义注解 @Target 属性定义注解也叫原数据,它是JDK1.5及之后版本引入的一个特性,它可以声明在类.方法.变量等前面,用来对这些元素进行说明. 作用生成文档:通过代码里标识的注解生成doc文档[生成doc文档] 代码分析:通过代码里标识的注解对代码进行分析[反射] 编译检查:通过代码里标识的注解让编译器能够实现基本的编译检查[Override] 注解与注释的区别注解是给编译器看的,注释是给程序员看的. JDK内置的标准注
Java代理模式的示例详解

目录定义案例需求方案:静态代理模式总结定义代理模式(Proxy Parttern) 为一个对象提供一个替身,来控制这个对象的访问,即通过代理对象来访问目标对象,这样做的话好处是可以在目标对象实现的基础上,进行额外的功能的扩展. 案例需求苹果公司通过苹果代理商来卖手机方案:静态代理模式定义抽象接口类,该类在代理模式中扮演的是一个抽象功能的角色,该案例中就是把出售手机抽象为了一个接口 /** * 售卖手机的接口(代理模式--抽象角色) * @author:liyajie * @
Java动态代理的示例详解

目录定义分类案例需求方案一:jdk动态代理方案二:cglib动态代理分析总结定义动态代理指的是,代理类和目标类的关系在程序运行的时候确定的,客户通过代理类来调用目标对象的方法,是在程序运行时根据需要动态的创建目标类的代理对象. 分类 jdk动态代理 cglib动态代理案例需求苹果公司通过苹果代理商来卖手机方案一:jdk动态代理定义抽象接口 /** * 售卖手机的接口(代理模式--抽象角色) * @author:liyajie * @createTime:2022/2

Go&java算法之最大数示例详解

目录

最大数

方法一：排序（java）

方法一：排序（go）

相关推荐

随机推荐