C++

1. const_cast

  • 功能：用于去除变量的const或volatile属性（非const对象的强制转换）。
  • 注意：去除const后修改数据时需小心，若对原本声明为const的数据进行修改，会导致未定义行为。

2. 三大特性

  1. 封装:
    • 封装了数据，隐藏了实现细节，只暴露出必要的接口。
    • 通过访问修饰符（private、protected、public）控制数据的访问权限。
  2. 继承:
    • 子类可以继承父类的资源、属性、函数等。
    • 支持代码复用，子类可以添加新的属性或重写父类的方法。
  3. 多态:
    • 子类可以重写（override）父类的虚函数，在运行时根据实际对象类型调用对应的方法。
    • 通过基类指针或引用实现动态绑定。

3. 虚函数与纯虚函数

  1. 虚函数 (virtual):

    • 通过virtual关键字声明，可以被子类重写。
    • 有正常的函数体，子类可以选择是否重写。

  2. 纯虚函数 (= 0):

    • 没有函数体，子类必须重写。
    • 拥有纯虚函数的类称为抽象类，不能实例化。

4. static

  1. 静态存储：存储在静态区，生命周期贯穿程序整个运行周期。
  2. 应用场景：
    • 静态成员变量：类共享的变量，每个对象实例共享一份内存。
    • 静态函数：不依赖于具体对象，可以通过类名直接调用。

5. 上行转换与下行转换

  1. 上行转换（Upcasting）：

    • 子类指针或引用转换为父类指针或引用。
    • 安全且无需强制转换。

  2. 下行转换（Downcasting）：

    • 父类指针或引用转换为子类指针或引用。
    • 需要通过dynamic_cast（确保安全）或static_cast。

6. weak_ptr

  1. 使用场景：

    • 避免shared_ptr之间的循环引用。

  2. 特性：

    • 不增加引用计数。
    • 可以通过lock()将weak_ptr提升为shared_ptr，如果资源已被释放，则返回空指针。

7. vector

  1. 查询：

    • 访问元素时间复杂度为O(1)（通过索引直接访问）。

  2. 插入：

    • 末尾插入：若空间足够，时间复杂度为O(1)；否则触发扩容，为O(n)。
    • 中间插入：需要将后续元素向后移动，时间复杂度为O(n)。

8. 左值与右值

  1. 左值：

    • 可以取地址的对象（如变量）。

  2. 右值：

    • 不能取地址的临时对象（如返回值、字面量）。
    • 通过std::move()可以将右值的所有权转移给其他对象。

9. C++函数参数的内存分配

  1. 传值参数：

    • 在栈上分配内存。

  2. 引用参数：

    • 不复制数据，仅在栈上存储引用（指针）。

  3. 指针参数：

    • 指针本身存储在栈上，指向的数据位置取决于具体分配（堆/栈）。

10. override

  • 子类重写父类的虚函数时，显式标记为override，可以帮助编译器检查是否真的重写了父类方法，避免错误。

11. 常见链表

  1. 单链表
  2. 双向链表
  3. 循环链表
  4. 跳表（用于高效查找，时间复杂度O(log n)）

12. 哈希冲突

哈希冲突：两个不同的键通过哈希函数得到相同的哈希值。
解决方法：

  1. 链式法：在同一哈希桶中存储冲突的元素。
  2. 线性探测：寻找下一个空闲位置存储元素。
  3. 二次探测：跳跃式寻找下一个空闲位置。

13. 死锁

  1. 四个必要条件：

    1. 请求保持：线程已持有资源，同时请求新的资源。
    2. 不可剥夺：资源不能被强行剥夺。
    3. 循环等待：多个线程形成资源等待的循环链。
    4. 互斥条件：资源只能被一个线程独占。

  2. 简述：

    • 两个线程分别持有部分资源，互相请求对方的资源且不释放，导致僵持状态。

14. enum 与 enum class

  1. enum：

    • 底层类型默认为int，可以隐式转换为int。
    • 同一作用域内，多个enum的成员名可能冲突。

  2. enum class：

    • 成员名必须通过enum class名限定。
    • 不支持隐式转换为int，需要显式转换。

15. malloc 与 new 分配的内存位置

  • malloc 和 new：分配在堆区。

16. malloc/free 与 new/delete 的区别

  1. malloc/free：

    • C语言函数。
    • 返回void *，需手动转换类型。
    • 分配失败返回NULL。
    • 不会调用构造/析构函数。

  2. new/delete：

    • C++操作符。
    • 返回具体类型指针。
    • 分配失败抛出异常（std::bad_alloc），可以使用nothrow避免异常。
    • 会自动调用构造/析构函数。

17. 手撕题

  1. 分组问题（并查集）：

    • 有些人不想和某人一组，判断是否可以分为两组。
    • 使用并查集或二分图染色法解决。

  2. 青蛙跳台阶问题：

    • 简单DP:
      • 状态转移方程：dp[i] = dp[i-1] + dp[i-2]
      • 初始化：dp[0] = 1, dp[1] = 1