正文索引 [隐藏]

传送门

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

签到题，直接写。

class Solution {
public:
    double average(vector<int>& salary) {
        int n = salary.size();
        double sum = 0;
        int ma = -INT_MAX, mi = INT_MAX;
        
        for(int i = 0; i < n; i++)
        {
            ma = max(ma, salary[i]);
            mi = min(mi, salary[i]);
            sum += salary[i];
        }
        
        sum -= (mi + ma);
        sum /= n - 2;
        
        return sum;
    }
};

T2 n 的第 k 个因子

维护n的因子数组arr，然后队尾就是答案。

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

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

题意很简单，去找一个最长的全1子串，这个子串中最多包含一个0。如果直接去写，可以用双指针，外层循环枚举左指针l，内层循环去枚举右指针r，在合法范围内尽量远地去推进r。最后答案就是最长的子串长度-1(去掉那个0)。这样做的复杂度最坏是O(n²)。

这里我采用的是O(n)的做法。

首先对串进行状态压缩，累加每个全1串，然后去枚举每一个0左右数字之和，找到最大的那个值，就是答案。

class Solution {
public:
    int longestSubarray(vector<int>& nums) {
    
    vector<int> arr;
	vector<int> pos;
	//状态压缩
	for(int i = 0; i < nums.size(); i++)
        {
            if(nums[i] == 1)
            {
                int tmp = 0;
                while(nums[i] == 1)
                {
                    tmp++;
                    i++;
                }
                i--;
                arr.push_back(tmp);
            }
            else
            {
                arr.push_back(0);
            }
        }
    //找到每个零的位置
    for(int i = 0; i < arr.size(); i++) 
		if(arr[i] == 0) 
			pos.push_back(i);
    //枚举左右和
    int maxn = -INT_MAX;
    for(int i = 0; i < pos.size(); i++)
	{
  	    if(pos[i] != 0 && pos[i] != arr.size() - 1)
        {
        	int tmp = arr[pos[i]-1] + arr[pos[i]+1];
            maxn = max(tmp, maxn);
        }
    }
    if(maxn == -INT_MAX) 
        return nums.size() - 1;
    return maxn;
    }
};