On the shoulders of giants.

biweekly-contest-29

去掉最低工资和最高工资后的工资平均值

给你一个整数数组 salary ,数组里每个数都是 唯一 的,其中 salary[i] 是第 i 个员工的工资。

请你返回去掉最低工资和最高工资以后,剩下员工工资的平均值。

示例 1:

输入:salary = [4000,3000,1000,2000]
输出:2500.00000
解释:最低工资和最高工资分别是 1000 和 4000 。
去掉最低工资和最高工资以后的平均工资是 (2000+3000)/2= 2500

示例 2:

输入:salary = [1000,2000,3000]
输出:2000.00000
解释:最低工资和最高工资分别是 1000 和 3000 。
去掉最低工资和最高工资以后的平均工资是 (2000)/1= 2000

示例 3:

输入:salary = [6000,5000,4000,3000,2000,1000]
输出:3500.00000

示例 4:

输入:salary = [8000,9000,2000,3000,6000,1000]
输出:4750.00000

提示:

  • 3 <= salary.length <= 100
  • 10^3 <= salary[i] <= 10^6
  • salary[i] 是唯一的。
  • 与真实值误差在 10^-5 以内的结果都将视为正确答案。
题解

直接模拟。

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

class Solution {
public:
    double average(vector<int>& salary) {
        int min_salary, max_salary, sum = 0;
        min_salary = max_salary = salary[0];
        for(auto num : salary) {
            sum += num;
            min_salary = min(min_salary, num);
            max_salary = max(max_salary, num);
        }
        return double(sum - min_salary - max_salary) / (salary.size() - 2);
    }
};

n 的第 k 个因子

给你两个正整数 n 和 k 。

如果正整数 i 满足 n % i == 0 ,那么我们就说正整数 i 是整数 n 的因子。

考虑整数 n 的所有因子,将它们 升序排列 。请你返回第 k 个因子。如果 n 的因子数少于 k ,请你返回 -1 。

示例 1:

输入:n = 12, k = 3
输出:3
解释:因子列表包括 [1, 2, 3, 4, 6, 12],第 3 个因子是 3 。

示例 2:

输入:n = 7, k = 2
输出:7
解释:因子列表包括 [1, 7] ,第 2 个因子是 7 。

示例 3:

输入:n = 4, k = 4
输出:-1
解释:因子列表包括 [1, 2, 4] ,只有 3 个因子,所以我们应该返回 -1 。

示例 4:

输入:n = 1, k = 1
输出:1
解释:因子列表包括 [1] ,第 1 个因子为 1 。

示例 5:

输入:n = 1000, k = 3
输出:4
解释:因子列表包括 [1, 2, 4, 5, 8, 10, 20, 25, 40, 50, 100, 125, 200, 250, 500, 1000] 。

提示:

  • 1 <= k <= n <= 1000
题解

直接模拟,找出第 k 个因子。

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

class Solution {
public:
    int kthFactor(int n, int k) {
        for(int i = 1; i <= n; i++) {
            if(n % i == 0 && --k == 0)
                return i;
        }
        return -1;
    }
};

删掉一个元素以后全为 1 的最长子数组

给你一个二进制数组 nums ,你需要从中删掉一个元素。

请你在删掉元素的结果数组中,返回最长的且只包含 1 的非空子数组的长度。

如果不存在这样的子数组,请返回 0 。

提示 1:

输入:nums = [1,1,0,1]
输出:3
解释:删掉位置 2 的数后,[1,1,1] 包含 3 个 1 。

示例 2:

输入:nums = [0,1,1,1,0,1,1,0,1]
输出:5
解释:删掉位置 4 的数字后,[0,1,1,1,1,1,0,1] 的最长全 1 子数组为 [1,1,1,1,1] 。

示例 3:

输入:nums = [1,1,1]
输出:2
解释:你必须要删除一个元素。

示例 4:

输入:nums = [1,1,0,0,1,1,1,0,1]
输出:4

示例 5:

输入:nums = [0,0,0]
输出:0

提示:

  • 1 <= nums.length <= 10^5
  • nums[i] 要么是 0 要么是 1
题解

模拟即可,找出每一段连续 1 的长度,隔开一个 0 的可以删除。

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

class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int per_len = 0, nex_len, n = nums.size();
        int record = 0, result = 0, flag = 0;
        for(int i = 0; i < n; i++) {
            if(nums[i] == 0) flag++;
        }
        if(flag == 0) return n - 1;
        for(int i = 0; i < n; i++) {
            while(i < n && nums[i] != 1) i++;
            int j = i;
            while(i < n && nums[i] != 0) i++;
            nex_len = i - j;
            record = max(record, nex_len);
            if(per_len != 0) {
                result = max(result, per_len + nex_len);
            }
            if(i + 1 < n && nums[i + 1] == 0) per_len = 0;
            else per_len = nex_len;
        }
        return max(result, record);
    }
};

并行课程 II

给你一个整数 n 表示某所大学里课程的数目,编号为 1 到 n ,数组 dependencies 中, dependencies[i] = [xi, yi]  表示一个先修课的关系,也就是课程 xi 必须在课程 yi之前上。同时你还有一个整数 k 。

在一个学期中,你 最多 可以同时上 k 门课,前提是这些课的先修课在之前的学期里已经上过了。

请你返回上完所有课最少需要多少个学期。题目保证一定存在一种上完所有课的方式。

示例 1:

输入:n = 4, dependencies = [[2,1],[3,1],[1,4]], k = 2
输出:3 
解释:上图展示了题目输入的图。在第一个学期中,我们可以上课程 2 和课程 3 。然后第二个学期上课程 1 ,第三个学期上课程 4 。

示例 2:

输入:n = 5, dependencies = [[2,1],[3,1],[4,1],[1,5]], k = 2
输出:4 
解释:上图展示了题目输入的图。一个最优方案是:第一学期上课程 2 和 3,第二学期上课程 4 ,第三学期上课程 1 ,第四学期上课程 5 。

示例 3:

输入:n = 11, dependencies = [], k = 2
输出:6

提示:

  • 1 <= n <= 15
  • 1 <= k <= n
  • 0 <= dependencies.length <= n * (n-1) / 2
  • dependencies[i].length == 2
  • 1 <= xi, yi <= n
  • xi != yi
  • 所有先修关系都是不同的,也就是说 dependencies[i] != dependencies[j] 。
  • 题目输入的图是个有向无环图。
题解

动态规划(压状),设 \(dp_s\) 为完成状态为 s 的全部课程所需要的最小学期。

有转移方程( y 状态课程先修课程都完成):

  • 当 y 状态课程小于等于 k 时,\(dp_{i|y}=\min (dp_{i}+1)\)
  • 当 y 状态课程大于 k 时,\(dp_{i|x}=\min (dp_{i}+1)\),其中 \(x \subset y,count_x \leq k\)

时间复杂度:\(O(2^nn)\)

const int INF = 1E8;
class Solution {
public:
    int minNumberOfSemesters(int n, vector<vector<int>>& dependencies, int k) {
        int m = (1 << n);
        vector<int> count(m);
        for(int i = 0; i < m; i++) {
            int tmp = i;
            while(tmp) count[i]++, tmp -= (-tmp) & tmp;
        }
        vector<int> s(n), dp(m, INF);
        dp[0] = 0;
        for(auto edge : dependencies) {
            s[edge[1] - 1] |= 1 << (edge[0] - 1);
        }
        for(int i = 0; i < m; i++) {
            int y = 0;
            for(int j = 0; j < n; j++) {
                if(!(i >> j & 1) && (s[j] & i) == s[j]) y |= (1 << j);
            }
            if(count[y] <= k) dp[i | y] = min(dp[i | y], dp[i] + 1);
            else {
                for(int x = y; x != 0; x = (x - 1) & y) {
                    if(count[x] <= k) dp[i | x] = min(dp[i | x], dp[i] + 1);
                }
            }
        }
        return dp[m - 1];
    }
};
Share

You may also like...

发表评论

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