使用 C++ 的 LeetCode 中的 Pow(x,n)。地址消毒器 33

Question

我尝试在 Leetcode 上提交 Pow(x,n) 问题的解决方案时遇到错误，我不知道如何解决。

double myPow(double x, int n) 
{
    if(n == 0) return 1;      //Power of 0 return 1
    int flag = 1;
    double result;
    if(n<0) flag = -1;      //check if negative power
    vector<double> myvec(n*flag,x);   //create a vector length of the power, filled with our number x
    result = accumulate(begin(myvec), end(myvec), 1.0, multiplies<>());   //multiply the elements of the vector
    return flag > 0? result : 1/result;     
}

我得到的错误是这样的：

==33==ERROR: AddressSanitizer: allocator is out of memory trying to allocate 0x3fffffff8 bytes
#7 0x7f44d265d82f  (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)
==33==HINT: if you don't care about these errors you may set allocator_may_return_null=1

如果我将“累加”行保留为 1 而不是 1.0，我得到的结果就好像双 x 是一个整数（例如 2.1^3=8）。但是当我将它更改为 1.0 以便从双精度中获取小数点时，我得到了上述错误。

有什么想法吗？

Answer 1

我认为这个问题不应该用 std::accumulate 来解决，不过我可能是错的。

这是一个迭代解决方案，将通过：

struct Solution {
    static const inline double myPow(double x, int64_t n) {
        double res = 1;
        int64_t m;

        if (n < 0) {
            m = -n;
            x = 1 / x;

        } else {
            m = n;
        }

        while (m) {
            if (m & 1) {
                res *= x;
            }

            x *= x;
            m >>= 1;
        }

        return res;
    }
};

这里是 LeetCode 的解决方案之一：

class Solution {
public:
    double myPow(double x, int n) {
        long long N = n;
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }
        double ans = 1;
        double current_product = x;
        for (long long i = N; i ; i /= 2) {
            if ((i % 2) == 1) {
                ans = ans * current_product;
            }
            current_product = current_product * current_product;
        }
        return ans;
    }
};

参考资料

有关其他详细信息，您可以在其中查看 Discussion Board. There are plenty of accepted solutions with a variety of languages and explanations, efficient algorithms, as well as asymptotic time/space complexity analysis^{1, 2}。

对于interviews：

我们想写 bug-free and clean codes based on standards and conventions (e.g., c^{1, 2}, c++^{1, 2}, java^{1, 2}, c#^{1, 2}, python¹, javascript¹, go¹, rust¹).

Answer 2

您分配的内存过多。您可以通过使用简单的 for 循环获得相同的结果。

double res = 1;
for (int i = 1; i <= n; ++i)
    res *= x;

虽然它可能会给你 TLE。所以你需要一个更好的算法。

使用 C++ 的 LeetCode 中的 Pow(x,n)。地址消毒器 33

Pow(x,n) in LeetCode using C++. AddressSanitizer 33

c++

algorithm

out-of-memory

参考资料

对于interviews：