LeetCode 补充题 20. 立方根

2025-03-19 HGNULB 约 6 分钟

文章信息 10 个分类 2 个标签

分类

LeetCode CodeTop 中等未解决 5-10 字节跳动美团滴滴拼多多高频面试题

题目描述

✅ 补充题 20. 立方根

题意分析

给定一个实数 x，求它的立方根，要求自己实现而不能直接调用现成的开方函数。答案是浮点数，通常按题面规定保留若干位小数，因此得到的是一个足够精确的近似值而非精确解。

题目禁止调库这一条，本身就是在指定考点：必须自己构造一个能逼近答案的过程。而输入是实数、输出也是实数，说明这不是整数域上的枚举问题，逼近必须在连续区间上进行。

有两处约束需要读出来。其一，立方根对负数同样有定义，且 $(-a)^3 = -a^3$，所以负输入的立方根就是其绝对值立方根取负——这允许把符号剥离出去，让核心逻辑只面对非负数。其二，输入的绝对值可能小于 1，而此时立方根大于输入本身，比如 0.001 的立方根是 0.1、0.008 的立方根是 0.2；如果想当然地认为答案不超过输入，搜索范围就会把真解排除在外。

边界情形：x 为 0 时答案为 0；x 为 1 或 -1 时答案就是自身；x 绝对值很大时答案远小于输入，搜索范围虽然宽但逼近速度是对数级的，不构成问题。

解法：浮点二分

核心思路

对非负数 target，函数 $f(y)=y^3$ 严格递增，因此可以在答案区间上二分。先把输入的符号剥离，只求 $\lvert x\rvert$ 的立方根，最后再恢复符号。

搜索区间取 [0, max(1, target)]。当 target >= 1 时，右端点的立方不小于 target；当 0 <= target < 1 时，真实立方根可能大于 target，但一定不超过 1。循环中始终维护：

真实立方根位于 [left, right] 内。

若 mid^3 < target，说明 mid 偏小，令 left = mid；否则令 right = mid。每轮区间减半且不丢失答案，因此循环结束时两端都逼近真实值。

浮点数不存在整数二分里的 mid + 1。这里固定迭代 80 次，避免区间缩小到相邻浮点数后边界不再变化导致死循环；对常见 double 精度已经足够。

解题步骤

记录 x 是否为负数，并令 target = abs(x)。

初始化 left = 0、right = max(1, target)，确保真解在区间内。

固定迭代 80 次，计算 mid = left + (right - left) / 2。

若 mid * mid * mid < target，收缩左边界；否则收缩右边界。

返回两端中点，并根据原输入恢复符号。

例如 x = 0.008 时，区间必须取 [0, 1]，因为答案 0.2 大于原数；若误把右端点写成 0.008，二分永远不可能找到答案。x = -8 则先对 8 求得 2，再返回 -2。

代码实现

class Solution {
    public double cubeRoot(double x) {
        boolean negative = x < 0;
        double target = Math.abs(x);
        double left = 0.0;
        double right = Math.max(1.0, target);

        for (int i = 0; i < 80; i++) {
            double mid = left + (right - left) / 2.0;
            if (mid * mid * mid < target) {
                left = mid;
            } else {
                right = mid;
            }
        }

        double root = left + (right - left) / 2.0;
        return negative ? -root : root;
    }
}

func cubeRoot(x float64) float64 {
    negative := x < 0
    target := x
    if target < 0 {
        target = -target
    }

    left, right := 0.0, target
    if right < 1 {
        right = 1
    }

    for i := 0; i < 80; i++ {
        mid := left + (right-left)/2
        if mid*mid*mid < target {
            left = mid
        } else {
            right = mid
        }
    }

    root := left + (right-left)/2
    if negative {
        return -root
    }
    return root
}

复杂度分析

时间复杂度：若要求绝对误差不超过 $\varepsilon$，初始区间宽度为 $R$，需要 $O(\log(R/\varepsilon))$ 轮。代码固定执行 80 轮，因此在固定双精度模型下可视为 $O(1)$。

空间复杂度：$O(1)$，只使用常数个浮点变量。

关键点总结

二分依赖的是函数单调性，而不是输入必须是数组。

max(1, abs(x)) 同时覆盖绝对值大于 1 和小于 1 的输入。

浮点二分更新为 mid，通常用固定轮数或明确精度控制终止。

面试时先说明精度要求；若题目要求任意大数或相对误差，需要进一步调整比较方式和终止条件。

易错点总结

右边界直接取 abs(x)：0 < abs(x) < 1 时真解会落在区间外。

忘记处理负数：循环会收敛到 0，而不是负立方根。

写成 left = mid + 1：浮点域没有“下一个实数”，会破坏区间不变量。

用浮点相等作为退出条件：舍入误差使该条件不可靠。

迭代轮数过少：初始区间较大时无法达到题目要求的精度。

相似题目

题目	难度	考察点
69. x 的平方根	简单	答案取整数，二分退化成整数域且要防乘法溢出
LCR 072. x 的平方根	简单	与 69 同题换编号，可对照整数与浮点两种收敛写法
875. 爱吃香蕉的珂珂	中等	谓词需要遍历数组统计耗时，判定本身是线性的
LCR 073. 爱吃香蕉的狒狒	中等	与 875 同题，注意向上取整的除法写法
1011. 在 D 天内送达包裹的能力	中等	下界必须取单件最大重量，否则谓词永远为假
410. 分割数组的最大值	困难	二分子数组和的上限，用贪心分段验证段数
1231. 分享巧克力	困难	最大化最小值，谓词方向与最小化最大值相反
1482. 制作 m 束花所需的最少天数	中等	在时间轴上二分，判定要数连续可用的花段
1552. 两球之间的磁力	中等	先排序再二分最小间距，贪心放球做验证
774. 最小化去加油站的最大距离	困难	同为浮点二分，判定是累加每段需要插入的站数
644. 子数组最大平均数 II	困难	浮点二分平均值，靠前缀和把判定转成存在性问题
668. 乘法表中第k小的数	困难	二分值域并按行计数，答案未必真实存在于表中
719. 找出第 K 小的数对距离	困难	二分距离，用双指针统计不超过该距离的数对数
878. 第 N 个神奇数字	困难	判定用容斥求倍数个数，还需处理取模与大数
1201. 丑数 III	中等	同为容斥计数，注意最小公倍数会超出常规范围
LCP 12. 小张刷题计划	中等	判定时每天可免去一道题，贪心里要额外记最大值