LeetCode.29场双周赛

距离回校还有18天,得多做(水)点题

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

给你一个整数数组salary ，数组里每个数都是 唯一 的，其中 salary[i]是第 i 个员工的工资。
请你返回去掉最低工资和最高工资以后，剩下员工工资的平均值。

分析

遍历一遍数组，找到最大值和最小值，并且求出工资和，结束后，按照题意计算即可

class Solution {
public:
    double average(vector<int>& salary) {
        int n = salary.size();
        int sum = 0;
        int minv = 1e7, maxv = 0;
        for(int i = 0; i<n; i++){
            minv = min(minv,salary[i]);
            maxv = max(maxv,salary[i]);
            sum += salary[i];
        }

        sum = sum - minv - maxv;
        return sum*1.0/(n-2);
    }
};

1492. n 的第 k 个因子

给你两个正整数 n 和 k 。
如果正整数 i 满足 n % i == 0，那么我们就说正整数 i 是整数 n 的因子。

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

分析

计算出n的所有因子并记录在数组中，按题意返回即可。

class Solution {
public:
    int kthFactor(int n, int k) {
        vector<int> ans;
        for(int i = 1; i<=n; i++){
            if(n%i == 0) ans.push_back(i);
        }
        int m = ans.size();
        return m>=k? ans[k-1]:-1;
    }
};

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

给你一个二进制数组 nums ，你需要从中删掉一个元素。
请你在删掉元素的结果数组中，返回最长的且只包含 1 的非空子数组的长度。
如果不存在这样的子数组，请返回 0 。

分析

题目要求我们求出删掉一个0之后最长的且只包含1的非空子数组，先不考虑这个0，假设我们现在只要求最长的只包含1的非空子数组的长度，可以利用双端队列，如果是1加到队尾，如果是0，从队头开始删除所有1，这样遍历数组，维护这个双端队列即可，用ans记录队列的最长长度，那么回到这题，不删0的话，那么0就在1之间，那我们只需要保证双端队列最多只存在一个0就行了，如果再遇到0，就删掉上一个0之前的所有数字。

class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int n = nums.size();
        int ans = 0;
        deque<int> q;
        int f = 0;   //f == 0表示现在队列中只存在一个0
        for(int i = 0; i<n; i++){
            if(!nums[i]){
                if(!f) {
                    q.push_back(0);  //如果当前队列中没有0，则这个0可以入队
                    f = 1;   //标记
                }
                else {
                    while(q.front() != 0) q.pop_front();  //否则，将前一个0删除
                    q.push_back(0);
                    q.pop_front();
                }
            }else
                q.push_back(1);
            ans = max(ans,(int)q.size()-1);
        }
        return ans;
    }
};

1494. 并行课程 II

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

在一个学期中，你 最多 可以同时上 k 门课，前提是这些课的先修课在之前的学期里已经上过了。
请你返回上完所有课最少需要多少个学期。题目保证一定存在一种上完所有课的方式。

分析

一开始我觉得就是单纯按拓扑序就行了，不过越做越麻烦，就放弃了
还是DPnb，看来不学好DP是不可能ak周赛的。
这题也是参考y总的解法，用二进制表示状态，状态转移方程：
f[i | now] = min(f[i | now], f[i] + 1);

class Solution {
public:
    vector<int> f;
    const int inf = 1024;
    int minNumberOfSemesters(int n, vector<vector<int>>& dependencies, int k) {
        f = vector<int> (1<<n,inf);
        f[0] = 0;
        for(auto &x:dependencies) x[0]--,x[1]--;  //编号从0开始
        for(int i = 0; i<1<<n; i++){
            vector<bool> st(n);  //标记该学期是否可以选修此门课
            for(auto& x:dependencies){
                int a = x[0], b = x[1];
                if(!(i>>a&1))
                    st[b] = true;  //如果当前没选b的先修课a，则标记b不可选
            }

            int state = 0;
            for(int j = 0; j<n; j++){
                if(!st[j] && !(i>>j&1))  //如果这门课可选且还没选，那么选上
                    state += 1<<j;
            }

            dfs(n,k,i,state,0,0);
        }
        return f[(1<<n)-1];
    }
    void dfs(int n,int k,int i,int state,int now,int start){
            if(!k || !state){
                f[i | now] = min(f[i | now], f[i] + 1);
                return ;
            }
            for(int j = start; j<n; j++){
                if(state>>j&1)
                    dfs(n,k-1,i,state-(1<<j),now+(1<<j),j+1);
            }
        }
};