星环科技一面、二面、Offer

一面--8月17日

如何解决强化学习中的奖励稀疏问题
- 奖励稀疏问题是指在强化学习中，智能体在执行任务时只会偶尔收到正面的奖励反馈，导致学习过程变得困难。解决奖励稀疏问题的方法有以下几个方向：
  1. 奖励设计：重新设计奖励函数，使其更具信息量，提供更多的反馈。可以采用稀疏奖励的方式，即设置额外的中间目标，并给予奖励，这样智能体在不断实现中间目标的过程中也能得到积极的反馈。
  2. 使用启发式初始化：通过给智能体提供一些启发式的初始知识，加速学习过程。这些启发式信息可以是专家的经验或者领域知识，在智能体开始学习之前就将其注入，帮助它更快地找到有效的策略。
  3. 探索与利用的平衡：使用合适的探索策略来平衡探索新状态和利用已获得的知识。例如，可以使用ε-贪婪算法，在一定概率下选择随机行为，以便发现新的有潜力的策略。
  4. 经验回放：通过保存智能体过去的经验，并将其随机抽取作为训练数据进行反复学习。这样可以使得智能体在少量正面奖励反馈出现时也能够从之前的经验中学到有效的策略。
  5. 逐步增加难度：如果任务过于困难，可以考虑逐步增加任务的难度。从简单的子任务开始训练智能体，然后逐渐引入更复杂的任务环境，这样有助于智能体逐步学习和掌握有效的策略。
  6. 联合学习：多个智能体之间可以相互协作，互相提供信息和奖励，以加快学习过程。例如，可以使用共享奖励的方法，多个智能体共同完成任务并分享奖励，从而减轻奖励稀疏性带来的问题。、
C++里面的独占指针和智能指针
- 智能指针和独占指针是C++中用于管理动态分配的内存的两种重要概念。
  
  智能指针是一种封装了动态分配对象的指针，它提供了自动化的内存管理。智能指针可以跟踪对象的所有权，并在不再需要时自动释放分配的内存，避免了内存泄漏和悬挂指针的问题。C++标准库提供了几种智能指针的实现，包括std::shared_ptr、std::unique_ptr和std::weak_ptr。
- 独占指针是一种特殊的智能指针，它只能拥有一块内存资源的所有权。当使用独占指针管理某个对象时，其他任何指针都不能同时拥有该对象的所有权。这样可以确保在对象没有被释放之前，不会发生误删除或多次删除的情况。在C++中，std::unique_ptr就是独占指针的一种实现。
  
  独占指针的特点包括：
  - 独占指针拥有对动态分配对象的独立所有权，当独占指针超出作用域或被显式释放时，它所拥有的对象将自动释放。
  - 独占指针不允许多个指针同时拥有同一个对象的所有权，因此可以避免悬挂指针和二次删除等问题。
  - 独占指针可以通过移动语义来转移对资源的所有权，从而实现所有权的转移而不需要进行昂贵的深拷贝操作。
  使用独占指针可以提高程序的安全性和可靠性，减少内存泄漏和指针错误的发生。但在使用时需要注意，确保只有一个独占指针拥有某个对象的所有权，避免产生悬挂指针或多重删除的问题。
C++的纯虚函数
- 纯虚函数（pure virtual function）是C++中的一种特殊函数，它在基类中声明但没有提供实现。它的语法形式是在函数声明后面加上= 0。
  
  具有纯虚函数的类被称为抽象类（abstract class），抽象类不能直接实例化对象，只能用作其他类的基类。抽象类的主要目的是定义一个接口，规定了派生类必须实现的功能或行为。
  
  抽象类通过纯虚函数提供了一个协议或契约，派生类必须实现这些纯虚函数，否则派生类也会变成抽象类，无法直接实例化对象。当派生类继承了抽象类并且没有实现所有纯虚函数时，编译器会发出错误提示。
  
  纯虚函数的主要特点包括：
  - 纯虚函数没有默认的实现，它只是一个接口的声明，派生类必须提供自己的实现。
  - 抽象类可以包含非纯虚函数和数据成员，与普通类一样。
  - 派生类可以重新定义基类的纯虚函数，并提供自己的实现。
  - 如果派生类没有实现所有基类的纯虚函数，它也将成为一个抽象类。
  纯虚函数的使用场景包括：
  - 实现接口：通过定义抽象类和纯虚函数来定义接口，派生类必须实现这些函数。
  - 多态性：通过指向基类的指针或引用调用纯虚函数，实现运行时的多态性。
  需要注意的是，纯虚函数不能在抽象类中直接调用，因为它没有默认的实现。如果希望在抽象类中调用某个函数，可以将其定义为虚函数并提供一个默认的实现，然后在纯虚函数中调用该虚函数。
  
  总之，纯虚函数是C++中用于定义抽象类和接口的一种机制，通过强制派生类实现接口的功能，实现了软件设计中的多态性和接口隔离原则。
C++中的虚表
- 虚表（virtual table），也被称为虚函数表（vtable），是C++中用于实现多态性的一种机制。
  
  在C++中，如果一个类至少有一个虚函数，编译器会为该类创建一个虚表。虚表是一个存储指向虚函数的指针的数组，每个虚函数在数组中对应一个指针。虚表位于对象的内存布局中的一个固定位置，通常是作为对象的第一个成员或者在对象的元数据中。
  
  当一个类通过继承关系派生出子类时，子类会继承父类的虚表，并且可以在虚表中添加或重写虚函数的指针。这样，在使用基类指针或引用指向派生类对象时，通过虚表可以实现动态绑定，即根据对象的实际类型来调用对应的虚函数。
  
  具体来说，通过虚表可以实现以下功能：
  1. 通过基类指针或引用调用派生类的虚函数：在运行时，根据对象的实际类型查找虚表，并调用对应的虚函数，实现多态性。
  2. 支持在派生类中重写基类的虚函数：派生类可以在虚表中替换掉基类虚函数的指针，从而重写该函数的实现。
  需要注意以下几点：
  - 虚表是针对每个类的，而不是针对每个对象的。不同对象共享同一个类的虚表。
  - 虚表的构建和管理由编译器负责，开发者无需手动操作。
  - 虚表的使用存在运行时开销，因为在调用虚函数时需要根据虚表进行查找。
  虚表是C++中实现多态性的重要机制之一，它使得通过基类指针或引用操作派生类对象时可以根据实际类型来调用相应的函数，从而实现了面向对象编程中的多态特性。
static关键字
- 在C++中，static 关键字具有多种用途，取决于它应用的上下文。下面是一些常见用法：
  1. 静态变量：
    - static 修饰函数内的局部变量时，会使该局部变量成为静态变量。静态变量在程序的生命周期内保持其值，并且仅在第一次进入声明它的函数时进行初始化。
    - static 修饰类的成员变量时，会使该成员变量成为类的共享变量，即所有该类的实例共享同一个变量副本。
  2. 静态函数：
    - static 修饰类的成员函数时，表示该函数属于类而不是类的实例。静态函数可以直接通过类名调用，无需创建类的实例。
    - static 成员函数只能访问类的静态成员变量和其他静态成员函数，不能访问非静态成员变量和非静态成员函数。
  3. 静态类：
    - static 关键字在类定义中的其他上下文中不起作用。C++中没有直接支持静态类的语法。如果想要实现静态类，可以使用命名空间和静态成员来模拟实现。静态类是指只包含静态成员的类，无需创建实例即可访问这些成员。
  4. 静态断言：
    - static_assert 是C++11中引入的关键字，用于在编译时进行静态断言。静态断言允许在编译时检查某个条件是否为真，并在条件为假时产生编译错误消息。
const关键字，以及如何辨析const int*以及int*const
- const 是 C++ 中的关键字，用于声明常量。它可以应用于变量、指针和函数返回类型。
  
  在 C++ 中，const int* 和 int* const 是两种不同的声明方式，它们分别表示了指向常量的指针和常量指针。
  1. const int* 表示指向常量的指针，也称为常量指针。这意味着指针可以指向不同的 int 值，但不能通过该指针来修改所指向的值。
```
const int* ptr; // 声明一个指向常量的指针
int num = 5;
ptr = &num; // 可以将指针指向一个常量
*num = 10; // 错误：不能通过指针修改所指向的值
```
  1. int* const 表示常量指针，也就是指针本身是常量，它的值不能改变。但是可以通过该指针来修改所指向的值。
```
int* const ptr; // 声明一个常量指针
int num = 5;
ptr = &num; // 错误：不能改变指针的值
*num = 10; // 可以通过指针修改所指向的值
```
  需要注意的是，const 修饰的是其右侧的内容。因此，const int* 和 int const* 是等价的，都表示指向常量的指针。而 int* const 表示的是常量指针，const 修饰的是指针本身。

输入二叉树的前序序列，中序序列，恢复这个二叉树

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

// 定义二叉树节点结构
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

TreeNode* buildTree(const vector<int>& preorder, const vector<int>& inorder) {
    // 利用哈希表存储中序遍历序列中每个元素对应的索引，加快搜索速度
    unordered_map<int, int> inorderMap;
    for (int i = 0; i < inorder.size(); i++) {
        inorderMap[inorder[i]] = i;
    }
    
    return buildTreeHelper(preorder, 0, preorder.size() - 1,
                           inorder, 0, inorder.size() - 1,
                           inorderMap);
}

TreeNode* buildTreeHelper(const vector<int>& preorder, int preStart, int preEnd,
                          const vector<int>& inorder, int inStart, int inEnd,
                          unordered_map<int, int>& inorderMap) {
    if (preStart > preEnd || inStart > inEnd) {
        return nullptr;
    }
    
    int rootVal = preorder[preStart];  // 前序序列的第一个元素是根节点
    TreeNode* root = new TreeNode(rootVal); // 创建根节点
    
    int inRoot = inorderMap[rootVal];  // 在中序序列中找到根节点的位置
    int leftSubtreeSize = inRoot - inStart;  // 左子树的节点数量
    
    // 递归构建左右子树
    root->left = buildTreeHelper(preorder, preStart + 1, preStart + leftSubtreeSize,
                                 inorder, inStart, inRoot - 1,
                                 inorderMap);
    root->right = buildTreeHelper(preorder, preStart + leftSubtreeSize + 1, preEnd,
                                  inorder, inRoot + 1, inEnd,
                                  inorderMap);
    
    return root;
}

// 前序遍历二叉树（用于验证结果是否正确）
void preorderTraversal(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    
    cout << root->val << " ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

int main() {
    vector<int> preorder = {1, 2, 4, 5, 3, 6};
    vector<int> inorder = {4, 2, 5, 1, 6, 3};
    
    TreeNode* root = buildTree(preorder, inorder);
    
    cout << "Reconstructed binary tree (preorder traversal): ";
    preorderTraversal(root);
    
    return 0;
}