LeetCode 179 Largest Number 的 Go 题解自定义比较器快排与 ab、ba 拼接比较【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇以 LeetCode-Go 仓库中 179. Largest Number 题解文档 为核心完整讲解给定一组非负整数重排它们使得拼接出的数字最大这一题的解题思路为什么朴素字符串比较会失效、如何用ab与ba的拼接比较构造自定义排序规则并结合 仓库源码 逐行剖析快速排序的分区实现与前导零处理细节最后给出仓库自带的完整测试用例与运行方式。读完后你可以独立复现这道题的 Go 实现并理解自定义比较器在排序类问题中的通用套路。一、题目与示例原题描述摘自 README.md给定一个非负整数列表将它们排列组合成一个最大的数字。示例 1Input: [10,2] Output: 210示例 2Input: [3,30,34,5,9] Output: 9534330注意结果可能非常大因此需要返回字符串而不是整数The result may be very large, so you need to return a string instead of an integer.。这道题的题面非常短但陷阱很典型排序的规则并不是数值大的在前也不是字符串字典序大的在前而是要设计一个面向最终拼接结果的比较规则。二、核心思路为什么不能直接用字符串大小比较很容易想到第一步把数字都转成字符串利用字符串比较来排序这样 9 开头的一定排在最前面。但原文明确指出这样做有一个错误——3 和 30 的比较按字典序30 比 3 大因为第 2 个字符 0 与 3 比较后 30 更长、前缀相同于是排序会把 30 放在 3 前面拼出 303而实际上 3 应该排在 30 前面拼出 330 才是更大的数。原文给出的修正方法是在比较两个字符串大小时不单纯只用字符串顺序进行比较而是加入一个互相拼接的维度aStr : a b bStr : b a通过比较aStr和bStr的大小来得出是 a 大还是 b 大。还是 3 和 30 的例子aStr : 3 30 330 bStr : 30 3 303330 303所以 3 应排在 30 前面。通过互相补齐位数后再比较前缀型数字一个是另一个的前缀如 12 与 128、12 与 121就不会再被字典序误判。从源码结构看这个比较器正是整个解法的关键排序部分没有任何额外的数值转换正确性完全由谁拼在前面更大这一局部规则保证。三、源码逐段解析完整实现位于 179. Largest Number.go共 4 个函数largestNumber、toStringArray、partitionString、quickSortString。3.1 主函数空数组、转字符串、拼接与去零func largestNumber(nums []int) string { if len(nums) 0 { return } numStrs : toStringArray(nums) quickSortString(numStrs, 0, len(numStrs)-1) res : for _, str : range numStrs { if res 0 str 0 { continue } res res str } return res }几个要点空输入返回空串len(nums) 0时直接返回对应测试用例[]int{}→排序后拼接调用quickSortString对字符串数组原地降序排序再顺序拼成结果前导零处理如果数组全是 0如[0, 0]排序后拼出来会是00语义上应返回0。这里的写法是一旦res已经等于0后续遇到的0一律跳过最终把00收敛为0。这个条件res 0 str 0的写法比较精巧——只有当结果当前恰好只剩一个 0 时才去重不影响10这类含零的正常结果。3.2 数字转字符串func toStringArray(nums []int) []string { strs : make([]string, 0) for _, num : range nums { strs append(strs, strconv.Itoa(num)) } return strs }就是标准的strconv.Itoa批量转换为后面按字符串做比较做准备。3.3 关键自定义比较器的快排分区func partitionString(a []string, lo, hi int) int { pivot : a[hi] i : lo - 1 for j : lo; j hi; j { ajStr : a[j] pivot pivotStr : pivot a[j] if ajStr pivotStr { // 这里的判断条件是关键 i a[j], a[i] a[i], a[j] } } a[i1], a[hi] a[hi], a[i1] return i 1 }这是标准 Lomuto 方案的快速排序分区唯一不同之处在判断条件取a[hi]作为基准pivot对每个a[j]不直接比较a[j]与pivot而是比较a[j] pivot与pivot a[j]这两个拼接串——即把 a[j] 放在 pivot 前面和把 pivot 放在 a[j] 前面哪个拼出来更大若前者更大则a[j]属于应排在 pivot 之前的分区执行i并交换。源码注释也直接标注了这一点// 这里的判断条件是关键。3.4 递归排序入口func quickSortString(a []string, lo, hi int) { if lo hi { return } p : partitionString(a, lo, hi) quickSortString(a, lo, p-1) quickSortString(a, p1, hi) }quickSortString(numStrs, 0, len(numStrs)-1)从整个区间开始递归。从源码结构看这里的快排选取最后一个元素作为 pivot 且没有随机化属于最直接的教科书实现在 LeetCode 本题的数据规模下没有问题但要意识到这是未经优化的快排形态。排序完成后再回到largestNumber主函数做拼接整个流程就是转字符串 → 自定义比较器快排 → 拼接去零。四、为什么这个比较规则对整道题成立ab ba定义的是谁应该排在谁前面。原理解释是拼接出的最终数字其大小由每一位决定比较两个相邻元素的先后顺序时只要保证任意相邻一对都满足更优的相对顺序整体拼接结果就是最大的。而ab与ba的比较恰好就是针对相邻拼接的最优判定——它把两者谁靠前这一局部决策问题转化成了两个等长字符串的字典序比较天然绕开了字符串长短不一时字典序失效的问题这正是 30 与 3 这类前缀陷阱的根源。仓库测试用例 179. Largest Number_test.go 中的多组数据也印证了这一点尤其是两组典型的前缀型用例输入输出验证点[3, 6, 9, 1]9631基本降序场景[1]1单元素边界[]空数组边界[2, 10]210数字 2 开头优先于 10 字典序[3, 30, 34, 5, 9]9534330原题示例含 3 vs 30 前缀陷阱[12, 128]1281212 是 128 的前缀128 应排前[12, 121]1212112 与 121 互相拼接后 12112 12121121 应排前[0, 0]0全零去重收敛为单个 0[1440, 7548, 4240, 6616, 733, 4712, 883, 8, 9576]9576888375487336616471242401440混合长度、多前缀关系的综合用例[12, 121]这组尤其值得注意按字典序 121 12恰好结论也对但理由不同——真正生效的是拼接比较 12112 12121。可以推断这类用例正是为了排除恰好靠字典序蒙对的实现而设计的。五、如何运行与验证仓库根目录的 go.mod 声明了 Go 1.19 模块环境。本题目录下的测试文件采用打印输入输出对照的方式组织Test_Problem179遍历全部用例并调用largestNumber打印实际结果与上方表格中的期望值逐一比对即可人工核验。在仓库根目录运行本题的测试go test -v ./leetcode/0179.Largest-Number/也可以运行仓库自带的 gotest.sh 对全部题解做带覆盖率的回归bash gotest.sh该脚本执行go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...一次性产出单一合法的覆盖率文件脚本注释中说明了这是为避免多包分次生成 profile 导致的格式问题。六、小结回到 题解文档 的原始脉络本仓库 179 题的完整解法可以浓缩为三步转字符串用strconv.Itoa把[]int映射为[]string为自定义比较做准备自定义比较器排序以ab与ba的字典序判定两元素先后配合 Lomuto 分区快排原地降序排序拼接与去零顺序拼接结果用res 0 str 0的条件把全零输入收敛为0。这一拼接比较器的模式不局限于本题凡是重排元素使拼接结果最优的题型如按特定顺序最大化/最小化拼接串都可以复用同样的比较器设计思路而 源码实现 与 测试用例 中的前缀型数据12/128、12/121则是检验比较器正确性的最佳判例。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 179 Largest Number 的 Go 题解：自定义比较器快排与 a+b、b+a 拼接比较
LeetCode 179 Largest Number 的 Go 题解自定义比较器快排与 ab、ba 拼接比较【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇以 LeetCode-Go 仓库中 179. Largest Number 题解文档 为核心完整讲解给定一组非负整数重排它们使得拼接出的数字最大这一题的解题思路为什么朴素字符串比较会失效、如何用ab与ba的拼接比较构造自定义排序规则并结合 仓库源码 逐行剖析快速排序的分区实现与前导零处理细节最后给出仓库自带的完整测试用例与运行方式。读完后你可以独立复现这道题的 Go 实现并理解自定义比较器在排序类问题中的通用套路。一、题目与示例原题描述摘自 README.md给定一个非负整数列表将它们排列组合成一个最大的数字。示例 1Input: [10,2] Output: 210示例 2Input: [3,30,34,5,9] Output: 9534330注意结果可能非常大因此需要返回字符串而不是整数The result may be very large, so you need to return a string instead of an integer.。这道题的题面非常短但陷阱很典型排序的规则并不是数值大的在前也不是字符串字典序大的在前而是要设计一个面向最终拼接结果的比较规则。二、核心思路为什么不能直接用字符串大小比较很容易想到第一步把数字都转成字符串利用字符串比较来排序这样 9 开头的一定排在最前面。但原文明确指出这样做有一个错误——3 和 30 的比较按字典序30 比 3 大因为第 2 个字符 0 与 3 比较后 30 更长、前缀相同于是排序会把 30 放在 3 前面拼出 303而实际上 3 应该排在 30 前面拼出 330 才是更大的数。原文给出的修正方法是在比较两个字符串大小时不单纯只用字符串顺序进行比较而是加入一个互相拼接的维度aStr : a b bStr : b a通过比较aStr和bStr的大小来得出是 a 大还是 b 大。还是 3 和 30 的例子aStr : 3 30 330 bStr : 30 3 303330 303所以 3 应排在 30 前面。通过互相补齐位数后再比较前缀型数字一个是另一个的前缀如 12 与 128、12 与 121就不会再被字典序误判。从源码结构看这个比较器正是整个解法的关键排序部分没有任何额外的数值转换正确性完全由谁拼在前面更大这一局部规则保证。三、源码逐段解析完整实现位于 179. Largest Number.go共 4 个函数largestNumber、toStringArray、partitionString、quickSortString。3.1 主函数空数组、转字符串、拼接与去零func largestNumber(nums []int) string { if len(nums) 0 { return } numStrs : toStringArray(nums) quickSortString(numStrs, 0, len(numStrs)-1) res : for _, str : range numStrs { if res 0 str 0 { continue } res res str } return res }几个要点空输入返回空串len(nums) 0时直接返回对应测试用例[]int{}→排序后拼接调用quickSortString对字符串数组原地降序排序再顺序拼成结果前导零处理如果数组全是 0如[0, 0]排序后拼出来会是00语义上应返回0。这里的写法是一旦res已经等于0后续遇到的0一律跳过最终把00收敛为0。这个条件res 0 str 0的写法比较精巧——只有当结果当前恰好只剩一个 0 时才去重不影响10这类含零的正常结果。3.2 数字转字符串func toStringArray(nums []int) []string { strs : make([]string, 0) for _, num : range nums { strs append(strs, strconv.Itoa(num)) } return strs }就是标准的strconv.Itoa批量转换为后面按字符串做比较做准备。3.3 关键自定义比较器的快排分区func partitionString(a []string, lo, hi int) int { pivot : a[hi] i : lo - 1 for j : lo; j hi; j { ajStr : a[j] pivot pivotStr : pivot a[j] if ajStr pivotStr { // 这里的判断条件是关键 i a[j], a[i] a[i], a[j] } } a[i1], a[hi] a[hi], a[i1] return i 1 }这是标准 Lomuto 方案的快速排序分区唯一不同之处在判断条件取a[hi]作为基准pivot对每个a[j]不直接比较a[j]与pivot而是比较a[j] pivot与pivot a[j]这两个拼接串——即把 a[j] 放在 pivot 前面和把 pivot 放在 a[j] 前面哪个拼出来更大若前者更大则a[j]属于应排在 pivot 之前的分区执行i并交换。源码注释也直接标注了这一点// 这里的判断条件是关键。3.4 递归排序入口func quickSortString(a []string, lo, hi int) { if lo hi { return } p : partitionString(a, lo, hi) quickSortString(a, lo, p-1) quickSortString(a, p1, hi) }quickSortString(numStrs, 0, len(numStrs)-1)从整个区间开始递归。从源码结构看这里的快排选取最后一个元素作为 pivot 且没有随机化属于最直接的教科书实现在 LeetCode 本题的数据规模下没有问题但要意识到这是未经优化的快排形态。排序完成后再回到largestNumber主函数做拼接整个流程就是转字符串 → 自定义比较器快排 → 拼接去零。四、为什么这个比较规则对整道题成立ab ba定义的是谁应该排在谁前面。原理解释是拼接出的最终数字其大小由每一位决定比较两个相邻元素的先后顺序时只要保证任意相邻一对都满足更优的相对顺序整体拼接结果就是最大的。而ab与ba的比较恰好就是针对相邻拼接的最优判定——它把两者谁靠前这一局部决策问题转化成了两个等长字符串的字典序比较天然绕开了字符串长短不一时字典序失效的问题这正是 30 与 3 这类前缀陷阱的根源。仓库测试用例 179. Largest Number_test.go 中的多组数据也印证了这一点尤其是两组典型的前缀型用例输入输出验证点[3, 6, 9, 1]9631基本降序场景[1]1单元素边界[]空数组边界[2, 10]210数字 2 开头优先于 10 字典序[3, 30, 34, 5, 9]9534330原题示例含 3 vs 30 前缀陷阱[12, 128]1281212 是 128 的前缀128 应排前[12, 121]1212112 与 121 互相拼接后 12112 12121121 应排前[0, 0]0全零去重收敛为单个 0[1440, 7548, 4240, 6616, 733, 4712, 883, 8, 9576]9576888375487336616471242401440混合长度、多前缀关系的综合用例[12, 121]这组尤其值得注意按字典序 121 12恰好结论也对但理由不同——真正生效的是拼接比较 12112 12121。可以推断这类用例正是为了排除恰好靠字典序蒙对的实现而设计的。五、如何运行与验证仓库根目录的 go.mod 声明了 Go 1.19 模块环境。本题目录下的测试文件采用打印输入输出对照的方式组织Test_Problem179遍历全部用例并调用largestNumber打印实际结果与上方表格中的期望值逐一比对即可人工核验。在仓库根目录运行本题的测试go test -v ./leetcode/0179.Largest-Number/也可以运行仓库自带的 gotest.sh 对全部题解做带覆盖率的回归bash gotest.sh该脚本执行go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...一次性产出单一合法的覆盖率文件脚本注释中说明了这是为避免多包分次生成 profile 导致的格式问题。六、小结回到 题解文档 的原始脉络本仓库 179 题的完整解法可以浓缩为三步转字符串用strconv.Itoa把[]int映射为[]string为自定义比较做准备自定义比较器排序以ab与ba的字典序判定两元素先后配合 Lomuto 分区快排原地降序排序拼接与去零顺序拼接结果用res 0 str 0的条件把全零输入收敛为0。这一拼接比较器的模式不局限于本题凡是重排元素使拼接结果最优的题型如按特定顺序最大化/最小化拼接串都可以复用同样的比较器设计思路而 源码实现 与 测试用例 中的前缀型数据12/128、12/121则是检验比较器正确性的最佳判例。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考