LeetCode：经典题之1491、896 题解与延伸

系列目录

88.合并两个有序数组
52.螺旋数组
567.字符串的排列
643.子数组最大平均数
150.逆波兰表达式
61.旋转链表
160.相交链表
83.删除排序链表中的重复元素
389.找不同
1491.去掉最低工资和最高工资后的工资平均值
896.单调序列
206.反转链表
92.反转链表II
141.环形链表
142.环型链表

---

---

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);// 注意这里的doublereturn (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-2for (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+1for (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 namespaceint 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的迭代器分为五类：输入迭代器、输出迭代器、前向迭代器、双向迭代器和随机访问迭代器