week28

274 - H指数

从大到小排序， 从右往左 找到第一个满足f[i] >= i 的位置即为答案

class Solution {
public:
    int hIndex(vector<int>& citations) {
        sort(citations.begin(), citations.end(), greater<int>());
        // 6 5 3 1 0 满足f[i] >= i 
        for(int i = citations.size() - 1; i >= 0; i--)
            if(citations[i] >= i + 1) return i + 1;
        return 0;
    }
};

275 - H指数II

你可以优化你的算法到对数时间复杂度吗？

一看就是二分跑不掉了

class Solution {
public:
    int hIndex(vector<int>& citations) {
        // 这题已经保证有序了 但是是从小到大的有序
        int n = citations.size();
        if(n == 0) return 0;
        reverse(citations.begin(), citations.end());
        int l = 0, r = n - 1;
        while(l < r)
        {
            int mid = l + r + 1 >> 1;
            if(citations[mid] >= mid + 1) l = mid;
            else r = mid - 1;
        }
        if(citations[l] >= l + 1) return l + 1;
        else return l;
    }
};

但这里是可以通过处理二分的条件实现不用reverse的 -> 手动的坐标变换

这里的mid 是一定取不到0的

class Solution {
public:
    int hIndex(vector<int>& citations) {
        // 这题已经保证有序了 但是是从小到大的有序
        int n = citations.size();
        if(n == 0) return 0;
        //reverse(citations.begin(), citations.end());
        int l = 0, r = n;
        while(l < r)
        {
            int mid = l + r + 1 >> 1;
            if(citations[n - mid] >= mid) l = mid;
            else r = mid - 1;
        }
        return l;
    }
};

278 - 第一个错误的版本

纯纯二分法了

class Solution {
public:
    int firstBadVersion(int n) {
        // 二分
        int l = 1, r = n;
        while(l < r)
        {
            int mid = l + (r - l) / 2;
            if(isBadVersion(mid)) r = mid;
            else l = mid + 1;
        } 
        return r;
    }
};

279 - 完全平方数

这个可以用dp来做了 (完全背包) 首先打表然后状态转移就可 - o(n * sqrt(n))

class Solution {
public:
    int numSquares(int n) {
        vector<int> squares;
        // 打表预处理平方数 最大到100 * 100
        for(int i = 1; i <= 100; i++)
            squares.push_back(i * i);
        vector<int> f(n + 1, 10000);
        f[0] = 0;
        for(int i = 1; i <= n; i++)
            for(int j = 0; squares[j] <= i; j++)
                f[i] = min(f[i], f[i - squares[j]] + 1);
        return f[n];
    }
};

但除了这个dp之外 还有一些数学定理来帮助解决这个问题 （看一看就好了）

1. 拉格朗日四平方和定理

states that every natural number can be represented as the sum of four integer squares. That is, the squares form an additive basis of order four.

2. 勒让德三平方和定理

Legendre's three-square theorem states that a natural number can be represented as the sum of three squares of integers if and only if n is not of the form n = 4^a(8b + 7) for nonnegative integers a and b.

class Solution {
public:
    bool check(int x)
    {
        int r = sqrt(x);
        return r * r == x;
    }
    int numSquares(int n) {
        // 判断 答案 1
        if(check(n)) return 1;
        // 判断 答案 2
        for(int i = 1; i <= n / i; i++)
            if(check(n - i * i)) return 2;
        // 判断能否写成 4 ^ a (8b + 7)的形式
        while(n % 4 == 0)
            n /= 4;
        if(n % 8 != 7) return 3;
        return 4;
    }
};