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;
}
常用方法
（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 );
