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

(每日一题) 力扣 179 最大数

文章目录

      • 🎯 LeetCode 179 最大数:最优解法详解(C++实现)
        • 📋 问题描述
        • 💡 核心思路
        • 🚀 完整代码实现
        • 🔍 分步解析
          • 1. 全零检测
          • 2. 字符串转换
          • 3. 自定义排序规则
          • 4. 拼接结果
          • 5. 处理前导零
        • 📊 示例验证
        • ⏱️ 复杂度分析
        • 🚀 优化总结

在这里插入图片描述

🎯 LeetCode 179 最大数:最优解法详解(C++实现)

在这里插入图片描述

📋 问题描述

给定一组非负整数 nums,重新排列每个数的顺序,使其组成一个最大的整数。例如,输入 [3, 30, 34, 5, 9],输出应为 "9534330"。由于结果可能非常大,需返回字符串而非整数。


💡 核心思路

贪心策略:通过自定义排序规则,确保每两个数字的拼接结果局部最优,从而得到全局最大值。
关键步骤

  1. 🔍 全零检测:若输入全为 0,直接返回 "0"
  2. 🔄 字符串转换:将每个数字转为字符串,避免大数拼接时的溢出问题。
  3. 📊 自定义排序:按 a+b > b+a 的字典序降序排列。
  4. 🧩 拼接结果:直接拼接排序后的字符串。
  5. ⚠️ 处理前导零:仅在结果全零时返回 "0"

🚀 完整代码实现
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        // 1. 🔍 全零检测
        if (all_of(nums.begin(), nums.end(), [](int x) { return x == 0; })) {
            return "0";
        }
        
        // 2. 🔄 转换为字符串数组
        vector<string> strs;
        for (int num : nums) {
            strs.push_back(to_string(num));
        }
        
        // 3. 📊 自定义排序:a+b > b+a
        sort(strs.begin(), strs.end(), [](const string& a, const string& b) {
            return a + b > b + a;
        });
        
        // 4. 🧩 拼接结果
        string result;
        for (const string& s : strs) {
            result += s;
        }
        
        // 5. ⚠️ 处理前导零
        size_t start = 0;
        while (start < result.size() && result[start] == '0') start++;
        return (start == result.size()) ? "0" : result.substr(start);
    }
};

🔍 分步解析
1. 全零检测
if (all_of(nums.begin(), nums.end(), [](int x) { return x == 0; })) {
    return "0";
}
  • 作用:若输入全为 0(例如 [0, 0, 0]),直接返回 "0"✅,避免后续无效操作。
  • 复杂度:⏱️ 时间复杂度 O(n),🗃️ 空间复杂度 O(1)
2. 字符串转换
vector<string> strs;
for (int num : nums) {
    strs.push_back(to_string(num));
}
  • 优化点:提前转换所有数字为字符串,避免排序时重复调用 to_string🚀。
  • 复杂度:⏱️ O(n),🗃️ O(n)
3. 自定义排序规则
sort(strs.begin(), strs.end(), [](const string& a, const string& b) {
    return a + b > b + a;
});
  • 核心逻辑:比较两种拼接方式 a+bb+a 的字典序。
    • 示例:比较 "3""30""330" > "303",因此 "3" 排在 "30" 前👉。
  • 复杂度:⏱️ 排序 O(n log n),字符串比较 O(k)k 为字符串平均长度)。
4. 拼接结果
string result;
for (const string& s : strs) {
    result += s;
}
  • 复杂度:⏱️ O(nk),🗃️ O(nk)k 为字符串平均长度)。
5. 处理前导零
size_t start = 0;
while (start < result.size() && result[start] == '0') start++;
return (start == result.size()) ? "0" : result.substr(start);
  • 作用:跳过前导零,若结果全零则返回 "0"✅。
  • 优化点:无需反转字符串,直接遍历一次即可🚀。

📊 示例验证
输入输出说明
[10, 2]"210"正确排序 "10""2"
[3, 30, 34, 5, 9]"9534330"正确处理多位数拼接顺序
[0, 0, 0]"0"全零检测正确触发
[0, 1, 0]"100"前导零处理正确

⏱️ 复杂度分析
步骤时间复杂度空间复杂度
全零检测O(n)O(1)
字符串转换O(n)O(n)
自定义排序O(n log n)O(log n)
拼接结果O(nk)O(nk)
处理前导零O(n)O(1)
总计O(nk log n)O(nk)

Yes
No
Yes
No
Start
All zeros?
Return 0
Convert to strings
Sort by a+b > b+a
Concatenate
Leading zeros?
Trim leading zeros
Keep result
Output
🚀 优化总结
  1. 避免冗余操作:直接遍历处理前导零,而非反转字符串✅。
  2. 减少重复转换:提前将数字转为字符串数组,节省排序时间🚀。
  3. 贪心策略正确性:通过字典序比较保证局部最优解即为全局最优💡。

原文地址:https://blog.csdn.net/qq_46538985/article/details/146244983
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/584453.html

相关文章:

  • 前端面试:如何实现预览 PDF 文件?
  • 基于深度学习的肺炎X光影像自动诊断系统实现,真实操作案例分享,值得学习!
  • 【文献阅读】SPRec:用自我博弈打破大语言模型推荐的“同质化”困境
  • 电子电气架构 --- 智能电动汽车概述
  • 塔能IVO-SCY智能机箱:点亮智慧城市的电力“智慧核芯”
  • python语言写的一款pdf转word、word转pdf的免费工具
  • 微店关键词搜索接口(micro.item_search)返回数据测试指南
  • Spring 注解解析
  • java: system类
  • 高效集成聚水潭采购退货数据到MySQL的最佳实践
  • PHP批量去除Bom头的方法
  • JVM崩溃时产生的文件 hs_err.pid.log
  • 【实战ES】实战 Elasticsearch:快速上手与深度实践-8.2.1AWS OpenSearch无服务器方案
  • 3D匹配算法简述
  • Stable Diffusion F.1模型全面解析
  • 【MyBatis Plus 逻辑删除详解】
  • YOLOv8模型改进 第三十二讲 添加Transformer Self Attention TSA 解决CNN过程中特征丢失的问题
  • 问deepseek: OpenFOAM并行分区后,是如何实现ldumatrix矩阵向量乘法计算逻辑的?
  • 基于PyTorch的深度学习4——使用numpy实现机器学习vs使用Tensor及Antograd实现机器学习
  • LuaJIT 学习(2)—— 使用 FFI 库的几个例子