Math-Medium

2020-04-30

Abstract：leetcode 数学tag Medium 难度题解合集

50. Pow(x, n)

解法一：递归快速幂

快速幂本质就是靠不重复计算平方提速的，但是这题有坑点，n必须先转成long long类型，否则会被卡

class Solution {
public:
    double myPow(double x, int n) {
        long long l = n;
        return l > 0 ? fastPow(x, l) : fastPow(1 / x, -l);
    }

    double fastPow(double x, int n){
        if(n == 0) return 1;
        if(n == 1) return x;
        double half = fastPow(x, n / 2);
        if(n % 2 == 0)
            return half * half;
        else 
            return half * half * x;
    }
};

解法二：迭代快速幂

卡了半天还是看了答案

223. Rectangle Area

解法一

本质就是求交面积问题，因为没有旋转问题，所以求交也很简单。。

最后记得先减再加否则会溢出

class Solution {
public:
    int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
        int overlap = 0;
        if(!(E >= C || D <= F || G <= A || H <= B)) {        
            int left   = std::max(A, E);
            int right  = std::min(C, G);
            int top    = std::min(D, H);
            int bottom = std::max(B, F);   
            overlap = (right - left) * (top - bottom);
        }
        int area1 = (D - B) * (C - A);
        int area2 = (G - E) * (H - F);
        return  area1 + (area2 - overlap);
    }
};

279. Perfect Squares

解法一：记忆化递归

我们显然可以递归地求解这个问题，也就是

F(n) = 1 + min{ i * i <= n | F(n - i * i) }

很快我们可以得到递归写法

class Solution {
public:
    vector<int> memo;
    int numSquares(int n) {
        if(n == 0) return 0;
        int min = INT32_MAX;
        for(int i = 1; i * i <= n; i++) {
            min = std::min(min, numSquares(n - i * i) + 1);
        }
        return min;
    }
};

但是直接递归就太多重复了，就像斐波那契数列的递归写法一样，所以我们记忆化递归

class Solution {
public:
    vector<int> memo;
    int numSquares(int n) {
        memo = vector<int>(n + 1, INT32_MAX);
        memo[0] = 0;
        return getMinSquare(n);
    }

    int getMinSquare(int n) {
        if(memo[n] != INT32_MAX) return memo[n];
        for(int i = 1; i * i <= n; i++) {
            memo[n] = std::min(memo[n], getMinSquare(n - i * i) + 1);
        }
        return memo[n];
    }
};

解法二：DP

记忆化递归改写成DP

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1, INT32_MAX);
        dp[0] = 0;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j * j <= i; j++) {
                dp[i] = std::min(dp[i], dp[i - j * j] + 1);
            }
        }
        return dp[n];
    }
};

解法三：BFS + 贪心

如果把问题理解成最短路问题的话…下次再写

解法四：数论

这题是有数学解的，反正我是不知道这种方法，看了答案，数学，永远滴神

一个数最多需要4个完全平方数来表示
对于可以表示为$4^k(8m + 7)$形式的数，需要四个平方数来表示
对于完全平方数，当然只需要一个
对于需要两个的完全平方数，我们枚举检查
否则排除法需要三个

class Solution {
public:
    bool isSquare(int n) {
        int val = (int)std::sqrt(n);
        return n == val * val;
    }

    int numSquares(int n) {
        while(n % 4 == 0)
            n /= 4;
        if(n % 8 == 7)
            return 4;
        if(isSquare(n)) return 1;
        for(int i = 1; i * i <= n; i++) {
            if(isSquare(n - i * i)) return 2;
        }
        return 3;
    }
};

593. Valid Square

解法一：枚举

考虑三种不同的相对位置
当四条边相等且对角线也相等时说明是正方形

class Solution {
public:
    bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
        return check(p1, p2, p3, p4) || check(p1, p3, p2, p4) || check(p1, p2, p4, p3);
    }

    bool check(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
        int d1 = getDistance(p1, p2),
            d2 = getDistance(p2, p3),
            d3 = getDistance(p3, p4),
            d4 = getDistance(p4, p1),
            d5 = getDistance(p1, p3),
            d6 = getDistance(p2, p4);
        return d1 > 0 && d1 == d2 && d2 == d3 && d3 == d4 && d5 == d6;
    }

    int getDistance(vector<int>& p1, vector<int>& p2) {
        int y = p2[1] - p1[1], x = p2[0] - p1[0];
        return y * y + x * x; 
    }
};

Overyam