LeetCode-Go 题解精讲1689. 拆分最少数量的十-二进制数Deci-Binary Numbers【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇围绕 LeetCode-Go 仓库中第 1689 题「拆分最少数量的十-二进制数」的题解文档展开先完整还原题目定义、示例与约束再从数位角度给出答案即字符串中的最大数字的数学论证最后结合仓库中的 Go 实现源码与配套测试说明这一 O(n) 线性扫描解法如何落地、如何验证。读完后你将掌握这道题的完整证明思路、Go 实现的细节取舍以及在本仓库中运行该题测试与覆盖率检查的方法。一、题目描述什么是十-二进制数deci-binary原始题目见 题目文档的英文定义如下A decimal number is calleddeci-binaryif each of its digits is either0or1without any leading zeros. For example,101and1100aredeci-binary, while112and3001are not.Given a stringnthat represents a positive decimal integer, returntheminimumnumber of positivedeci-binarynumbers needed so that they sum up ton*.中文大意继承自原文档的题目大意小节如果一个十进制数字不含任何前导零且每一位上的数字不是 0 就是 1那么该数字就是一个十-二进制数。例如101和1100都是十-二进制数而112和3001不是。给定一个表示正整数的十进制字符串n返回使若干正十-二进制数之和恰好等于n所需的最少数目。原文档给出了三个示例完整保留如下示例 1Input: n 32 Output: 3 Explanation: 10 11 11 32示例 2Input: n 82734 Output: 8示例 3Input: n 27346209830709182346 Output: 9约束条件同样完整继承1 n.length 10^5n只由数字字符组成n不含前导零且表示一个正整数从约束可以看到n的长度上限达到 10 万位远超任何内置整数的表示范围——这也是题目要求以字符串而非整数作为入参的原因解法必须做到逐字符处理而不是把n解析成数值后再运算。二、核心洞察答案就是n中的最大数字原文档解题思路小节指出这题想通之后代码就 3 行。其论证可以拆解为下界证明与可达性构造两部分这里完整展开。下界为什么不能少于最大数字设n的某一位上数字为d例如n 82734的千位是 8。任何一个十-二进制数在该位上的取值只能是0或1且没有借位或进位跨数累加的机制——k 个十-二进制数相加时某一位的和最多只比 k 多出进位贡献但为了在该位最终得到d这 k 个数在该位至少要贡献出d个 1进位只会帮助低位不会凭空让高位数字减少所需加数个数。因此加数个数k必须满足k d。对所有数位取最大值得到最少数目 max(n 的每一位数字)以示例 1 为例32的最大数字是 3所以答案至少为 310 11 11 32恰好 3 个验证了取等成立。可达性为什么最大数字就一定够取k maxDigit。对n的每一位若该位数字为d就让这k个数中任意d个在该位取 1、其余k - d个在该位取 0。由于每一位上取 1 的个数恰好等于该位数字d逐位相加含正常十进制进位必然还原出n本身且每个构造出的数都不含前导零问题千位上若d 1取 1 的那个数自然以 1 开头若最高位d 0这与n 不含前导零的约束矛盾故最高位d 1。原文档用n 23423723举例这是一个 8 位数最大数字是 7所以至少需要 7 个数累加得到n这 7 个数的千位都为 1其他数位按需求取 0 和 1——例如万位是 2就让 7 个数中任意 2 个的万位为 1其余 5 个为 0 即可。综合两部分得到题目核心结论minPartitions(n) max( n 的每一位十进制数字 )这是一个与数值大小无关、只与数位字符相关的性质示例 2 中82734的最大数字为 8、示例 3 中27346209830709182346的最大数字为 9均与给定输出吻合。三、Go 实现一次线性扫描求最大数字仓库中的解题源码位于 1689. Partitioning Into Minimum Number Of Deci-Binary Numbers.go与题解文档中的代码完全一致package leetcode func minPartitions(n string) int { res : 0 for i : 0; i len(n); i { if int(n[i]-0) res { res int(n[i] - 0) } } return res }实现要点逐条说明逐字节扫描不解析为数值。n是字符串n[i]直接取到第i个字节的 ASCII 码n[i]-0把它换算成对应的数字0~9再显式转为int。整个过程不产生大数运算天然满足长度可达 10^5的约束。原地维护最大值。res从 0 开始题目保证n是正整数故最终结果至少为 1每遇到比当前res大的数字就更新等价于对 10 个候选数字值做一轮取 max。由于单字节数字值域只有0~9也可以写成if n[i] byte(0res)之类的比较技巧但当前写法可读性最好。复杂度时间 O(n)仅一次遍历空间 O(1)除返回值外只用了res一个变量。对于答案只取决于最大数字这类问题这已是理论下界——必须至少看一遍所有字符才能确认最大值不存在渐近更快的做法。边界情况n 1时循环一次res更新为 1 后返回 1符合至少需要 1 个正十-二进制数的语义全 0 的情况被约束条件排除n表示正整数且无前导零。从源码结构看该文件只有单一函数、无任何辅助类型函数名minPartitions与 LeetCode 官方签名一致可直接提交。四、测试验证用仓库的测试框架跑一遍同目录下的 1689. Partitioning Into Minimum Number Of Deci-Binary Numbers_test.go 遵循本仓库统一的测试组织方式定义para1689入参结构体字段n string与ans1689期望答案结构体字段one int再在Test_Problem1689中构造用例切片并逐个打印实际输出qs : []question1689{ { para1689{32}, ans1689{3}, }, { para1689{82734}, ans1689{8}, }, }两个用例正好对应题目文档中的示例 132 - 3与示例 282734 - 8。值得注意的是测试以fmt.Printf打印【input】/【output】供人工比对而ans1689中的期望值目前仅作为参考数据存在这与该仓库多数题解测试的风格一致——把每题的核心示例固化为可重跑的最小回归集。本仓库对全部题解包统一采用gotest.sh生成覆盖率文件其内容很简单go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...也就是说对第 1689 题所在包运行测试时它与整个leetcode/...目录下的题解一起被编译、执行并统计覆盖率结果写入 coverage.txt。单独验证本题时可以直接执行go test -v ./leetcode/1689.Partitioning-Into-Minimum-Number-Of-Deci-Binary-Numbers/由于包内仅含minPartitions一个被测函数测试输出中【output】:3与【output】:8两个值即对应示例 1、示例 2 的判定示例 3 的长字符串27346209830709182346期望输出 9可手动调用minPartitions快速核对其最大数字恰为 9与结论一致。五、小结数学结论把n拆成最少数目的十-二进制数之和答案就是n各位数字中的最大值——下界来自每一位至多由每个加数贡献 1上界由按位分配 1 的个数的构造法给出。工程实现一次 O(n) 线性扫描、O(1) 额外空间用n[i]-0完成字符到数字的换算天然兼容 10^5 长度的超长数字串。验证方式仓库内以统一的para1689/ans1689结构组织用例覆盖题目前两个官方示例并通过 gotest.sh 与其余题解一起纳入 100% 覆盖率的测试体系。这道题的价值在于展示了把数值问题翻译成数位问题的视角一旦意识到答案只与数位字符相关复杂的大数处理问题就退化为一次字符扫描这也是 LeetCode-Go 中多数字符串类题解极简而正确风格的典型代表。【免费下载链接】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-Go 题解精讲：1689. 拆分最少数量的十-二进制数（Deci-Binary Numbers）
LeetCode-Go 题解精讲1689. 拆分最少数量的十-二进制数Deci-Binary Numbers【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇围绕 LeetCode-Go 仓库中第 1689 题「拆分最少数量的十-二进制数」的题解文档展开先完整还原题目定义、示例与约束再从数位角度给出答案即字符串中的最大数字的数学论证最后结合仓库中的 Go 实现源码与配套测试说明这一 O(n) 线性扫描解法如何落地、如何验证。读完后你将掌握这道题的完整证明思路、Go 实现的细节取舍以及在本仓库中运行该题测试与覆盖率检查的方法。一、题目描述什么是十-二进制数deci-binary原始题目见 题目文档的英文定义如下A decimal number is calleddeci-binaryif each of its digits is either0or1without any leading zeros. For example,101and1100aredeci-binary, while112and3001are not.Given a stringnthat represents a positive decimal integer, returntheminimumnumber of positivedeci-binarynumbers needed so that they sum up ton*.中文大意继承自原文档的题目大意小节如果一个十进制数字不含任何前导零且每一位上的数字不是 0 就是 1那么该数字就是一个十-二进制数。例如101和1100都是十-二进制数而112和3001不是。给定一个表示正整数的十进制字符串n返回使若干正十-二进制数之和恰好等于n所需的最少数目。原文档给出了三个示例完整保留如下示例 1Input: n 32 Output: 3 Explanation: 10 11 11 32示例 2Input: n 82734 Output: 8示例 3Input: n 27346209830709182346 Output: 9约束条件同样完整继承1 n.length 10^5n只由数字字符组成n不含前导零且表示一个正整数从约束可以看到n的长度上限达到 10 万位远超任何内置整数的表示范围——这也是题目要求以字符串而非整数作为入参的原因解法必须做到逐字符处理而不是把n解析成数值后再运算。二、核心洞察答案就是n中的最大数字原文档解题思路小节指出这题想通之后代码就 3 行。其论证可以拆解为下界证明与可达性构造两部分这里完整展开。下界为什么不能少于最大数字设n的某一位上数字为d例如n 82734的千位是 8。任何一个十-二进制数在该位上的取值只能是0或1且没有借位或进位跨数累加的机制——k 个十-二进制数相加时某一位的和最多只比 k 多出进位贡献但为了在该位最终得到d这 k 个数在该位至少要贡献出d个 1进位只会帮助低位不会凭空让高位数字减少所需加数个数。因此加数个数k必须满足k d。对所有数位取最大值得到最少数目 max(n 的每一位数字)以示例 1 为例32的最大数字是 3所以答案至少为 310 11 11 32恰好 3 个验证了取等成立。可达性为什么最大数字就一定够取k maxDigit。对n的每一位若该位数字为d就让这k个数中任意d个在该位取 1、其余k - d个在该位取 0。由于每一位上取 1 的个数恰好等于该位数字d逐位相加含正常十进制进位必然还原出n本身且每个构造出的数都不含前导零问题千位上若d 1取 1 的那个数自然以 1 开头若最高位d 0这与n 不含前导零的约束矛盾故最高位d 1。原文档用n 23423723举例这是一个 8 位数最大数字是 7所以至少需要 7 个数累加得到n这 7 个数的千位都为 1其他数位按需求取 0 和 1——例如万位是 2就让 7 个数中任意 2 个的万位为 1其余 5 个为 0 即可。综合两部分得到题目核心结论minPartitions(n) max( n 的每一位十进制数字 )这是一个与数值大小无关、只与数位字符相关的性质示例 2 中82734的最大数字为 8、示例 3 中27346209830709182346的最大数字为 9均与给定输出吻合。三、Go 实现一次线性扫描求最大数字仓库中的解题源码位于 1689. Partitioning Into Minimum Number Of Deci-Binary Numbers.go与题解文档中的代码完全一致package leetcode func minPartitions(n string) int { res : 0 for i : 0; i len(n); i { if int(n[i]-0) res { res int(n[i] - 0) } } return res }实现要点逐条说明逐字节扫描不解析为数值。n是字符串n[i]直接取到第i个字节的 ASCII 码n[i]-0把它换算成对应的数字0~9再显式转为int。整个过程不产生大数运算天然满足长度可达 10^5的约束。原地维护最大值。res从 0 开始题目保证n是正整数故最终结果至少为 1每遇到比当前res大的数字就更新等价于对 10 个候选数字值做一轮取 max。由于单字节数字值域只有0~9也可以写成if n[i] byte(0res)之类的比较技巧但当前写法可读性最好。复杂度时间 O(n)仅一次遍历空间 O(1)除返回值外只用了res一个变量。对于答案只取决于最大数字这类问题这已是理论下界——必须至少看一遍所有字符才能确认最大值不存在渐近更快的做法。边界情况n 1时循环一次res更新为 1 后返回 1符合至少需要 1 个正十-二进制数的语义全 0 的情况被约束条件排除n表示正整数且无前导零。从源码结构看该文件只有单一函数、无任何辅助类型函数名minPartitions与 LeetCode 官方签名一致可直接提交。四、测试验证用仓库的测试框架跑一遍同目录下的 1689. Partitioning Into Minimum Number Of Deci-Binary Numbers_test.go 遵循本仓库统一的测试组织方式定义para1689入参结构体字段n string与ans1689期望答案结构体字段one int再在Test_Problem1689中构造用例切片并逐个打印实际输出qs : []question1689{ { para1689{32}, ans1689{3}, }, { para1689{82734}, ans1689{8}, }, }两个用例正好对应题目文档中的示例 132 - 3与示例 282734 - 8。值得注意的是测试以fmt.Printf打印【input】/【output】供人工比对而ans1689中的期望值目前仅作为参考数据存在这与该仓库多数题解测试的风格一致——把每题的核心示例固化为可重跑的最小回归集。本仓库对全部题解包统一采用gotest.sh生成覆盖率文件其内容很简单go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...也就是说对第 1689 题所在包运行测试时它与整个leetcode/...目录下的题解一起被编译、执行并统计覆盖率结果写入 coverage.txt。单独验证本题时可以直接执行go test -v ./leetcode/1689.Partitioning-Into-Minimum-Number-Of-Deci-Binary-Numbers/由于包内仅含minPartitions一个被测函数测试输出中【output】:3与【output】:8两个值即对应示例 1、示例 2 的判定示例 3 的长字符串27346209830709182346期望输出 9可手动调用minPartitions快速核对其最大数字恰为 9与结论一致。五、小结数学结论把n拆成最少数目的十-二进制数之和答案就是n各位数字中的最大值——下界来自每一位至多由每个加数贡献 1上界由按位分配 1 的个数的构造法给出。工程实现一次 O(n) 线性扫描、O(1) 额外空间用n[i]-0完成字符到数字的换算天然兼容 10^5 长度的超长数字串。验证方式仓库内以统一的para1689/ans1689结构组织用例覆盖题目前两个官方示例并通过 gotest.sh 与其余题解一起纳入 100% 覆盖率的测试体系。这道题的价值在于展示了把数值问题翻译成数位问题的视角一旦意识到答案只与数位字符相关复杂的大数处理问题就退化为一次字符扫描这也是 LeetCode-Go 中多数字符串类题解极简而正确风格的典型代表。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考