408算法题leetcode--第一天

参考

• 参考题单

1523. 在区间范围内统计奇数数目

• 1523. 在区间范围内统计奇数数目
• 思路：数据量有$10^9$，所以遍历求解会超时；而(low, high)区间中的奇数 = (0, high) - (0, low - 1)的奇数
• 时间和空间复杂度：O(1)

class Solution {
public:int countOdds(int low, int high) {return (high + 1) / 2 - low / 2;}
};

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

• 1491. 去掉最低工资和最高工资后的工资平均值
• 遍历即可
• 时间复杂度：O(n)；空间：O(1)

class Solution {
public:double average(vector<int>& salary) {double ret = 0;int max_v = 0, min_v = 1e7;for(auto i : salary){ret += i;max_v = max(max_v, i);min_v = min(min_v, i);}ret = ret - max_v - min_v;return ret / (salary.size() - 2);}
};