C++知识

指针

• *号的两种使用

• 定义指针int* p, int *p，星号位置不重要

• 解指针p = &a ,*(p)

• 指针可用->访问成员变量，ptr->member等价于(*ptr).member

• 也可以连续访问root->left->right

it是一个迭代器，
vector<int>& nums = it->second;   // (1) 引用
vector<int> nums = it->second;    // (2) 值拷贝，一般不用

new关键字返回的是指针
所以构造结点的正确做法如下

Node* p = new Node(0);
// 或者
Node dummy(0);          // 直接构造
Node* p = &dummy;       // 获取指针
// 或
Node dummy = Node(0);   // 拷贝初始化（C++17 后也是直接构造）

vector 向量（动态数组）

• vector<int> vec(n, 1);初始化长度为 n,元素全为 1 的向量

• vector<vector<int>> vec;空的二维向量

• int m = matrix.size(), n = matrix[0].size();获取向量的长度 m，每一项的长度为 n

• vec.push_back({b});添加每一项的第一个

• vec[i].push_back(b);添加每一项的第二个

• vec.resize(n);初始化,分配空间之后才能赋值，所有初值为 0

• swap(nums[i], nums[j]);交换两个元素

• vec[0], vec.back()返回第一个和最后一个元素的引用

• vec.begin(), vec.end()返回第一个和最后一个元素的迭代器

• ranges::reverse(nums.begin(), nums.begin() + k);翻转向量，123->321

• ranges::sort(vec);排序数组

• vec.erase(it);动态删除向量里的元素

• vec1 = move(vec2);把 vec2 内部的指针等资源直接转移给 vec1，vec2 空，时间复杂度 O(1)，vec1 会被完全覆盖

• vec.emplace_back(pair)功能相当于vec.push_back(pair)，但在面对复杂对象时效率更高，他是直接在 vec 里面创建这个对象

• vector vec(n, string(m, '.'));快捷创建 n 行 m 列二维向量

// 初始化向量
vector<int> vec;
vec.resize(n);
vec[i] = 1;

二维向量相关操作

// leetCode第56题合并区间
vector<vector<int>> ans;// 新建一个二维向量
ranges::sort(intervals); // 二维向量按照左端点从小到大排序
for (auto& pair : intervals) {
    if (!ans.empty() && ans.back()[1] >= pair[0]) {// .back()访问最后一项，[1]访问第二个元素
        ans.back()[1] = max(ans.back()[1], pair[1]);
        continue;
    }
    ans.emplace_back(pair);// 如果不满足就在ans中构建这个新pair
}

unordered_map 哈希表

• unordered_map<int, int> map;初始化
• map[i] == map2[i]用操作符[]访问不存在的 key 时会隐式的插入 0 污染 map，即使作为判断条件也是
• map.count(key)判断是否存在，返回 0 或 1，在上面的判断条件里加上map2.count(s[i]) &&先执行就能避免污染
• map 是无序的，用for (auto& x : map)迭代也是随机的

迭代器

• 实质是一个指针，可用it -> first, it -> second访问内部成员
• 也可以完全解指针&a = *it, a -> first
• 用于迭代for (auto it = c.begin(); it != c.end(); ++it)或者for (const auto& x : vec)
• 类型复杂所以直接用 auto 声明
• 很多函数返回的都是迭代器，就比如lower_bound(), map.find(key), nums.begin(), nums.end()

lambda 表达式（匿名函数）

C++在方法内定义方法就要用这种隐函数的语法
函数名只能用 auto
[capture](parameters) -> return-type { body }

auto sum = [&](int b) -> int {
    // ...
};

捕获器类型

• [] 不捕获任何外部变量
• [&] 按引用捕获所有用到的外部变量（推荐用于读写或大对象）
• [=] 按值捕获所有用到的外部变量（只读副本）
• [&nums, threshold] 显式按引用捕获 nums，按值捕获 threshold

定义递归函数，把函数自身作为参数传进去(this auto&& dfs)

auto dfs = [&](this auto&& dfs, int i, int j) -> void {
            // 出界，或者不是 '1'，就不再往下递归
            if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != '1') {
                return;
            }
            grid[i][j] = '2'; // 插旗！避免来回横跳无限递归
            dfs(i, j - 1); // 往左走
            dfs(i, j + 1); // 往右走
            dfs(i - 1, j); // 往上走
            dfs(i + 1, j); // 往下走
        };

<<>>位运算符

<<运算符用于左移，>>运算符用于右移

x << 3  // 等价于 x * 8

int a = 5;        // 二进制: 00000101
int b = a << 1;   // 左移1位 → 00001010 = 10
int c = a << 2;   // 左移2位 → 00010100 = 20

cout << b << endl; // 输出: 10
cout << c << endl; // 输出: 20

&运算符用于位与，|运算符用于位或，^运算符用于位异或，~运算符用于位取反

// 检查第 c 位是否为 1
if (vis >> c & 1) { // c 在集合中
    return false;
}
vis |= 1 << c; // 把 c 加入集合

deque 双端队列

两侧都能添加和删除元素
deque<int> q;初始化
pop_front() 删除队列首元素,动态删除，删完之后队首元素索引还是 0
pop 访问队首元素，但不删除

条件

C++ 的&&是从左到右求值，所以会先执行q.back()，再判断!q.empty()，在 q 为空的时候这么做会报错
正确做法:while (!q.empty() && nums[i] > nums[q.back()])

字符串

• 操作和动态数组很像

• 可以直接加减字符串string ans = t + 'a'

  构建子串

• std::string sub1 = s.substr(0, 5); // 选取从 0 开始的长度为 5 的子串

• std::string sub2 = s.substr(7); // 选取从 7 开始的子串

stack 栈

• stack<int> s;初始化
• s.push(x)入栈
• s.pop()出栈
• s.top()访问栈顶元素,要获取栈顶再弹出就要先 top()再 pop()
• s.empty()判断栈是否为空
• st = stack<int>();构造空栈，置空栈

单调栈，栈内元素是单调的

// 84. 柱状图中最大的矩形
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int ans = 0;
stack<int> st;
st.push(-1);// 用-1 入栈来做哨兵元素，这样所有左侧第一小保底就是-1，改 while 循环条件
heights.push_back(-1); // 结尾也加哨兵元素，就能用用 -1 把栈清空

        // 有了哨兵元素而且能直接计算，所以最后数组也不需要了
        for (int right = 0; right < heights.size(); right++) {// i改叫right，更直观
            int h = heights[right];
            // 在进入while的时候，当前的right就是栈顶的左侧第一小！！！
            // 数组结尾添加一个哨兵-1，遍历到-1，就能最后把栈排空
            while (st.size() > 1 && h <= heights[st.top()]) {
                int h_ans = heights[st.top()];// 保存当前栈顶的高
                // 弹出一个元素之后，当前栈顶就是被弹出栈顶的左侧第一小！！！
                st.pop();
                int left = st.top();
                ans = max(ans, h_ans * (right - left - 1));
            }
            st.push(right);
        }
        return ans;
    }
};

queue 队列

先进后出，从队尾入队，队首出队(就是排队)
可用于广度优先搜索(BFS)

• queue<T> q;初始化
• q.push(x)入队
• q.pop()出队
• q.front()访问队首元素,要获取队首再弹出就要先 front()再 pop()
• q.empty()判断队列是否为空

Deque 双端队列

构造函数的初始化列表

用初始化列表初始化成员变量，比赋值更高效
const 成员和引用成员只能用初始化列表初始化

• LRUCache(int _capacity) 是构造函数的参数列表；
• :capacity(_capacity),size(0) 为初始化列表

class LRUCache {
private:
    int size;
    int capacity;
public:
    // 构造函数,接受一个传入的参数_capacity用他capacity,然后再初始化size为0
    LRUCache(int _capacity):capacity(_capacity),size(0) {
        // 使用初始化的值
    }
}

结构体

结构体(struct)是一种用户自定义的数据类型，允许将不同类型的数据组合在一起。
结点就是一种定义的结构体，用指针加成员访问符->可以访问成员变量，用结构体名加.也可以访问成员变量

// 定义一个结构体实现双向链表，包含4个属性，key，value，前后指针
struct DLinkedNode {
    int key, value;
    DLinkedNode* prev;
    DLinkedNode* next;
    // 默认构造器
    DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {}
    // 带参构造器
    DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}
};

pair 二元组

pair 是 C++ 标准库中的一个类，用于存储两个元素。
适合遍历图，Map，表示坐标，键值对
有两个成员变量 first 和 second，分别表示键和值。

vector<pair<int, int>> q;坐标向量
for (auto& [x, y] : q)结构化绑定遍历
或者for (auto& p : q)然后用 p.first, p.second 访问

Map 哈希表

map 里面的元素是键值对，pair 来表示，也可称作 entry
first 和 second 是 pair 的成员变量
map 的遍历
for (auto& [key, value] : map)
for (auto& p : map)然后用 p.first, p.second 访问`