On the shoulders of giants.

weekly-contest-193

一维数组的动态和

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

请返回 nums 的动态和。

示例 1:

输入:nums = [1,2,3,4]
输出:[1,3,6,10]
解释:动态和计算过程为 [1, 1+2, 1+2+3, 1+2+3+4] 。

示例 2:

输入:nums = [1,1,1,1,1]
输出:[1,2,3,4,5]
解释:动态和计算过程为 [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1] 。

示例 3:

输入:nums = [3,1,2,10,1]
输出:[3,4,6,16,17]

提示:

  • 1 <= nums.length <= 1000
  • -10^6 <= nums[i] <= 10^6
题解

简单的一维前缀和。

时间复杂度: \(O(n)\)

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

不同整数的最少数目

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

示例 1:

输入:arr = [5,5,4], k = 1
输出:1
解释:移除 1 个 4 ,数组中只剩下 5 一种整数。

示例 2:

输入:arr = [4,3,1,1,3,3,2], k = 3
输出:2
解释:先移除 4、2 ,然后再移除两个 1 中的任意 1 个或者三个 3 中的任意 1 个,最后剩下 1 和 3 两种整数。

提示:

  • 1 <= arr.length <= 10^5
  • 1 <= arr[i] <= 10^9
  • 0 <= k <= arr.length
题解

统计每一个数出现的次数,然后以出现次数从小到大排序,最后模拟删除次数少的即可。

时间复杂度:\(O(n\log n)\)

class Solution {
public:
    int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
        map<int, int> s;
        for(auto num : arr) s[num]++;
        vector<pair<int, int>> nums;
        for(auto x : s) nums.push_back({x.second, x.first});
        sort(nums.begin(), nums.end());
        for(int i = 0; i < nums.size(); i++) {
            if(nums[i].first <= k) k -= nums[i].first;
            else return nums.size() - i;
        }
        return 0;
    }
};

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

给你一个整数数组 bloomDay,以及两个整数 mk

现需要制作 m 束花。制作花束时,需要使用花园中 相邻的 k 朵花

花园中有 n 朵花,第 i 朵花会在 bloomDay[i] 时盛开,恰好 可以用于 一束 花中。

请你返回从花园中摘 m 束花需要等待的最少的天数。如果不能摘到 m 束花则返回 -1

示例 1:

输入:bloomDay = [1,10,3,10,2], m = 3, k = 1
输出:3
解释:让我们一起观察这三天的花开过程,x 表示花开,而 _ 表示花还未开。
现在需要制作 3 束花,每束只需要 1 朵。
1 天后:[x, _, _, _, _]   // 只能制作 1 束花
2 天后:[x, _, _, _, x]   // 只能制作 2 束花
3 天后:[x, _, x, _, x]   // 可以制作 3 束花,答案为 3

示例 2:

输入:bloomDay = [1,10,3,10,2], m = 3, k = 2
输出:-1
解释:要制作 3 束花,每束需要 2 朵花,也就是一共需要 6 朵花。而花园中只有 5 朵花,无法满足制作要求,返回 -1 。

示例 3:

输入:bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3
输出:12
解释:要制作 2 束花,每束需要 3 朵。
花园在 7 天后和 12 天后的情况如下:
7 天后:[x, x, x, x, _, x, x]
可以用前 3 朵盛开的花制作第一束花。但不能使用后 3 朵盛开的花,因为它们不相邻。
12 天后:[x, x, x, x, x, x, x]
显然,我们可以用不同的方式制作两束花。

示例 4:

输入:bloomDay = [1000000000,1000000000], m = 1, k = 1
输出:1000000000
解释:需要等 1000000000 天才能采到花来制作花束

示例 5:

输入:bloomDay = [1,10,2,9,3,8,4,7,5,6], m = 4, k = 2
输出:9

提示:

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

答案具有单调性,答案天数之后的天数也可以。

二分答案,当确定第几天时,可以枚举判断是否能拿出 m 束花。

时间复杂度:\(O(n\log m)\)

class Solution {
public:
    int check(vector<int>& bloomDay, int key, int k) {
        int total = 0, len = 0;
        for(auto day : bloomDay) {
            if(key >= day) {
                if(++len == k) {
                    total++;
                    len = 0;
                }
            } else len = 0;
        }
        return total;
    }
    int minDays(vector<int>& bloomDay, int m, int k) {
        vector<int> days;
        for(auto day : bloomDay) days.push_back(day);
        sort(days.begin(), days.end());
        int n = unique(days.begin(), days.end()) - days.begin();
        int lef = 0, rig = n - 1, mid, total, len;
        while(lef < rig) {
            mid = lef + rig >> 1;
            if(m <= check(bloomDay, days[mid], k)) rig = mid;
            else lef = mid + 1;
        }
        if(check(bloomDay, days[rig], k) < m) return -1;
        else return days[rig];
    }
};

树节点的第 K 个祖先

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

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

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

示例:

输入:
["TreeAncestor","getKthAncestor","getKthAncestor","getKthAncestor"]
[[7,[-1,0,0,1,1,2,2]],[3,1],[5,2],[6,3]]

输出:
[null,1,0,-1]

解释: 
TreeAncestor treeAncestor = new TreeAncestor(7, [-1, 0, 0, 1, 1, 2, 2]);
 treeAncestor.getKthAncestor(3, 1); // 返回 1 ,它是 3 的父节点 
treeAncestor.getKthAncestor(5, 2); // 返回 0 ,它是 5 的祖父节点 
treeAncestor.getKthAncestor(6, 3); // 返回 -1 因为不存在满足要求的祖先节点

提示:

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

倍增(ST表)模板题。

设 \(st_{x,k}\) 为树节点 x 上跳 \(2^k\) 个节点跳到的祖先节点。

有转移方程:\(st_{x,k}=st_{y,k-1}\),其中 \(y=st_{x,k-1}\)。

时间复杂度:\(O(n\log n)\)

class TreeAncestor {
public:
    vector<vector<int>> dp;

    TreeAncestor(int n, vector<int>& parent) {
        dp = vector<vector<int>> (n, vector<int> ((int)log2(n) + 1));
        for(int i = 0; i < n; i++) dp[i][0] = parent[i];
        for(int k = 1; k <= log2(n); k++) {
            for(int x = 0; x < n; x++) {
                if(dp[x][k - 1] == -1) dp[x][k] = -1;
                else dp[x][k] = dp[dp[x][k - 1]][k - 1];
            }
        }
    }
    
    int getKthAncestor(int node, int k) {
        int t = log2(k);
        for(int i = 0; i <= t && node != -1; i++) {
            if((k & (1 << i)) == 0) continue;
            node = dp[node][i];
        }
        return node;
    }
};

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

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注