LeetCode 刷题笔记

1. 20241218

（1）2447

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

#include <iostream>
#include <numeric> // std::gcd

int 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 = b
        b = a % b
        a = temp
    return a

function gcd_of_list(numbers):
    if numbers is empty:
        return 0
    result = 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()：获取队列中元素的数量。