leetcode 1766

题目

在这里插入图片描述

例子

在这里插入图片描述

思路

将边的关系，转化为树结构。
记录val 对应的id 列表。
记录是否遍历过节点。
记录id 和对应的深度。

使用dfs，从根开始遍历。

代码实现

class Solution {
private:
    vector<vector<int>> gcds;

    //val : the id of nodes matching the val 
    vector<vector<int>> val_to_id;
    // i-th node : parent and childern of i-th node
    vector<vector<int>> graph;
    //i-th node : depth of i-th node
    vector<int> dep;
    //i-th node : ans of i-th node
    vector<int> ans;

public:

    void dfs(vector<int>& nums, int id, int depth){
        dep[id] = depth;

        for(int val : gcds[nums[id]]){
            if(val_to_id[val].empty()){
                //dfs 当前深度，找不到对应的gcd的值
                continue;
            }else{
                //获取已经遍历的节点的val的对应的id, 从根开始记录val_to_id的列表，所以back应该是最近的节点。
                int last_id = val_to_id[val].back();
                if(ans[id] == -1 || dep[last_id] > dep[ans[id]]){
                    ans[id] = last_id;
                }
            }
        }

        val_to_id[nums[id]].push_back(id);

        for(int child_id : graph[id]){
            //等于-1没有遍历过
            if(dep[child_id] == -1){
                dfs(nums, child_id, depth +1);
            }
        }

        val_to_id[nums[id]].pop_back();


    }

    vector<int> getCoprimes(vector<int>& nums, vector<vector<int>>& edges) {
        int n = nums.size();

        gcds.resize(51);
        val_to_id.resize(51);

        ans.resize(n, -1);
        dep.resize(n, -1);
        graph.resize(n);

        for(int i=1; i<= 50; i++){
            for(int j=1; j<= 50; j++){
                if(gcd(i,j) == 1){
                    gcds[i].push_back(j);
                }
            }
        }

        for(const auto& val : edges){
            // 无向图，根据dep[id] 是否为-1, 判断是否遍历
            graph[val[0]].push_back(val[1]);
            graph[val[1]].push_back(val[0]);
        }

        dfs(nums, 0, 1);

        return ans;
    }
};

push_back 和 pop_back

push_back() 和 pop_back() 是 std::vector 容器类提供的两个重要成员函数，用于向向量尾部添加元素和删除尾部元素。

`push_back()`

push_back() 函数用于在 vector 的末尾添加一个新元素。它将新元素插入到向量的尾部，使得向量的大小增加 1。语法如下：

void push_back(const T& value);
void push_back(T&& value);

其中，value 是要添加到向量末尾的元素。如果 vector 的存储空间不足以容纳新元素，push_back() 函数会自动重新分配更大的存储空间，并将元素添加到向量的末尾。示例如下：

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec;

    // 添加元素到向量尾部
    vec.push_back(10);
    vec.push_back(20);
    vec.push_back(30);

    // 打印向量的元素
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

输出为：

10 20 30

`pop_back()`

pop_back() 函数用于删除 vector 的末尾元素，减小向量的大小。它不会返回任何值。如果 vector 不为空，则会删除最后一个元素；如果 vector 为空，则调用 pop_back() 函数会导致未定义行为。语法如下：

void pop_back();

示例：

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec = {10, 20, 30};

    // 删除向量的最后一个元素
    vec.pop_back();

    // 打印向量的元素
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

输出为：

10 20

在使用 pop_back() 函数之前，通常应该检查 vector 是否为空，以避免未定义行为。

这些函数是 std::vector 容器类的基本操作之一，非常常用于动态管理序列的大小和内容。

容器

在 C++ 中，容器是用来存储和管理一组对象的数据结构。标准模板库（STL）提供了多种容器，每种容器都有自己的特点和适用场景。以下是 C++ 中常用的几种容器：

Vector（向量）：
- 动态数组，大小可以动态增长。
- 支持快速随机访问。
- 在尾部插入元素的开销低，但在中间或头部插入元素的开销较高。
- 适合需要频繁对尾部进行插入和删除操作的场景。
Deque（双端队列）：
- 双端队列，支持在两端高效地进行插入和删除操作。
- 比向量更适合在两端进行频繁的插入和删除操作。
List（链表）：
- 双向链表，支持在任意位置高效地进行插入和删除操作。
- 不支持随机访问，访问元素的时间复杂度为 O(n)，而在头部和尾部插入和删除元素的时间复杂度为 O(1)。
Forward List（前向链表）：
- 单向链表，与双向链表相比，每个节点只保存下一个节点的地址。
- 支持在链表头部高效地进行插入和删除操作，但不支持在链表尾部直接访问。
Stack（栈）：
- 后进先出（LIFO）的数据结构，只允许在栈顶进行插入和删除操作。
- 基于向量或双端队列实现。
Queue（队列）：
- 先进先出（FIFO）的数据结构，只允许在队尾插入元素，在队头删除元素。
- 基于双端队列实现。
Priority Queue（优先队列）：
- 元素按照一定的优先级顺序排列，每次取出优先级最高的元素。
- 基于堆（heap）实现。
Set（集合）：
- 不重复元素的集合，通常基于红黑树实现。
- 支持高效的插入、删除和查找操作，元素按照升序排序。
Multiset（多重集合）：
- 允许重复元素的集合，通常基于红黑树实现。
- 元素按照升序排序。
Map（映射）：
- 键值对的集合，每个键唯一对应一个值。
- 支持高效的插入、删除和查找操作，键按照升序排序。
Multimap（多重映射）：
- 键可以重复的映射。
- 键按照升序排序。

这些容器都位于标准命名空间 std 中，可以通过包含相应的头文件来使用它们，例如 <vector>、<list>、<stack> 等。每种容器都有自己的优势和适用场景，选择合适的容器取决于具体的需求和性能要求。

push_back 函数

void push_back(const T& value);：这个函数接受一个常量引用作为参数。当调用这个函数时，它会复制参数 value 的值，并将这个值添加到容器的末尾。这意味着在函数调用过程中会发生数据的复制操作，因为它是通过常量引用传递的，所以不会改变传递给函数的实参。
```
std::vector<int> vec;
int x = 10;
vec.push_back(x); // 使用常量引用版本，复制 x 的值到容器
```
void push_back(T&& value);：这个函数接受一个右值引用作为参数。当调用这个函数时，它会使用参数 value 的值，并将其添加到容器的末尾。这个版本的函数通常用于移动语义，它不会复制参数的值，而是窃取参数的资源（例如，移动对象的所有权），因此更高效。
```
std::vector<std::string> vec;
std::string str = "Hello";
vec.push_back(std::move(str)); // 使用右值引用版本，窃取 str 的资源到容器
```

下面是两个版本的使用示例：

#include <iostream>
#include <vector>
#include <string>

int main() {
    // 使用常量引用版本
    std::vector<int> vec1;
    int x = 10;
    vec1.push_back(x); // 复制 x 的值到容器
    std::cout << "vec1 size: " << vec1.size() << std::endl;

    // 使用右值引用版本
    std::vector<std::string> vec2;
    std::string str = "Hello";
    vec2.push_back(std::move(str)); // 窃取 str 的资源到容器
    std::cout << "vec2 size: " << vec2.size() << std::endl;

    return 0;
}

在这个例子中，push_back(const T& value) 将会复制 x 的值到容器 vec1 中，而 push_back(T&& value) 则会窃取 str 的资源到容器 vec2 中。

引用

在 C++ 中，引用与传递地址有些相似，但并不完全等同。引用本质上是一个别名，它是被绑定到另一个对象或变量上的名称。当你使用引用时，实际上是在操作原始对象，而不是它的地址。

与传递地址不同的是，引用不需要进行解引用操作（使用指针时需要使用解引用操作符 *），因为引用本身就是原始对象的别名，所以操作起来更加直观和方便。

另外，使用引用传递参数时，不会涉及指针的语法，从而减少了一些错误的可能性，例如空指针引用等。同时，引用在编译期间会进行类型检查，从而提供了更强的类型安全性。

因此，虽然引用有些类似于传递地址的概念，但它们之间有着明显的区别。

引用传递是一种在函数参数中使用引用的机制，允许函数直接访问并修改调用者提供的变量。通过引用传递，可以避免复制大型对象，提高程序的性能并减少内存使用。

在C++中，引用传递通常通过引用参数实现，有两种类型的引用参数：

左值引用（Lvalue Reference）：通过使用 & 符号声明的引用类型。左值引用可以绑定到具有名称的变量，包括对象、数组、函数等。在函数中修改左值引用的值会影响到调用者提供的原始变量。
```
void modifyValue(int& x) {
    x += 10;
}

int main() {
    int num = 5;
    modifyValue(num);
    std::cout << "Modified value: " << num << std::endl; // 输出 15
    return 0;
}
```
右值引用（Rvalue Reference）：通过使用 && 符号声明的引用类型。右值引用通常用于移动语义，允许将资源（如临时对象）的所有权从一个对象转移给另一个对象。
```
void modifyValue(int&& x) {
    x += 10;
}

int main() {
    modifyValue(5); // 临时对象的所有权转移给函数
    return 0;
}
```

引用传递相比于值传递有以下优点：

避免对象的复制：使用引用传递可以避免复制大型对象，从而提高程序的性能和效率。
直接修改原始值：通过引用传递，函数可以直接修改调用者提供的变量的值，而无需返回值。

需要注意的是，引用传递可能会导致函数的行为不易理解，因为函数可以修改原始变量的值。因此，建议在使用引用传递时，对函数的行为进行良好的文档说明，以避免产生混淆。

左值和右值

在C++中，左值（lvalue）和右值（rvalue）是两种用于表示表达式的属性的术语。它们主要与对象的生命周期和可修改性相关联。

左值（Lvalue）：
- 左值是可以标识并且持久存在于内存中的表达式，通常具有名称或者可以取地址的表达式。
- 左值表达式可以出现在赋值语句的左边或者右边，因为它们代表着一个确定的内存位置。
- 例如，变量、数组元素、返回左值引用的函数等都是左值。
右值（Rvalue）：
- 右值是临时的、一次性的值，通常不具有名称或者不能被取地址。
- 右值表达式通常是在赋值语句的右边出现，它们表示的是一个临时的、无法被修改的值。
- 例如，常量、临时变量、返回右值引用的函数等都是右值。

在C++11引入的移动语义中，右值引用允许程序员将资源的所有权从一个对象转移给另一个对象，从而避免不必要的复制操作，提高了程序的性能和效率。

总的来说，左值表示具有名称和持久性的值，而右值表示临时的、一次性的值。右值引用允许有效地管理临时对象的生命周期和资源。

lambda 与引用

当使用 Lambda 表达式时，引用捕获允许在 Lambda 函数体内访问并修改外部作用域的变量。这对于需要在 Lambda 函数内部修改外部作用域变量的情况非常有用。以下是一个简单的 C++11 Lambda 表达式示例，展示了如何使用引用捕获：

#include <iostream>

int main() {
    int x = 10;

    // Lambda 表达式使用引用捕获外部变量 x
    auto lambda = [&x]() {
        // 在 Lambda 函数体内部访问和修改外部变量 x
        std::cout << "Inside lambda, x = " << x << std::endl;
        x += 5;
    };

    std::cout << "Before lambda, x = " << x << std::endl;

    // 调用 Lambda 函数
    lambda();

    std::cout << "After lambda, x = " << x << std::endl;

    return 0;
}

在这个示例中，Lambda 表达式 lambda 捕获了外部变量 x 的引用。Lambda 函数体内部可以访问和修改变量 x 的值。当调用 Lambda 函数后，会输出修改后的 x 值。

输出将会是：

Before lambda, x = 10
Inside lambda, x = 10
After lambda, x = 15

这里，在 Lambda 内部访问的 x 是外部的 x，并且通过引用捕获可以在 Lambda 内部修改外部的变量。

leetcode 1766

leetcode 1766

题目

例子

思路

代码实现

push_back 和 pop_back

push_back()

pop_back()

容器

push_back 函数

引用

左值和右值

lambda 与引用

相关推荐

最近更新

热门阅读

`push_back()`

`pop_back()`