组成最大数 - 华为OD统一考试(E卷)
2024华为OD机试（C卷+D卷）最新题库【超值优惠】Java/Python/C++合集
题目描述
小组中每位都有一张卡片，卡片上是6位以内的正整数。将卡片连起来可以组成多种数字，计算组成的最大数字。
输入描述
,号分割的多个正整数字符串，不需要考虑非数字字符情况，小组最多25个人。
输出描述
最大的数字字符串
示例1
输入：
22,221
输出：
22221
说明：
将22和221组合成最大值的排列是22221。
示例2
输入：
4589,101,41425,9999
输出：
9999458941425101
说明：
将4589, 101, 41425, 9999组合成最大值的排列是9999458941425101。
题解
题目类型
这道题属于贪心算法类型的题目。题目的核心在于：如何通过将多个数字组合成一个字符串来形成尽可能大的数字。要做到这一点，需要通过贪心的思想，在每一步选择两个数字组合时，确保它们的拼接顺序能带来全局最优解。
解题思路
- 字符串比较：首先，我们要确定如何将数字拼接在一起才能得到最大的数字。对于两个数字
a和b，我们可以比较a + b和b + a的结果。如果a + b大于b + a，那么a应该排在b前面，反之亦然。- 排序：基于以上的比较规则，我们可以将输入的数字转换为字符串，然后按照上述规则对字符串数组进行排序。排序后的结果，拼接起来就是能形成的最大数字
代码大致描述
Java: 使用
Arrays.sort()方法自定义排序规则，利用compareTo比较字符串拼接后的字典序。最后将排好序的字符串数组拼接为最终结果。Python: 使用
sorted()函数，并结合cmp_to_key进行自定义比较。自定义比较函数类似于 Java 中的compareTo，比较两个数字拼接后的大小。C++: 使用
sort()函数和自定义比较函数compare，对字符串进行排序。排序后通过拼接得到最大的数字。时间复杂度
排序是此问题的核心部分，排序的时间复杂度主要取决于比较函数的执行次数。假设输入有
n个字符串，每个字符串的平均长度为k：
- 比较操作的时间复杂度：比较两个字符串的时间复杂度为
O(k)，因为我们需要比较拼接后的两个字符串。- 排序的时间复杂度：排序的总体复杂度是
O(n log n)，因此总体时间复杂度为O(n k log n)。空间复杂度
空间复杂度主要取决于存储中间结果的字符串数组：
额外存储空间：我们需要存储排序后的数组，因此空间复杂度为
O(n)，加上用于存储拼接结果的O(n * k)，总的空间复杂度为O(n k)。总结
这道题属于经典的贪心算法题目，重点在于如何正确自定义字符串拼接的排序规则。通过对数字进行排序，并将排序结果拼接成字符串，可以得到最大可能的数字。
Java
import java.util.Arrays;
import java.util.Scanner;
/**
* @author code5bug
*/
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String[] nums = in.nextLine().split(",");
// 排序规则，两个字符串拼接后比较大小，降序排列
Arrays.sort(nums, (a, b) -> (b + a).compareTo(a + b));
StringBuilder result = new StringBuilder();
for (String num : nums) result.append(num);
System.out.println(result.toString());
}
}
Python
from functools import cmp_to_key
def solve(nums):
# 自定义比较函数，决定字符串的拼接顺序
def compare(a, b):
if a + b > b + a:
return -1
elif a + b < b + a:
return 1
else:
return 0
# 将数字转换为字符串后排序
nums = sorted(nums, key=cmp_to_key(compare))
# 拼接排序后的数字
result = ''.join(nums)
if __name__ == '__main__':
nums = input().split(",")
print(solve(nums))
代码说明：
自定义比较函数
compare：用于比较两字符串拼接后的结果，a + b和b + a比较，确保按照最大的字典序排列。排序：使用
sorted函数，结合cmp_to_key将自定义的比较规则应用于字符串排序。拼接结果：使用
''.join(nums)将排序好的字符串数组拼接成最终结果。处理全为0的情况：如果拼接结果以
'0'开头（如输入全为0），则直接返回'0'。cmp_to_key 详细解释：
cmp_to_key是 Python 中functools模块的一个函数，它的作用是将一个老式的比较函数（基于比较两个元素的结果返回 -1、0、1）转换为适合 Python 的key函数。这是因为 Python 3 中的排序函数（如sorted和sort）已经从直接使用比较函数切换为使用key函数进行排序。在 Python 2 中，排序函数（如
sorted()）直接使用比较函数，它通过传入两个参数并返回 -1、0、1 来决定元素的顺序：
- 返回负数：表示第一个元素应排在第二个之前。
- 返回0：表示两个元素相等。
- 返回正数：表示第一个元素应排在第二个之后。
然而，在 Python 3 中，排序算法不再直接支持比较函数，而是通过
key函数来替代。key函数接收一个单独的元素并返回一个可以比较的值。为了保持兼容性，cmp_to_key就是用来将旧的比较函数（cmp函数）转换为新的key函数。
C++
#include <bits/stdc++.h>
using namespace std;
// 自定义比较函数，通过比较两个字符串 a + b 和 b + a 的结果，决定排序顺序。
bool cmp(const string& a, const string& b)
{
return (a + b) > (b + a);
}
int main()
{
vector<string> nums;
string line;
cin >> line;
// 分割字符串
string num;
for (char ch : line) {
if (ch == ',') {
nums.push_back(num);
num.clear();
} else {
num += ch;
}
}
nums.push_back(num);
// 排序数组，使用自定义比较函数
sort(nums.begin(), nums.end(), cmp);
// 拼接排序后的数字
string result;
for (const string& s : nums) {
result += s;
}
cout << result << endl;
return 0;
}
#面经##华为od##华为od题库##华为od机试##华为OD机试算法题库#整理题解不易， 如果有帮助到您，请给点个赞 ❤️ 和收藏 ⭐，让更多的人看到。🙏🙏🙏
有被激励到
