关于编译器

  • gcc 主要用作 C 语言编译器，但它实际上可以编译多种语言的代码，包括 C、C++等
  • g++ 专门用于编译 C++ 代码

在使用gcc编译时，需要添加-lstdc++ -o ，-lstdc++ 选项用于告诉编译器链接 C++ 标准库，-o 选项指定输出文件的名称。

而在使用g++时，则无需，但要在JSON文件里修改编译器（许多软件、工具、框架都使用 JSON 作为配置文件格式）

基础知识

1
using namespace std;

需要避免与用户自定义的类或函数名字与__C++ 标准库__大量常用的工具和数据结构（例如 vector、string、map 等）冲突。为了避免每次都写 std:: 前缀在前面声明这样一句话。

for

常见的几种使用方式：

  • 传统的循环方式，for(int i = 0;;)，如果是循环中初始化的变量，作用域只能在for循环里。
  • 遍历容器或数组，for (declaration : container)
  • 使用引用的范围，for (int& num : numbers)
    • 这里的&表示引用，当函数参数是大对象时，使用值传递会导致对象被复制，消耗大量的内存和性能。通过使用按引用传递，可以避免复制，只传递对象的引用。与指针有很大的区别，比如指针可以是空的，但引用必须在初始化的时候就指向某个对象，等。当被引用的对象不能进行更改时，可以用const进行修饰。，此外该符号还有取地址的意思。

字符串

  • 判断两个字符串是否相同的方式
    • 运算符==
    • 方法std::string::compare()，返回0表示字符串相等
    • 函数std::strcmp()，返回0表示字符串相等
    • 函数boost::iequals()，比较时忽略大小写
  • insert可用于给哈希表添加元素，push_back用于动态的（数组vector、不能用于哈希表）插入元素

复杂度

  • __时间复杂度__可以理解为在最坏情况下，程序中某个操作（例如循环或递归）执行的次数。大 O 表示法的规则，我们忽略常数因子。
  • __空间复杂度__，算法执行过程中需要额外的存储空间，比如循环中迭代的i复杂度就是O(n)，不管输入或常量规模多大，复杂度都是O(1)。

哈希表

unordered_set只储存键，__官方库不支持<vector>类型__，使用.insert()函数进行插入，unordered_map即储存键也储存值，只插入键时，默认的值是0，不能只插入键，必须插入键值。比如map1[p[i]] = 0;。当元素不在容器中时，.find()会返回.end()。.erase()用于删除哈希表的某个键。.clear()用于清空所有键。_对于一般的数据类型都是有官方的哈希函数的，但是如果是数组则需要自己定义，比如vector<int>或者vector<char>_。通过.size()获取哈希表的大小。

哈希表可以直接存放基本数据类型，如 int、float、double、char、bool 等。哈希表也可以存放标准库中的数据类型，如 std::string、std::vector、std::pair 等。哈希表可以存放自定义数据类型，但需要满足以下条件：

  • 作为键（Key）时：必须定义哈希函数和相等比较函数。
  • 作为值（Value）时：无需额外操作。

常见用途：

  • 快速查找
  • 去重
  • 计数
  • 快速判断元素是否存在

将哈希表中的键存入数组：

1
2
3
for (const auto& key : keys) {  //&表示引用，相当于直接操作要被遍历的变量，减少了地址的开销
    cout << key << " ";
}

双指针

  1. 快慢指针
  2. 左右指针

作用主要在于降低时间复杂度，比如在处理三数之和的数组时…

排序

C++标准库有可以直接使用的排序函数，sort(数组的开始位置,数组结束的位置)，默认是升序排序，降序如下：

1
2
3
4
5
6
//升序
sort(nums.begin(), nums.end());//对nums进行排序
// 使用 lambda 表达式进行降序排序
sort(vec.begin(), vec.end(), [](int a, int b) {
    return a > b;  // 如果 a > b，则返回 true，表示降序
});

宏定义

宏定义（关键字：define）C/C++等编程语言中的一种预处理指令，用于在编译之前对代码进行文本替换。

常见用法

(1) 定义常量

用于定义程序中使用的常量，避免魔法数字（Magic Number）。

1
2
#define PI 3.14159
#define MAX_SIZE 100

(2) 定义函数式宏

可以定义带参数的宏，类似于函数，但本质是文本替换。

1
2
#define SQUARE(x) ((x) * (x))
#define MAX(a, b) ((a) > (b) ? (a) : (b))

(3) 简化代码

用于简化重复性代码，提高可读性。

1
#define PRINT_ERROR(message) printf("Error: %s\n", message)

(4) 条件编译

与#ifdef、#ifndef等指令结合，实现条件编译。

1
2
3
4
#define DEBUG
#ifdef DEBUG
  printf("Debug mode is enabled.\n");
#endif

链表

使用临时链表复制当前链表：

1
ListNode *tempA = headA;

常量指针（Pointer to Constant）

常量指针是指 指针指向的值不能被修改，但指针本身可以指向其他地址。

语法：

1
const int* ptr;

指针常量（Constant Pointer）

指针常量是指 指针本身的值（即指向的地址）不能被修改，但可以通过指针修改指向的值。

语法：

1
int* const ptr;

常量指针常量（Constant Pointer to Constant）

常量指针常量是指 指针本身的值和指针指向的值都不能被修改。

语法：

1
const int* const ptr;

STL容器

vector

常用操作方法

  1. 创建 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    // 创建一个空的 vector
    std::vector<int> vec1;

    // 创建包含 5 个元素的 vector，初始值为 0
    std::vector<int> vec2(5);

    // 创建包含 5 个元素的 vector，初始值为 10
    std::vector<int> vec3(5, 10);

    // 使用初始化列表创建 vector
    std::vector<int> vec4 = {1, 2, 3, 4, 5};

  2. 访问元素

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    // 使用下标访问元素
    std::cout << "Element at index 2: " << vec[2] << std::endl;

    // 使用 at() 访问元素（会检查边界）
    std::cout << "Element at index 3: " << vec.at(3) << std::endl;

    // 访问第一个元素
    std::cout << "First element: " << vec.front() << std::endl;

    // 访问最后一个元素
    std::cout << "Last element: " << vec.back() << std::endl;

  3. 插入元素

    1
    2
    3
    4
    5
    // 在末尾插入元素
    vec.push_back(4);

    // 在指定位置插入元素
    vec.insert(vec.begin() + 1, 10); // 在索引 1 处插入 10

  4. 删除元素

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    // 删除末尾元素
    vec.pop_back();

    // 删除指定位置的元素
    vec.erase(vec.begin() + 1); // 删除索引 1 处的元素

    // 删除一段范围内的元素
    vec.erase(vec.begin() + 1, vec.begin() + 3); // 删除索引 1 到 2 的元素

    // 清空 vector
    vec.clear();

链表

链表的基本结构是一个节点类，包含数据域和指针域。以下是单链表的节点定义：

1
2
3
4
5
CPPstruct ListNode {
    int val;          // 数据域
    ListNode* next;   // 指针域，指向下一个节点
    ListNode(int x) : val(x), next(nullptr) {} // 构造函数
};

链表根据指针域的不同可以分为以下几种：

  1. 单链表（Singly Linked List）

每个节点只有一个指针域，指向下一个节点。最后一个节点的指针域为 nullptr。

1
head -> [1] -> [2] -> [3] -> nullptr
  1. 双链表（Doubly Linked List）

每个节点有两个指针域，分别指向前一个节点和后一个节点。

1
head <-> [1] <-> [2] <-> [3] <-> nullptr

节点定义：

1
2
3
4
5
6
CPPstruct ListNode {
    int val;
    ListNode* prev; // 指向前一个节点
    ListNode* next; // 指向后一个节点
    ListNode(int x) : val(x), prev(nullptr), next(nullptr) {}
};
  1. 循环链表（Circular Linked List）

单链表或双链表的最后一个节点的指针域指向头节点，形成一个环。

1
head -> [1] -> [2] -> [3] -> head

以下是链表的一些常见操作：

  1. 创建链表
1
2
3
CPPListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);
  1. 遍历链表
1
2
3
4
5
CPPListNode* curr = head;
while (curr != nullptr) {
    cout << curr->val << " ";
    curr = curr->next;
}
  1. 插入节点

在头部插入

1
2
3
CPPListNode* newNode = new ListNode(0);
newNode->next = head;
head = newNode;

在尾部插入

1
2
3
4
5
CPPListNode* curr = head;
while (curr->next != nullptr) {
    curr = curr->next;
}
curr->next = new ListNode(4);

在中间插入

1
2
3
CPPListNode* newNode = new ListNode(2.5);
newNode->next = head->next;
head->next = newNode;
  1. 删除节点

删除头部节点

1
2
3
CPPListNode* temp = head;
head = head->next;
delete temp;

删除尾部节点

1
2
3
4
5
6
CPPListNode* curr = head;
while (curr->next->next != nullptr) {
    curr = curr->next;
}
delete curr->next;
curr->next = nullptr;

删除中间节点

1
2
3
CPPListNode* temp = head->next;
head->next = head->next->next;
delete temp;
  1. 查找节点
1
2
3
4
5
6
7
8
9
CPPListNode* curr = head;
int target = 2;
while (curr != nullptr) {
    if (curr->val == target) {
        cout << "Found: " << target << endl;
        break;
    }
    curr = curr->next;
}
  1. 反转链表
1
2
3
4
5
6
7
8
9
CPPListNode* prev = nullptr;
ListNode* curr = head;
while (curr != nullptr) {
    ListNode* next = curr->next;
    curr->next = prev;
    prev = curr;
    curr = next;
}
head = prev;
  1. 检测环

使用快慢指针（Floyd’s Cycle Detection Algorithm）：

1
2
3
4
5
6
7
8
9
10
CPPListNode* slow = head;
ListNode* fast = head;
while (fast != nullptr && fast->next != nullptr) {
    slow = slow->next;
    fast = fast->next->next;
    if (slow == fast) {
        cout << "Cycle detected!" << endl;
        break;
    }
}

二叉树

  1. 中序遍历（Inorder Traversal）

顺序：左子树 → 根节点 → 右子树

中序遍历会按照“左-根-右”的顺序访问二叉树的节点。

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
private:
    vector<int> ans;
public:
    vector<int> inorderTraversal(TreeNode* root) {
        iterTree(root);
        return ans;
    }
    
    void orderTree(TreeNode* root){
        if(!root){
            return;
        }
        orderTree(root->left);
        ans.push_back(root->val);
        orderTree(root->right);
    }

};
  1. 前序遍历（Preorder Traversal）

顺序：根节点 → 左子树 → 右子树
前序遍历会按照“根-左-右”的顺序访问二叉树的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
private:
    vector<int> ans;
public:
    vector<int> inorderTraversal(TreeNode* root) {
        iterTree(root);
        return ans;
    }
    
    void orderTree(TreeNode* root){
        if(!root){
            return;
        }
        ans.push_back(root->val);
        orderTree(root->left);
        orderTree(root->right);
    }

};
  1. 后序遍历（Postorder Traversal）

顺序：左子树 → 右子树 → 根节点
后序遍历会按照“左-右-根”的顺序访问二叉树的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
private:
    vector<int> ans;
public:
    vector<int> inorderTraversal(TreeNode* root) {
        iterTree(root);
        return ans;
    }
    
    void orderTree(TreeNode* root){
        if(!root){
            return;
        }
        orderTree(root->left);
        orderTree(root->right);
        ans.push_back(root->val);
    }

};