193周赛.md

450 / 3803

第一题前缀和就放上来了。

题目： LeetCode 5437. 不同整数的最少数目. 给你一个整数数组 arr 和一个整数 k 。现需要从数组中恰好移除 k 个元素，请找出移除后数组中不同整数的最少数目。

//排序可以不需要用pair，因为只关心剩余的数字的个数，可以只用数字作为排序。
class Solution {
public:
    int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
        unordered_map<int,int> m;
        for(int a: arr){
            m[a]++;
        }
        vector<pair<int,int>> count;
        for(auto it = m.begin(); it != m.end(); it++){
            count.push_back(*it);
        }
        sort(count.begin(),count.end(),[&](pair<int,int> p1,pair<int,int>p2){
            return p1.second < p2.second; 
        });
        int index = 0;
        for(auto p : count){
            if(p.second <= k){
                k -= p.second;
                index++;
            }else{
                break;
            }
        }
        return count.size()-index;
    }
};

题目： LeetCode 5438. 给你一个整数数组 bloomDay，以及两个整数 m 和 k 。现需要制作 m 束花。制作花束时，需要使用花园中 相邻的 k 朵花 。花园中有 n 朵花，第 i 朵花会在 bloomDay[i] 时盛开，恰好可以用于一束 花中。请你返回从花园中摘 m 束花需要等待的最少的天数。如果不能摘到 m 束花则返回 -1 。

//二分法，在解空间里查找，给定天数判断是否满足条件，如果满足则往查找更小的值，如果不满足就找更大的天数。
class Solution {
public:
    //改成动态规划
    bool satisfy(vector<int>& bloomDay,int m, int k, int day){
        int count = 0;
        for(int i = 0; i < bloomDay.size(); ){
            int j ;
            for(j = 0; j < k ; j++){  
                if(i+j >= bloomDay.size() || bloomDay[i+j] > day){  
                    break;
                }    
            }
            if(j == k){
                count++;
            }
            i = i + (j>1?j:1);
            if(count >= m) return true;
        }
        return count >= m ;
    }
    int minDays(vector<int>& bloomDay, int m, int k) {
        if(m*k > bloomDay.size()) return -1;
        int left = INT_MAX;
        int right = 0;
        for(int day:bloomDay){
            if(day>right){
                right = day;
            }
            if(day<left){
                left = day;
            }
        }
        while(left<right){
            int mid = left + (right-left)/2;
            if(satisfy(bloomDay,m,k,mid)){  //如果满足条件，肯定在更小的区间里找
                right = mid;
            }else{  //不满足，则找更大的
                left = mid+1;
            }
        }
        return left;
        if(satisfy(bloomDay,m,k,left)) return left;
        return -1;
    }
};

题目： LeetCode 5188. 给你一棵树，树上有 n 个节点，按从 0 到 n-1 编号。树以父节点数组的形式给出，其中 parent[i] 是节点 i 的父节点。树的根节点是编号为 0 的节点。请你设计并实现 getKthAncestor(int node, int k) 函数，函数返回节点 node 的第 k 个祖先节点。如果不存在这样的祖先节点，返回 -1 。树节点的第 k 个祖先节点是从该节点到根节点路径上的第 k 个节点。

//因为可能树变成线性的表，因此需要用额外的空间记录更多的信息。
//dp[i][j] 代表第i个节点的2^j个父亲节点。
// 如果 a->b->c->d->e
// dp[a][0] = b ;
// dp[a][1] = dp[ dp[a][0] ] [0] = c
// dp[a][2] = dp[ dp[a][1] ] [1] = e  四个父亲节点
class TreeAncestor {
    vector<vector<int>> p;
public:
    TreeAncestor(int n, vector<int>& parent) {
        p = vector<vector<int>>(n, vector<int>(18, -1));
        for (int i = 0; i < n; ++i)
            p[i][0] = parent[i];
        // 18 代表正数最多18位，不会再比这个多了
        for (int k = 1; k < 18; ++k)
            for (int i = 0; i < n; ++i) {
                if (p[i][k - 1] == -1)
                    continue;
                //如果到-1了直接退出循环
                p[i][k] = p[p[i][k - 1]][k - 1];
            }
    }
    int getKthAncestor(int node, int k) {

        //这里把k看作二进制，当那一位为1时，才进行查找
        for (int i = 17; i >= 0; --i)
            if (k & (1 << i)) {
                node = p[node][i];
                if (node == -1)
                    break;
            }
        return node;
    }
};