当前位置: 面试刷题>> a b问题 (经典算法题500道)


题目描述补充

题目:a b问题

给定两个非负整数a和b(0 ≤ a, b ≤ 10^9),计算a^b(即a的b次幂)的结果,并以字符串形式返回。由于结果可能非常大,直接计算并存储为整数可能会导致溢出,因此以字符串形式返回是必要的。

示例

  • 输入:a = 2, b = 10
  • 输出:"1024"

注意

  • 考虑到性能,尽量避免使用库函数直接计算大数乘法或幂运算(尽管在某些语言中这些操作可能内置了优化)。
  • 编写代码时,应考虑到内存和时间的效率。

PHP 示例代码

function power($a, $b) {
    $result = "1";
    $base = strval($a);
    
    while ($b > 0) {
        if ($b % 2 == 1) {
            $result = multiplyStrings($result, $base);
        }
        $base = multiplyStrings($base, $base);
        $b = intdiv($b, 2);
    }
    
    return $result;
}

function multiplyStrings($num1, $num2) {
    $m = strlen($num1);
    $n = strlen($num2);
    $result = array_fill(0, $m + $n, 0);
    
    for ($i = $m - 1; $i >= 0; $i--) {
        for ($j = $n - 1; $j >= 0; $j--) {
            $mul = intval($num1[$i]) * intval($num2[$j]);
            $p1 = $i + $j;
            $p2 = $i + $j + 1;
            $sum = $mul + $result[$p2];
            $result[$p2] = $sum % 10;
            $result[$p1] += intval($sum / 10);
        }
    }
    
    $resultStr = "";
    $i = 0;
    while ($i < count($result) && $result[$i] == 0) $i++;
    
    while ($i < count($result)) {
        $resultStr .= strval($result[$i++]);
    }
    
    return $resultStr == "" ? "0" : $resultStr;
}

// 示例使用
echo power(2, 10);  // 输出:1024

Python 示例代码

Python 的内建库支持大数运算,但为了符合题目要求,这里使用迭代方法手动实现:

def power(a, b):
    if b == 0:
        return "1"
    
    result = "1"
    base = str(a)
    
    while b > 0:
        if b % 2 == 1:
            result = multiply_strings(result, base)
        base = multiply_strings(base, base)
        b //= 2
    
    return result

def multiply_strings(num1, num2):
    m, n = len(num1), len(num2)
    result = [0] * (m + n)
    
    for i in range(m - 1, -1, -1):
        x = int(num1[i])
        for j in range(n - 1, -1, -1):
            y = int(num2[j])
            result[i + j + 1] += x * y
            result[i + j] += result[i + j + 1] // 10
            result[i + j + 1] %= 10
    
    # 去除前导零
    i = 0
    while i < len(result) and result[i] == 0:
        i += 1
    
    return ''.join(map(str, result[i:])) or "0"

# 示例使用
print(power(2, 10))  # 输出:1024

JavaScript 示例代码

JavaScript 同样支持大数运算,但为了练习,我们手动实现:

function power(a, b) {
    if (b === 0) return "1";

    let result = "1";
    let base = a.toString();

    while (b > 0) {
        if (b % 2 === 1) {
            result = multiplyStrings(result, base);
        }
        base = multiplyStrings(base, base);
        b = Math.floor(b / 2);
    }

    return result;
}

function multiplyStrings(num1, num2) {
    let m = num1.length;
    let n = num2.length;
    let result = Array(m + n).fill(0);

    for (let i = m - 1; i >= 0; i--) {
        for (let j = n - 1; j >= 0; j--) {
            let mul = parseInt(num1[i]) * parseInt(num2[j]);
            let p1 = i + j;
            let p2 = i + j + 1;
            let sum = mul + result[p2];
            result[p2] = sum % 10;
            result[p1] += Math.floor(sum / 10);
        }
    }

    let resultStr = "";
    for (let i = 0; i < result.length; i++) {
        if (result[i] !== 0) break;
    }
    for (let i = i; i < result.length; i++) {
        resultStr += result[i].toString();
    }
    return resultStr || "0";
}

// 示例使用
console.log(power(2, 10));  // 输出:1024

码小课:在码小课网站中,你可以找到更多关于算法和数据结构的深入解析,以及更多编程实战项目,帮助大家提升编程能力。

推荐面试题