出现最频繁的偶数元素

就是可以通过一个数组来记录每个数的出现次数

开一个哈希表或者开个数组就可以模拟

class Solution {
public:
    int f[100001];//记录出现次数

    int mostFrequentEven(vector<int> &nums) {
        for (auto &n: nums) {
            if (n % 2 == 0)//如果是偶数，对应的出现次数+1
                f[n]++;
        }
        int id = max_element(f, f + 100001) - f;//找到出现次数最多的值的索引，也就是这个数
        if (f[id] == 0) {//如果出现0次是返回-1
            return -1;
        }
        return id;//否则直接返回结果
    }
};

子字符串的最优划分

实质上本题的答案应该在[1,s.size()/26]之间，

本质就是通过一个布尔数组来记录出现的字符，然后得到答案

每次判断如果不能加入该字符，就让布尔数组重置即可

class Solution {
public:
    bool f[256];//用于记录每个字符的出现情况

    int partitionString(string s) {
        int ans = 1;//最小答案是1，因为默认会有一个字符串， 每次切分要结果+1
        for (auto &ch: s) {
            if (f[ch]) {//要加入到当前段的字符串有此字符
                ans++;//需要在该字符串前切分
                memset(f, 0, sizeof f);//切分后重置字符串
            }
            f[ch] = 1;//把当前字符记录到当前段的出现记录中
        }
        return ans;
    }
};

将区间分为最少组数

本题应该是个原题我印象里

如果这个点被2个区间覆盖了，那么我们要把覆盖2次分成两个组。

故本题实质是找哪个点被覆盖的次数最多，答案就是覆盖的次数

对于每个区间[l,r]，可以理解为在[l,r]上的每个值都+1了，

最中就找哪个点的值最大。

因此是很明显的差分数组题目

class Solution {
public:
    int f[1000010];//差分数组

    int minGroups(vector<vector<int>> &intervals) {
        for (auto &i: intervals) {
            f[i[0]]++;//起点要+1
            f[i[1] + 1]--;//由于是闭区间，因此右端点的后一个数要-1
        }
        int now = 0;//记录当前点的覆盖次数
        int ans = 0;//记录结果
        for (int i = 1; i < 1000010; i++) {
            now += f[i];//计算当前点的覆盖次数
            ans = max(ans, now);//比较答案和当前的次数
        }
        return ans;
    }
};

最长递增子序列 II

这个题就在前几周出过，但是因为那个题是字符串，k是小于26的，这个是1e5，所以复杂度O(nk)会达到1e10。

优化的话就是通过线段树来找每个区间的最大值，将O(nk)变为O(nlogk)

const int N = 100010;
struct no {
    int l, r;
    int v;
} tr[N * 4];

class Solution {
public:
    void pushup(int u) { tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v); }
    void build(int u, int l, int r) {
        tr[u] = {l, r};
        if (l == r) return;
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    }
    int query(int u, int l, int r) {
        if (tr[u].l >= l && tr[u].r <= r) return tr[u].v;
        int mid = tr[u].l + tr[u].r >> 1;
        int v = 0;
        if (l <= mid) v = query(u << 1, l, r);
        if (r > mid) v = max(v, query(u << 1 | 1, l, r));
        return v;
    }
    void modify(int u, int x, int v) {
        if (tr[u].l == x && tr[u].r == x)
            tr[u].v = v;
        else {
            int mid = tr[u].l + tr[u].r >> 1;
            if (x <= mid)
                modify(u << 1, x, v);
            else
                modify(u << 1 | 1, x, v);
            pushup(u);
        }
    }
    int lengthOfLIS(vector<int> &nums, int k) {
        build(1, 1, N);//单点修改，区间最大值线段树
        for (auto &n: nums) {
            int cnt = query(1, n - k, n - 1);//找到[n-k,n-1]的最大值
            modify(1, n, cnt + 1);//将当前字符结尾的最大长度记录为[n-k,n-1]的最大值+1
        }
        return query(1, 1, N);//最终答案是整个树中的最大值
    }
};