系列目录
88.合并两个有序数组
52.螺旋数组
567.字符串的排列
643.子数组最大平均数
150.逆波兰表达式
61.旋转链表
160.相交链表
83.删除排序链表中的重复元素
389.找不同
1491.去掉最低工资和最高工资后的工资平均值
896.单调序列
206.反转链表
92.反转链表II
141.环形链表
142.环型链表
目录
- 系列目录
- 1491. 去掉最低工资和最高工资后的工资平均值
- 方法一
- 方法二
- 896. 单调数列
- 方法一
- 方法二
- STL库
1491. 去掉最低工资和最高工资后的工资平均值
🌟数组+数学
原题链接
C++
若未特殊标明，以下题解均写用C++
- 在C++20之前，如果你想实现一个
reduce函数，可以编写或使用第三方库(如：Boost、STL的扩展) - 下面是一个简单的
reduce函数的实现，它使用std::accumulate算法来累加容器中的元素：
#include <numeric> // for std::accumulate
#include <vector>
template<typename T, typename Iter>
T reduce(Iter begin, Iter end) {
return std::accumulate(begin, end, T());
}
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
int sum = reduce(vec.begin(), vec.end());
// sum will be 15
return 0;
}
- 在C++中，
ranges::min()函数是C++20引入的一个标准库函数，用于在一个范围内找到最小值
示例：
#include <iostream>
#include <vector>
#include <ranges>
using namespace std;
int main() {
vector<int> v = {4, 2, 9, 3, 5};
// 使用ranges::min查找并打印最小元素
auto min_value = ranges::min(v);
cout << "The minimum value is: " << min_value << '\n';
// 你也可以使用begin()和end()迭代器
auto min_value_iter = ranges::min(v.begin(), v.end());
cout << "The iterator to the minimum value is: " << distance(v.begin(), min_value_iter) << '\n';
return 0;
}
方法一
auto+ranges::minmax
// 这里的 minmax不能颠倒
class Solution {
public:
double average(vector<int>& salary) {
int s = reduce(salary.begin(), salary.end());
auto [m, M] = ranges::minmax(salary);
// 注意这里的double
return (double) (s - m - M) / (salary.size() - 2);
}
};
方法二
模拟
class Solution {
public:
double average(vector<int>& salary) {
sort(salary.begin(), salary.end());
int n = salary.size();
// 注意这里是浮点数
double sum = 0;
// 这里n的上限为n-2，n-2-1+1=n-2
for (int i = 1; i < n - 1; i ++)
sum += salary[i];
return sum / (n - 2);
}
};
小试牛刀，再一起看看下面这道题吧～
896. 单调数列
🌟数组+数学
原题链接
方法一
class Solution {
public:
bool isMonotonic(vector<int>& nums) {
bool is_increase = true, is_decrease = true;
int n = nums.size();
// 为什么这里是 n-1而不是n——有i+1
for (int i = 0; i < n - 1; i ++) {
if (nums[i] < nums[i + 1])
is_decrease = false;
if (nums[i] > nums[i + 1])
is_increase = false;
}
// 或运算——与之对应的且运算——&&
return is_increase || is_decrease;
}
};
is_sorted()函数
本身不会像sort函数一样，对数组进行排序，只判断是否已经是升序排序
rbegin()函数
c.begin() 返回一个迭代器，它指向容器c的第一个元素
c.end() 返回一个迭代器，它指向容器c的最后一个元素的下一个位置
c.rbegin() 返回一个逆序迭代器，它指向容器c的最后一个元素
c.rend() 返回一个逆序迭代器，它指向容器c的第一个元素前面的位置
在C++中，rbegin()是一个成员函数，用于获取指向容器( 如vector、list、deque、array等)最后一个元素的反向迭代器
反向迭代器是一种特殊的迭代器，它按照与正常迭代器相反的方向遍历容器
当你调用rbegin()时，它返回一个指向容器最后一个元素的反向迭代器
这意味着当你使用++操作符递增这个反向迭代器时，它实际上会向前移动到容器的上一个元素，而不是向后 同样，当你使用--操作符递减反向迭代器时，它会向后移动到容器的下一个元素
示例：
#include <iostream>
#include <vector>
using namespace
int main() {
vector<int> v = {1, 2, 3, 4, 5};
// 使用rbegin()获取指向容器最后一个元素的反向迭代器
auto rit = v.rbegin();
// 使用反向迭代器遍历容器
for (; rit != v.rend(); rit ++) {
cout << *rit << ' '; // 输出：5 4 3 2 1
}
cout << '\n';
return 0;
}
在这个示例中，我们创建了一个包含五个整数的vector 然后，我们使用rbegin()获取一个指向容器最后一个元素的反向迭代器，并使用这个迭代器遍历容器，从后向前输出元素
注意，我们使用v.rend()作为循环的结束条件，rend()返回一个表示反向迭代器“尾后”位置的反向迭代器
方法二
// 两次遍历——“检查”🧐
// 调用STL库里的 is_sorted()函数 检查向量是否为升序或降序排列
class Solution {
public:
bool isMonotonic(vector<int>& nums) {
return is_sorted(nums.begin(), nums.end()) || is_sorted(nums.rbegin(), nums.rend());
}
};
STL库
在C++中，**STL(Standard Template Library，标准模板库)**是一个包含大量通用模板类和函数的库，这些模板类和函数用于处理各种常见的数据结构和算法STL是C++标准库的一部分，由ISO C++标准委员会制定，并包含在其中
STL的设计理念是“泛型编程”(generic programming)，即编写可以处理多种数据类型的代码通过使用模板和迭代器，STL能够实现这种泛型编程的目标，使得C++代码更加灵活、可重用和易于维护
STL的应用：
- 提供大量的容器(containers)，如
vector、list、deque(双端队列)、set、map等，用于存储和管理数据这些容器类都是模板类，可以存储任何类型的数据(只要该类型支持必要的操作，如：拷贝和赋值) - 包含一系列算法(algorithms)，用于处理存储在容器中的数据这些算法包括排序、查找、复制、替换等STL的算法都是高度通用的，并且不依赖于特定的数据结构，因此可以应用于任何支持STL迭代器(iterator)的容器
- 包含一些迭代器(iterator)，用于遍历和访问容器中的元素迭代器是一种设计模式，它提供了一种方法，用于遍历容器中的数据，而无需了解容器的底层实现细节STL的迭代器分为五类：输入迭代器、输出迭代器、前向迭代器、双向迭代器和随机访问迭代器
