LeetCode 补充题 161. 有符号三进制字符串转十进制

约 4 分钟
文章信息 3 个分类 2 个标签
分类
补充题 中等 字节
标签
字符串 数学

题目描述

给定可带正负号的三进制整数字符串 s，将它转换成任意精度的十进制字符串。

只允许数字 0、1、2，非法输入抛出异常或返回错误。

示例 1：

输入： s = "-102"
输出： "-11"
解释： 三进制 102 表示 1×3²+0×3+2=11，保留负号。

示例 2：

输入： s = "+002"
输出： "2"
解释： 前导正号和零不影响整数值，十进制结果为 2。

示例 3：

输入： s = "1203"
输出： 解析失败
解释： 数字 3 不属于三进制；Java 抛出解析异常，Go 返回失败标志。

提示：

  • 仅允许一个可选的前导正负号及数字 0、1、2。
  • 结果为任意精度十进制字符串。
  • 非法输入返回解析失败。

题意分析

输入只允许 ASCII 数字 0、1、2，以及一个可选的前导正负号。手撕时逐位计算 value=value×3+digit；任意精度的乘加和十进制格式化交给标准库。Java 非法输入抛出解析异常，Go 返回空串与 false。

解法：逐位乘三累加并处理符号

核心思路

[!blue]

value 始终表示已经读取的三进制数字前缀的非负数值。新来一位时，旧前缀的每个数位权重都提高三倍，再加当前数字，得到 value = value * 3 + digit。逐位应用这一式子就是完整的位权展开。

只在开头读取一次可选符号，符号后至少保留一位数字。之后每个字符都必须是 ASCII 0、1、2，不能忽略空格或中间符号；遇到非法字符立即返回解析失败。

全程用大整数累积，最后统一应用负号并转成十进制字符串。前导零自然不改变数值，负零也规范化为 0；不能先用固定宽度整数接收输入再转大整数。

解题步骤

  1. 检查非空输入，读取至多一个前导符号；只有符号时失败。
  2. 逐字符检查 0、1、2，执行 value=value×3+当前位。
  3. 最后应用负号，并由大整数库输出十进制字符串。

代码实现

class Solution {
    public String ternaryToDecimal(String s) {
        if (s == null || s.isEmpty()) {
            throw new NumberFormatException("empty input");
        }

        int index = 0;
        boolean negative = false;

        if (s.charAt(0) == '+' || s.charAt(0) == '-') {
            negative = s.charAt(0) == '-';
            index++;
        }

        if (index == s.length()) {
            throw new NumberFormatException("missing digits");
        }

        BigInteger value = BigInteger.ZERO;
        BigInteger base = BigInteger.valueOf(3);

        for (; index < s.length(); index++) {
            char digit = s.charAt(index);

            if (digit < '0' || digit > '2') {
                throw new NumberFormatException("invalid ternary digit");
            }

            value = value.multiply(base).add(BigInteger.valueOf(digit - '0'));
        }

        return (negative ? value.negate() : value).toString();
    }
}

import "math/big"

func ternaryToDecimal(s string) (string, bool) {
    if len(s) == 0 {
        return "", false
    }
    index := 0
    negative := false
    if s[0] == '+' || s[0] == '-' {
        negative = s[0] == '-'
        index++
    }
    if index == len(s) {
        return "", false
    }
    value, base := new(big.Int), big.NewInt(3)
    for ; index < len(s); index++ {
        digit := s[index]
        if digit < '0' || digit > '2' {
            return "", false
        }
        value.Mul(value, base)
        value.Add(value, big.NewInt(int64(digit-'0')))
    }
    if negative {
        value.Neg(value)
    }
    return value.String(), true
}

复杂度分析

  • 时间复杂度：解析执行 $O(n)$ 次大整数乘小常数与加法，数值位数随输入长度增长，不能把每次大整数运算都当作固定代价。十进制输出的转换成本另计。
  • 空间复杂度：随位数为 $O(n)$。

关键点总结

[!green]

手撕的是位权递推与输入规则，大整数乘加复用标准库；不能用固定宽度整数暂存完整输入。

易错点总结

[!yellow]

  • 不能先把长输入转成 int 或 long，再构造大整数。
  • 只有符号不是合法数字；符号只能出现在第一位。
  • 逐位校验 ASCII 0、1、2，非法字符不能被忽略；负零输出为 0。

相似题目

题目 难度 关联与区别
补充题 145. 有符号整数的进制转换 中等 两题是相反方向：本题从高位累乘解析，另一题从低位取余生成数位。
171. Excel 表列序号 简单 同样按位权累乘累加，Excel 列数字从 1 开始，本题数码从 0 开始且使用任意精度。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/04955387
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！