> For the complete documentation index, see [llms.txt](https://vernon97-io.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://vernon97-io.gitbook.io/untitled/notes/week28.md).

# week28

#### 274 - H指数

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

```cpp
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

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

一看就是二分跑不掉了

```cpp
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的

```cpp
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 - 第一个错误的版本

纯纯二分法了

```cpp
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))`

```cpp
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.

```cpp
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;
    }
};
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://vernon97-io.gitbook.io/untitled/notes/week28.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.