力扣 岛屿数量-200

岛屿数量-200

class Solution {//深度优先搜索 dfs
public:
    int vis[300][300] = {0};//用于标记的数组，标记是否遍历过
    int cnt = 0;//岛屿计数
    //上下左右的移动方向数组
    int dx[4]={-1,1,0,0};
    int dy[4]={0,0,-1,1};
    //深度优先搜索
    void dfs(vector<vector<char>>& grid,int x,int y)
    {
        for(int i=0;i<4;i++)
        {
            int bx = x+dx[i];
            int by = y+dy[i];
            //检查边界
            if(bx<0||bx>=grid.size()||by<0||by>=grid[0].size())continue;
            //检查是否被标记过（已经遍历过），当前位置的值是否为1，被标记过或者值为1就跳过
            if(vis[bx][by]||grid[bx][by]!='1')continue;
            //标记当前点为已经访问
            vis[bx][by]=1;
            //递归搜索相邻的格子
            dfs(grid,bx,by);
        }
    }
    int numIslands(vector<vector<char>>& grid) {
        //遍历数组
        for(int i=0;i<grid.size();i++)
        {
            for(int j=0;j<grid[0].size();j++)
            {
                //如果没有被标记过（为0），并且值为'1'
                if(!vis[i][j]&&grid[i][j]=='1')
                {
                    //岛屿计数加1
                    cnt++;
                    //当前元素标记为1表示已经访问过
                    vis[i][j]=1;
                    //深度优先搜索
                    dfs(grid,i,j);
                }
            }
        }
        return cnt;
    }
};

每日问题

右值引用和移动语义

右值引用和移动语义

在 C++11 中，引入了 右值引用 和 移动语义 这两个重要概念，它们主要用于优化性能，减少不必要的资源拷贝，尤其是在处理大对象时。理解这两个概念有助于写出更加高效的 C++ 代码。

1. 右值和左值

在讨论右值引用之前，我们需要先理解 左值 和 右值 的区别：

• 左值 (Lvalue)：指代内存中的某个位置，有持久性的，可以对其取地址。
  • 示例：变量、数组元素、解引用的指针等。
  • 例如：int a = 10; 中的 a 是左值。
• 右值 (Rvalue)：临时的、没有持久性的数据，不能取地址。通常是表达式计算的结果、常量、临时对象等。
  • 示例：a + b 或 func() 返回的临时对象。
  • 例如：int x = a + b; 中的 a + b 是右值。

左值 和 右值 的区分在 C++11 中变得更加重要，特别是在涉及到 右值引用 和 移动语义 时。

2. 右值引用（&&）

右值引用（&&）是 C++11 引入的新特性，它用于捕获 右值。与传统的 左值引用（&） 不同，右值引用是用来绑定 右值 的，目的是为了解决不必要的拷贝操作和资源的浪费。

右值引用的特点：

• 右值引用只能绑定 右值，而不能绑定左值。
• 右值引用使得对象的资源（如内存、文件句柄等）能够被 转移（move），而不是复制（拷贝）。

右值引用的声明：

int&& r = 5;  // 5 是右值，r 是右值引用

3. 移动语义

移动语义 允许资源从一个对象 转移（move） 到另一个对象，而不是复制资源。这通过右值引用实现，避免了昂贵的深拷贝操作，特别是在处理大型对象（如 std::vector、std::string）时，大大提高了性能。

关键概念：

• 移动构造函数：一个特殊的构造函数，它接收一个右值引用，并转移（而不是复制）其资源。
• 移动赋值运算符：与移动构造函数类似，它接收一个右值引用并转移资源。

例子：移动构造函数和移动赋值运算符

考虑一个自定义的类 MyClass，它管理一个动态分配的数组。我们希望能够利用 移动语义 来避免不必要的资源拷贝。

#include <iostream>
#include <cstring>

class MyClass {
private:
    char* data;

public:
    // 普通构造函数
    MyClass(const char* str) {
        data = new char[strlen(str) + 1];
        strcpy(data, str);
        std::cout << "Constructing: " << data << std::endl;
    }

    // 移动构造函数
    MyClass(MyClass&& other) noexcept {
        data = other.data;          // 转移所有权
        other.data = nullptr;       // 使其他对象处于有效的空状态
        std::cout << "Moving: " << data << std::endl;
    }

    // 移动赋值运算符
    MyClass& operator=(MyClass&& other) noexcept {
        if (this != &other) {
            delete[] data;         // 删除原来的资源
            data = other.data;     // 转移所有权
            other.data = nullptr;  // 使其他对象处于有效的空状态
        }
        std::cout << "Move Assigning: " << data << std::endl;
        return *this;
    }

    // 析构函数
    ~MyClass() {
        delete[] data;
        std::cout << "Destructing: " << (data ? data : "nullptr") << std::endl;
    }

    void print() const {
        std::cout << "Data: " << data << std::endl;
    }
};

int main() {
    MyClass obj1("Hello, World!");    // 使用普通构造函数
    MyClass obj2 = std::move(obj1);   // 使用移动构造函数

    obj2.print();                      // 输出 obj2 的数据
    // obj1 不再持有有效数据，因为它的资源已被转移
    obj1.print();                      // 输出 obj1 的数据（null）

    MyClass obj3("Temporary");
    obj3 = std::move(obj2);           // 使用移动赋值运算符

    return 0;
}

输出：

Constructing: Hello, World!
Moving: Hello, World!
Data: Hello, World!
Destructing: nullptr
Move Assigning: Hello, World!
Destructing: Temporary
Destructing: Hello, World!

4. 为什么使用移动语义？

移动语义的主要优点在于，它允许将资源的所有权从一个对象转移到另一个对象，而不是进行昂贵的复制操作。

性能优化：

在没有移动语义的情况下，当一个对象被复制时，通常需要执行深拷贝操作，这可能会消耗大量时间，尤其是对于包含大量数据的对象（如 std::vector、std::string）。但是使用移动语义，数据的所有权被直接转移，避免了复制操作，从而提高了性能。

使用场景：

• 当一个对象的生命周期短，并且不再需要它时，可以将它的资源转移到另一个对象中。
• 当你返回一个临时对象时，移动语义能避免不必要的复制。

5. 右值引用与常规引用的区别

• 左值引用 (&)：可以绑定到 左值，引用已经存在的对象。不能绑定到临时对象或常量。
• 右值引用 (&&)：只能绑定到 右值，即临时对象、表达式的结果等。允许资源的转移，避免了深拷贝。

举个例子：

int a = 10;
int& lref = a;     // 左值引用，绑定到左值 a
int&& rref = 20;   // 右值引用，绑定到右值 20

6. 总结

• 右值引用 (&&) 允许我们捕获和操作 右值，为 移动语义 提供支持。
• 移动语义 允许我们将对象的资源从一个对象转移到另一个对象，避免了不必要的拷贝，从而提高了程序的性能。
• 移动构造函数 和 移动赋值运算符 是支持移动语义的核心，它们通过转移对象的资源来避免复制操作。

通过右值引用和移动语义，我们能够写出更高效、性能更好的 C++ 代码，尤其是在处理大型数据结构和容器时。

自动类型推导（auto 和 decltype）

自动类型推导：auto 和 decltype

在 C++ 中，auto 和 decltype 都是与类型推导相关的关键字，它们帮助程序员简化代码，避免手动指定冗长或复杂的类型。

1. auto 关键字

        auto 是 C++11 引入的关键字，用来自动推导变量的类型。编译器根据变量的初始化表达式来推导变量的类型。

基本用法：

auto x = 10;        // x 的类型是 int
auto y = 3.14;      // y 的类型是 double
auto z = "hello";   // z 的类型是 const char*

用于函数返回类型：

auto 也可以用于函数的返回类型，特别是当返回类型较为复杂时，或者返回值的类型依赖于某些表达式的计算结果。

auto add(int a, int b) {
    return a + b;  // 返回值的类型自动推导为 int
}

用于迭代器：

auto 在使用 STL 容器时特别有用，避免了繁琐的类型声明，尤其是迭代器类型的声明。

#include <vector>

std::vector<int> vec = {1, 2, 3, 4, 5};
for (auto it = vec.begin(); it != vec.end(); ++it) {
    std::cout << *it << " ";  // 自动推导 it 的类型
}

2. decltype 关键字

decltype 是 C++11 引入的另一个关键字，它的作用是查询表达式的类型。decltype 不会计算表达式的值，只会返回该表达式的类型。

基本用法：

int x = 10;
decltype(x) y = 20;  // y 的类型与 x 相同，都是 int

double z = 3.14;
decltype(z) w = 2.71;  // w 的类型是 double

用于推导函数返回类型：

有时候，函数的返回类型可能很复杂（如模板函数），这时可以用 decltype 来推导返回类型，而无需手动指定。

template<typename T, typename U>
auto multiply(T a, U b) -> decltype(a * b) {
    return a * b;  // 返回值的类型是 a * b 的类型
}

3. auto 和 decltype 的区别

auto：用于变量声明时，编译器根据初始化表达式来推导类型。适用于你知道变量的初始值，但不想显式写出类型时。

        自动推导类型，适用于变量声明。

        如果初始化表达式返回引用或常量，auto 会丢弃引用或常量。

decltype：用于获取任何表达式的类型，无论是否为引用、常量、指针等。适用于你想要查询某个表达式类型或返回类型时。

        获取表达式的类型，不对类型进行推导。

        如果表达式是一个引用类型，decltype 会保留这个引用。

举例说明两者的区别：

int x = 10;
int& ref = x;

// auto 会推导为 int，因为初始化值是 `x`
auto a = x;      // a 的类型是 int

// decltype 会保留引用类型
decltype(ref) b = x;  // b 的类型是 int&

4. 使用场景和最佳实践

使用 auto：

        适用于复杂类型的变量声明，尤其是当类型很长或难以确定时。

        减少代码重复和冗长，特别是在模板编程中。

        迭代器类型、返回类型等都可以通过 auto 自动推导。

示例：

std::vector<int>::iterator it = vec.begin();
auto it2 = vec.begin();  // 自动推导类型

使用 decltype：

        当你需要保持某个变量的类型，特别是引用类型时，decltype 是非常有用的。

        用于函数返回类型推导，或者在模板编程中获取表达式类型。

示例：

decltype(x + y) result = x + y;  // result 的类型与 x + y 相同

5. 组合使用：auto 和 decltype

这两个关键字可以结合使用，尤其是在模板编程或复杂类型的情况中非常有用。

示例：

template <typename T>
auto sum(T a, T b) -> decltype(a + b) {
    return a + b;
}

在这里，auto 用于返回类型，decltype 用于推导 a + b 的类型。

总结

        auto 关键字用于变量声明时自动推导类型，简化代码，尤其在复杂类型或迭代器类型中非常有用。

        decltype 用于查询表达式的类型，保持原始类型信息，适用于需要精确控制类型的场景。

        auto 和 decltype 经常一起使用，帮助简化和增强代码的可读性与灵活性。