LeetCode.193场周赛

~~先bb两句，科目三终于考完了，现在可以好好的学习(玩耍)了hh~~

1480.一维数组的动态和

给你一个数组 nums 。数组「动态和」的计算公式为：runningSum[i] = sum(nums[0]…nums[i])。
请返回 nums 的动态和。

分析

求一次前缀和即可。 $O(n)$

class Solution {
public:
    vector<int> runningSum(vector<int>& nums) {
        
        int n = nums.size();
        vector<int> ans(n);
        ans[0] = nums[0];
        for(int i = 1; i<n; i++) {
            if(i)
                ans[i]  = ans[i-1] + nums[i];
        }

        return ans;
    }
};

1481.不同整数的最少数目

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

分析

构造一个pair数组，second放数字本身，first放该数字出现的次数，根据pair的性质，在排序时，先比较first，如果first相同在比较second，排完序后，删除前面的数即可，优先删除数量少的数字肯定是对答案有利的。 $O(nlogn)$ .

class Solution {
public:
    int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
        unordered_map<int,int> h;
        for(int x: arr) h[x]++;
        int ans = h.size();
        vector<pair<int,int>> s;
        for(auto it:h)
            s.push_back(make_pair(it.second,it.first));

        sort(s.begin(),s.end());

        for(auto x: s){
            if(k>=x.first){
                k -= x.first;
                ans--;
            }else break;
        }
        return ans;
    }
};

1482.制作m束花所需的最少天数

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

$bloomDay.length == n$
$1 <= n <= 10^5$
$1 <= bloomDay[i] <= 10^9$
$1 <= m <= 10^6$
$1 <= k <= n$

分析

二分答案，check函数判断在当前天数下是否可以制作出m束花。

class Solution {
public:
    vector<int> a;
    bool check(int x,int n,int m,int k){
        int r = 0;
        for(int i = 0; i<n; i++){
            if(a[i] <= x){
                int t = k;
                while(i<n && a[i]<=x){
                    i++;
                    t--;
                    if(t == 0){
                        r++;
                        t = k;
                    }
                }
            } 
        }
        return r>=m;
    }
    int minDays(vector<int>& bloomDay, int m, int k) {
        int n = bloomDay.size();
        if(m*k > n) return -1;
        this->a = bloomDay;
        int l = 1, r = 1e9;
        while(l<r){
            int mid = (l+r)>>1;
            if(check(mid,n,m,k)) r = mid;
            else l = mid+1;
        }
        //cout<<l<<endl;
        if(check(l,n,m,k)) return l;
        return -1;
    }
};

1483.树节点的第k个祖先

给你一棵树，树上有 n 个节点，按从 0 到 n-1 编号。树以父节点数组的形式给出，其中parent[i] 是节点 i 的父节点。树的根节点是编号为 0 的节点。

请你设计并实现 getKthAncestor(int node, int k)函数，函数返回节点 node 的第 k 个祖先节点。如果不存在这样的祖先节点，返回 -1 。

树节点的第 k 个祖先节点是从该节点到根节点路径上的第 k 个节点。

$1 <= k <= n <= 5*10^4$
$parent[0] == -1 表示编号为 0 的节点是根节点。$
$对于所有的 0 < i < n ，0 <= parent[i] < n 总成立$
$0 <= node < n$
$至多查询 5*10^4 次$

分析

DP, dp[i][j]表示节点 i 向上走2^j步，就有dp[i][j] = dp[dp[i][j-1]][j-1]，从根节点bfs一遍，预处理出dp数组。

class TreeAncestor {
public:
    vector<vector<int>> dp;  //dp[i][j] 表示节点i向上走2^j步
    vector<vector<int>> g;   //邻接表
    TreeAncestor(int n, vector<int>& parent) {
        dp = vector<vector<int>> (n,vector<int>(16,-1));
        g = vector<vector<int>> (n);

        int root = 0;
        for(int i = 0; i<n; i++){
            if(parent[i] == -1) root = i;
            else g[parent[i]].push_back(i);
        }

        //宽搜，预处理出dp数组
        queue<int> q;
        q.push(root);
        while(q.size()){
            int t = q.front();
            q.pop();

            for(int x: g[t]){
                dp[x][0] = t;  //向上走一步走到自己的父节点
                for(int j = 1; j<16; j++){
                    if(dp[x][j-1] != -1)
                        dp[x][j] = dp[dp[x][j-1]][j-1];
                }
                q.push(x);
            }
        }
    }
    
    int getKthAncestor(int node, int k) {
        int ans = node;
        for(int i = 0; i<16; i++){
            if(k>>i&1){
                ans = dp[ans][i];
                if(ans == -1) return -1;
            }
        }
        return ans;
    }
};

/**
 * Your TreeAncestor object will be instantiated and called as such:
 * TreeAncestor* obj = new TreeAncestor(n, parent);
 * int param_1 = obj->getKthAncestor(node,k);
 */