LeetCode 刷题笔记

LeetCode 刷题笔记

1. 20241218

（1）2447

std::gcd是C++17引入的一个函数，用于计算两个整数的最大公因数。位于<numeric>头文件中。

#include <iostream>
#include <numeric> // std::gcdint main() {int a = 36;int b = 60;// 计算两个整数的最大公因数int gcd = std::gcd(a, b);// 输出最大公因数std::cout << "The GCD of " << a << " and " << b << " is: " << gcd << std::endl;return 0;
}

计算一组数的最大公因数

function gcd(a, b):while b ≠ 0:temp = bb = a % ba = tempreturn afunction gcd_of_list(numbers):if numbers is empty:return 0result = numbers[0]for i from 1 to length(numbers) - 1:result = gcd(result, numbers[i])return result// 示例使用
numbers = [24, 36, 48, 60]
result = gcd_of_list(numbers)
print("The GCD of the given numbers is: " + result)

（2）3319

在C++中，可以使用标准库中的std::priority_queue来实现最大堆和最小堆。默认情况下，std::priority_queue是一个最大堆，但能够通过指定比较函数来实现最小堆。

最大堆

#include <iostream>
#include <queue>
#include <vector>int main() {// 创建一个优先队列（最大堆）std::priority_queue<int> maxHeap;// 向堆中添加元素maxHeap.push(10);maxHeap.push(20);maxHeap.push(30);maxHeap.push(5);maxHeap.push(15);// 输出堆顶元素std::cout << "Top element: " << maxHeap.top() << std::endl;// 输出并移除堆中的所有元素std::cout << "Elements in the max heap: ";while (!maxHeap.empty()) {std::cout << maxHeap.top() << " "; // 获取堆顶元素maxHeap.pop(); // 移除堆顶元素}std::cout << std::endl;return 0;
}

最小堆

#include <iostream>
#include <queue>
#include <vector>
#include <functional>int main() {// 创建一个优先队列（最小堆）std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;// 向堆中添加元素minHeap.push(10);minHeap.push(20);minHeap.push(30);minHeap.push(5);minHeap.push(15);// 输出堆顶元素std::cout << "Top element: " << minHeap.top() << std::endl;// 输出并移除堆中的所有元素std::cout << "Elements in the min heap: ";while (!minHeap.empty()) {std::cout << minHeap.top() << " "; // 获取堆顶元素minHeap.pop(); // 移除堆顶元素}std::cout << std::endl;return 0;
}

自定义比较器

#include <iostream>
#include <queue>
#include <vector>struct Compare {bool operator()(const std::pair<int, int>& a, const std::pair<int, int>& b) {return a.second > b.second; // 按第二个元素从小到大排序}
};int main() {std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, Compare> pq;pq.push({1, 10});pq.push({2, 5});pq.push({3, 20});while (!pq.empty()) {auto top = pq.top();std::cout << "(" << top.first << ", " << top.second << ") ";pq.pop();}// 输出：(2, 5) (1, 10) (3, 20)return 0;
}

#include <iostream>
#include <queue>
#include <vector>int main() {auto compare = [](int a, int b) {return a > b; // 小顶堆};std::priority_queue<int, std::vector<int>, decltype(compare)> pq(compare);pq.push(10);pq.push(5);pq.push(20);while (!pq.empty()) {std::cout << pq.top() << " "; // 输出：5 10 20pq.pop();}return 0;
}

常用方法

（1）push(const T& value)：向堆中添加元素
（2）pop()：移除堆顶元素
（3）top()：获取堆顶元素
（4）empty()：检查堆是否为空
（5）size()：获取堆中元素的数量

（3）2316

std::queue 是 C++ 标准库中的一个容器适配器，用于实现先进先出（FIFO）的数据结构。

常用方法

（1）构造函数：
queue()：创建一个空的队列。
queue(const Container &cont)：使用给定的容器创建队列。
queue(const queue &other)：拷贝构造函数。
（2）push(const T& value)：向队列的末尾添加元素。
（3）pop()：移除队列的第一个元素。
（4）front()：获取队列的第一个元素。
（5）back()：获取队列的最后一个元素。
（6）empty()：检查队列是否为空。
（7）size()：获取队列中元素的数量。

2. 20241219

（1）1300

二分查找
在 C++ 标准库中，相关的函数主要有 std::lower_bound 、std::upper_bound、std::equal_range 和 std::binary_search。这些函数都位于 <algorithm> 头文件中，并且用于在已排序的范围内进行查找操作。

// 返回一个迭代器，指向第一个大于value的元素
// 如果所有元素都不大于value, 则返回last
// 使用 std::upper_bound 的前提是容器中的元素必须是已排序的。如果容器未排序，结果将是未定义的。
template< class ForwardIt, class T >
ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value );

// 返回一个迭代器，指向第一个不小于 value 的元素
// 如果所有元素都小于 value，则返回 last
// 使用 std::lower_bound 的前提是容器中的元素必须是已排序的。如果容器未排序，结果将是未定义的
template< class ForwardIt, class T >
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value );

// 返回一个 std::pair 对象，包含两个迭代器：
// first：指向第一个不小于 value 的元素。
// second：指向第一个大于 value 的元素。
// 使用 std::equal_range 的前提是容器中的元素必须是已排序的。如果容器未排序，结果将是未定义的。
template< class ForwardIt, class T >
std::pair<ForwardIt, ForwardIt> equal_range( ForwardIt first, ForwardIt last, const T& value );

// 如果在范围内找到等于 value 的元素，则返回 true；否则返回 false
template< class ForwardIt, class T >
bool binary_search( ForwardIt first, ForwardIt last, const T& value );

3. 20241222

（1）3286

std::list 是 C++ 标准模板库（STL）中的一个容器，提供了双向链表的实现。它允许高效地插入和删除元素，但在随机访问性能上不如 std::vector。
特性
（1）双向链表：
每个节点都包含一个数据和两个指针，分别指向前一个节点和后一个节点。
插入、删除操作的时间复杂度为 O(1)。
（2）动态大小：
自动调整大小，不需要手动管理内存。
（3）不支持随机访问：
使用迭代器遍历元素，但不支持 [] 运算符。
（4）稳定性：
在插入和删除操作后，迭代器和引用仍然有效。

常用操作
以下是一些常用的 std::list 成员函数：
（1）构造函数

std::list<int> l1;                  // 默认构造，空列表
std::list<int> l2(5, 10);           // 初始化 5 个值为 10 的元素
std::list<int> l3(l2.begin(), l2.end()); // 用迭代器范围初始化

（2）插入和删除

l1.push_back(1);    // 在尾部插入
l1.push_front(0);   // 在头部插入
l1.pop_back();      // 删除尾部元素
l1.pop_front();     // 删除头部元素
l1.insert(l1.begin(), 20); // 在指定位置插入
l1.erase(l1.begin());      // 删除指定位置的元素
l1.clear();        // 清空列表

（3）访问元素

l1.front();  // 返回头部元素
l1.back();   // 返回尾部元素

（4）大小相关

l1.empty();      // 检查列表是否为空
l1.size();       // 返回元素个数

（5）排序和反转

l1.sort();       // 排序，默认按升序
l1.reverse();    // 反转列表

（6）合并和去重

l1.merge(l2);     // 合并两个已排序列表
l1.unique();      // 删除相邻的重复元素

适用场景
需要频繁插入或删除操作的场景。
不需要随机访问时。
数据大小动态变化频繁时。