C++ 数组
数组大小固定，里面的值可以更改
定义并初始化数组
double balance[10];
double balance[5] = {1000.0, 2.0, 3.4, 7.0, 50.0};
double balance[] = {1000.0, 2.0, 3.4, 7.0, 50.0};
balance[4] = 50.0;
double balance[6] = {1000.0, 2.0, 3.4, 7.0, 50.0}; // 最后一位被赋了默认值0

STL容器
String:
构造函数：
string str1; // 创建一个空字符串对象
string str2 = "Hello"; // 使用C字符串初始化一个字符串对象
string str3(str2); // 使用另一个字符串对象初始化一个新的字符串对象
赋值操作：
string str1 = "Hello"; string str2 = str1; // 将一个字符串对象的值赋给另一个字符串对象
string str3 = "world"; str1 = str3; // 将一个字符串对象的值赋给另一个字符串对象
连接操作：
string str1 = "Hello"; string str2 = "world"; string str3 = str1 + " " + str2; // 将两个字符串对象连接在一起
string str1 = "Hello"; string str2 = "world"; str1.append(" "); // 将一个字符串对象连接到另一个字符串对象的末尾 str1.append(str2);
比较操作：
string str1 = "Hello"; string str2 = "Hello"; if (str1 == str2) { // 判断两个字符串对象是否相等 cout << "str1 and str2 are equal." << endl; }
string str1 = "Hello"; string str2 = "World"; if (str1 < str2) { // 判断一个字符串对象是否小于另一个字符串对象 cout << "str1 is less than str2." << endl; }
子串操作：
string str1 = "Hello world"; string str2 = str1.substr(6, 5); // 从一个字符串对象中提取一个子串 cout << "str2 is: " << str2 << endl;
string str1 = "Hello world"; str1.erase(5, 6); // 删除一个字符串对象的子串 cout << "str1 is now: " << str1 << endl;
查找操作：
string str1 = "Hello world"; size_t pos = str1.find("world"); // 在一个字符串对象中查找特定的子串 if (pos != string::npos) { cout << "The substring 'world' was found at position " << pos << endl; }
string str1 = "Hello world"; size_t pos = str1.rfind("l"); // 在一个字符串对象中从后往前查找特定的子串 if (pos != string::npos) { cout << "The last occurrence of 'l' was found at position " << pos << endl; }
其他操作：
string str1 = "Hello world"; int len = str1.size(); // 返回字符串对象中字符的数量 if (str1.empty()) { // 检查字符串对象是否为空 cout << "str1 is empty." << endl; }
string str1 = "Hello world"; const char* cstr = str1.c_str(); // 返回一个指向字符串对象所表示的C字符串的指针
求string的长度用
int len = str.size(); // 使用 size() 方法获取字符串长度
int len2 = str.length(); // 使用 length() 方法获取字符串长度

char
char就是ascii码，可直接比较（>, <, ==）
islower(char c) 是否为小写字母
isupper(char c) 是否为大写字母
isdigit(char c) 是否为数字
isalpha(char c) 是否为字母
isalnum(char c) 是否为字母或者数字
toupper(char c) 字母小转大
tolower(char c) 字母大转小

array
#include
using namespace std;

// 定义并初始化std::array
array<int, 5> arr = {1, 2, 3, 4, 5};

// 循环遍历赋值
array<int, 5> arr1;
for (int i = 0; i < 5; ++i) {
arr1[i] = i + 1;
}

// fill函数赋值
array<int, 5> arr2;
fill(arr2.begin(), arr2.end(), 0);

vector
C++标准库提供了vector容器类，它是一种动态数组，支持在数组末尾快速添加和删除元素，可以方便地实现数组的动态管理。vector的初始化和赋值有以下几种方法：
1、使用默认构造函数初始化
vector vec; // 初始化一个空的vector

2、使用构造函数初始化
可以使用vector的构造函数，将一个已有的数组或其他容器中的元素赋值给vector，例如：
int arr[] = {1, 2, 3, 4, 5}; v{ector vec(arr, arr + 5); // 将数组中的元素赋值给vector

3、使用初始化列表初始化
可以使用花括号{}，使用初始化列表初始化vector，例如：
vector vec = {1, 2, 3, 4, 5}; // 直接在花括号中添加元素

4、使用assign函数赋值
可以使用assign函数，将另一个vector、数组或初始化列表中的元素赋值给vector，例如：
vector vec; vec.assign({1, 2, 3, 4, 5}); // 将初始化列表中的元素赋值给vector
使用push_back函数添加元素

5、可以使用push_back函数，逐个添加元素到vector中，例如：
vector vec; vec.push_back(1); vec.push_back(2); vec.push_back(3);

vector.insert(pos, value); // 在 pos 处插入单个元素 value
vector.insert(pos, n, value); // 在 pos 处插入 n 个元素，每个元素的值为 value
vector.insert(pos, first, last); // 在 pos 处插入区间 [first, last) 中的元素
std::sort(vec.begin(), vec.end());

切片：

构造二维vector
初始化默认为0

初始化默认为1

Vector初始化

Stack：
初始化：
Stack只接受一个参数

Stack.pop() 无返回值
Stack.pop()一次添加一个，stack.emplace()一次添加多个
列表初始化，单个元素可以()和{}
多个元素必须{}

Map：
初始化

查找字典的值可以用find，可以用[]

确定某个键是否在字典内，可用map.count()

遍历map的key，value：
std::map<int, int> m;
std::vector keys;
std::vector values;
for (auto kv : m) {
keys.push_back (kv.first); // 将键存入 keys
values.push_back (kv.second); // 将值存入 values
}

有序字典：

Pair

std：：make_pair(x, y);
std::pair<int, int> p1 = std::make_pair(1, 2); // 显式指定类型
auto p2 = std::make_pair(3, 4); // 使用 auto 推断类型

Queue:

priority_queue

Deque

Set：

一些注意点：
在用指针的时候，最好用new

不能用 a<i< b, 应该用 a<i && i<b

Reverse(s.begin(), s.end())

列表初始化，单个元素可以()和{}
多个元素必须{}

Lambda
auto plus = [] (int a, int b) -> int { return a + b; }
int c = plus(1, 2);

取整的方法：
floor():向下取整
ceil()：向上取整
round()：四舍五入
trunc()：整数部分

Sort函数

是用lambda函数

无限大和无限小

C++,可以用int表示任意进制数
Int a = 0x16; // 十六进制
Int b = 0b1; //二进制
Int c = 077; //八进制

to_string(a)
接受一个数，转成字符串，只能转成10进制字符串

stoi(const string &str, size_t *idx = 0, int base = 10) -> int

字符串转为int，
参数分别为字符串，字符串中要转换的子串的起始位置 和 字符串的进制。

转为字符串的奇葩方法：

此时输出s为2a

转为二进制字符串：

求一个数的二进制位数：
int m = 32 - __builtin_clz(num);
int用__builtin_clz， long用64 - __builtin_clzl，long long用64 - __builtin_clzll

sstream 也是很好的str转int的方法

set里不可以放pair<int, int> ，可以 用a * base + b 把二维转一维
vector<vector> a, vector<pair<int, int>>a, vector<tuple<int, int, int>> a
可以直接a.push_back({a, b, c});

函数内定义函数可以 auto dfs = [&](int i, int cnt, bool is_limit) -> long long {}; 用lambda表达式
但是如果这个函数会递归调用，则不能用auto。
应该用function<long long(int, int, bool)> dfs = [&](int i, int cnt, bool is_limit) -> long long {};

求一个vector中最大的元素，
用*max_element(dp.begin(), dp.end())
max_element和min_element返回的是一个迭代器。

max有两种用法：
1、放两个数，如max(a, b)
2、放initializer_list, 如max({1, 2, 3, 4})

vector.begin(): 返回一个指向容器第一个元素的迭代器。
vector.end(): 返回一个指向容器末尾（最后一个元素的后一个位置）的迭代器。

memset(dp, 0, sizeof(dp)); 把数组dp全赋值0,也可以赋值二维dp
memset(dp, 0x3F, sizeof(dp)); 赋值无限大，0X7F为无限大，但这里用0x3F，这样两个无限大相加不会溢出
memset(dp, 0x80, sizeof(dp)); 赋值无限小
memset是按照字节赋值，但int占4个字节，只有赋值0和-1的时候是准确的

std::lower_bound： 返回一个迭代器，指向第一个不小于目标值的元素位置。如果第一个元素都大于目标的话，则返回vector.begin()。 如果最后一个元素都小于的话，则返回vector.end()。
std::upper_bound： 返回一个迭代器，指向第一个大于目标值的元素位置。

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> numbers = {1, 2, 2, 4, 4, 6, 8, 10};

    // 使用 std::lower_bound 查找第一个不小于目标值的元素位置
    auto lowerIt = std::lower_bound(numbers.begin(), numbers.end(), 4);

    // 使用 std::upper_bound 查找第一个大于目标值的元素位置
    auto upperIt = std::upper_bound(numbers.begin(), numbers.end(), 4);

    // 输出结果
    std::cout << "lower_bound: " << *lowerIt << " at index " << std::distance(numbers.begin(), lowerIt) << std::endl;
    std::cout << "upper_bound: " << *upperIt << " at index " << std::distance(numbers.begin(), upperIt) << std::endl;

    return 0;
}

std::equal_range 函数结合了 std::lower_bound 和 std::upper_bound 的功能，返回一个范围，表示有序序列中等于目标值的元素的区间。
这个函数返回一个 std::pair 对象，其中 first 成员是一个指向第一个等于目标值的元素的迭代器，second 成员是一个指向最后一个等于目标值的元素的迭代器。 若目标不存在则返回空
std::binary_search 是 C++ 标准库中的一个算法，用于在有序序列中判断是否存在目标值。
这个函数返回一个 bool 值，如果在指定的有序序列 [first, last) 中找到了等于 value 的元素，则返回 true；否则返回 false。

求一个vector的和， accumulate(arr.begin(), arr.end(), 0);

容器的复制：
arr2.resize(arr1.size());
copy_n(arr1.begin(), arr1.size(), arr2.begin()); \\ 从arr1中复制5个元素到arr2中
copy_n对于vector不会动态拓展大小，要确保arr2的大小大于arr1。

在做题时， 有时要用到visited，
unordered_set<pair<int, int>> visited; // 不对，因为没哈希函数
bool visited[m][n] // 可以

C++ 非结构化绑定支持pair和tuple， C++17支持vector和数组（未验证）
Python支持元祖，列表，字符串， 用*对剩余元素解包(放到列表里)。

建议对所有的变量在其定义的时候就对其进行初始化，这样可以避免许多无意的错误

C++ lambda函数的递归

岛屿数量

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int row = grid.size(), col = grid[0].size();
        int directions[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        auto dfs = [&](int i, int j, auto&& dfs_ref) -> void{
            grid[i][j] = '2';
            for (auto [dx, dy] : directions) {
                int nx = i + dx, ny = j + dy;
                if (nx < 0 || nx >= row || ny < 0 || ny >= col) continue;
                if (grid[nx][ny] == '1') dfs_ref(nx, ny, dfs_ref);
            }
        };

        int ans = 0;
        for (auto i = 0; i < row; ++i) {
            for (auto j = 0; j < col; ++j) {
                if (grid[i][j] == '1') {
                    ans++;
                    dfs(i, j, dfs);
                }
            }
        }
        return ans;
        
    }
};

visited集合要存pair<int, int>: vis.emplace(1LL*(u+k) << 32 | (l+k));
题目3694

124.二叉树中的最大路径和

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // helper 函数返回左边的最大值和右边的最大值

    int maxPathSum(TreeNode* root) {
        int res = INT_MIN;
        function<int(TreeNode*)> helper = [&](TreeNode* node)-> int {
            if (node == nullptr) return 0;
            int left = max(0, helper(node->left));
            int right = max(0, helper(node->right));
            res = max(res, node->val + left + right);
            return node->val + max(left, right);
        };

        helper(root);
        return res;
        
        
    }
};

C++求次方，开方用math.h库中的pow函数，如平方pow(x, 2)