LeetCode一些技巧

数组

1
2
3

vector<int> ret;
ret.back(); // 代表最后的一个元素
ret[ret.size() - 1];

堆

1 2	// 最大堆 priority_queue<pair<int, int>, vector<pair<int, int>>, less<pair<int, int>>> pri_que;

// 最小堆
struct compare {
    bool operator()(ListNode* a, ListNode* b) {
        return a -> val > b -> val;
    }
};

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, compare> pq;
    }
}

// 最小堆
priority_queue<int, vector<int>, greater<int>> pq;

对于greater和less

同一个 greater<int>：

即 greater<int>()(a, b) 等价于 a > b；

在 sort 里表示：大的排前面，而且要加括号 greater<int>()；
在 priority_queue 里表示：大的往下沉，小的留在顶上，而且不用加括号 greater<int>；

循环

善用auto&和冒号循环

vector<int> temp;
for(auto& t : temp) {

}

二分法技巧

1	middle = left + (right - left) / 2

(left + right) / 2 可能会整形溢出。

取值范围

在取值范围比较大的情况下，为了防止溢出，可以采用 int64_t 类型。

[int8_t]
sizeof(int8_t) = 1 byte(s) = 8 bit(s)
MIN = -128
MAX = 127

[int16_t]
sizeof(int16_t) = 2 byte(s) = 16 bit(s)
MIN = -32768
MAX = 32767

[int32_t]
sizeof(int32_t) = 4 byte(s) = 32 bit(s)
MIN = -2147483648
MAX = 2147483647

[int64_t]
sizeof(int64_t) = 8 byte(s) = 64 bit(s)
MIN = -9223372036854775808
MAX = 9223372036854775807

检测结果：

╔══════════════════════════════════════════════════════════════════════╗
║          整数类型取值范围检测（C++ integer type ranges）            ║
╚══════════════════════════════════════════════════════════════════════╝

【一】平台基本整数类型（大小因平台/编译器而异）
------------------------------------------------------------------------
  [short]
  sizeof(short) = 2 byte(s) = 16 bit(s)
  MIN = -32768
  MAX = 32767

  [int]
  sizeof(int) = 4 byte(s) = 32 bit(s)
  MIN = -2147483648
  MAX = 2147483647

  [long]
  sizeof(long) = 4 byte(s) = 32 bit(s)
  MIN = -2147483648
  MAX = 2147483647

  [long long]
  sizeof(long long) = 8 byte(s) = 64 bit(s)
  MIN = -9223372036854775808
  MAX = 9223372036854775807

  [unsigned short]
  sizeof(unsigned short) = 2 byte(s) = 16 bit(s)
  MIN = 0
  MAX = 65535

  [unsigned int]
  sizeof(unsigned int) = 4 byte(s) = 32 bit(s)
  MIN = 0
  MAX = 4294967295

  [unsigned long]
  sizeof(unsigned long) = 4 byte(s) = 32 bit(s)
  MIN = 0
  MAX = 4294967295

  [unsigned long long]
  sizeof(unsigned long long) = 8 byte(s) = 64 bit(s)
  MIN = 0
  MAX = 18446744073709551615

【二】<climits> 极值宏（对应基本类型）
------------------------------------------------------------------------
  -- short --
  SHRT_MIN = -32768
  SHRT_MAX = 32767
  USHRT_MAX = 65535

  -- int --
  INT_MIN = -2147483648
  INT_MAX = 2147483647
  UINT_MAX = 4294967295

  -- long --
  LONG_MIN = -2147483648
  LONG_MAX = 2147483647
  ULONG_MAX = 4294967295

  -- long long --
  LLONG_MIN = -9223372036854775808
  LLONG_MAX = 9223372036854775807
  ULLONG_MAX = 18446744073709551615

【三】<cstdint> 固定宽度整数类型（大小严格固定，跨平台首选）
------------------------------------------------------------------------
  [int8_t]
  sizeof(int8_t) = 1 byte(s) = 8 bit(s)
  MIN = -128
  MAX = 127

  [int16_t]
  sizeof(int16_t) = 2 byte(s) = 16 bit(s)
  MIN = -32768
  MAX = 32767

  [int32_t]
  sizeof(int32_t) = 4 byte(s) = 32 bit(s)
  MIN = -2147483648
  MAX = 2147483647

  [int64_t]
  sizeof(int64_t) = 8 byte(s) = 64 bit(s)
  MIN = -9223372036854775808
  MAX = 9223372036854775807

  [uint8_t]
  sizeof(uint8_t) = 1 byte(s) = 8 bit(s)
  MIN = 0
  MAX = 255

  [uint16_t]
  sizeof(uint16_t) = 2 byte(s) = 16 bit(s)
  MIN = 0
  MAX = 65535

  [uint32_t]
  sizeof(uint32_t) = 4 byte(s) = 32 bit(s)
  MIN = 0
  MAX = 4294967295

  [uint64_t]
  sizeof(uint64_t) = 8 byte(s) = 64 bit(s)
  MIN = 0
  MAX = 18446744073709551615

【四】<cstdint> 固定宽度类型的极值宏
------------------------------------------------------------------------
  -- int8_t / uint8_t --
  INT8_MIN = -128
  INT8_MAX = 127
  UINT8_MAX = 255

  -- int16_t / uint16_t --
  INT16_MIN = -32768
  INT16_MAX = 32767
  UINT16_MAX = 65535

  -- int32_t / uint32_t --
  INT32_MIN = -2147483648
  INT32_MAX = 2147483647
  UINT32_MAX = 4294967295

  -- int64_t / uint64_t --
  INT64_MIN = -9223372036854775808
  INT64_MAX = 9223372036854775807
  UINT64_MAX = 18446744073709551615

【五】最大/最小宽度类型（intmax_t / intptr_t / size_t / ptrdiff_t）
------------------------------------------------------------------------
  [intmax_t]
  sizeof(intmax_t) = 8 byte(s) = 64 bit(s)
  MIN = -9223372036854775808
  MAX = 9223372036854775807

  [uintmax_t]
  sizeof(uintmax_t) = 8 byte(s) = 64 bit(s)
  MIN = 0
  MAX = 18446744073709551615

  [intptr_t]
  sizeof(intptr_t) = 8 byte(s) = 64 bit(s)
  MIN = -9223372036854775808
  MAX = 9223372036854775807

  [uintptr_t]
  sizeof(uintptr_t) = 8 byte(s) = 64 bit(s)
  MIN = 0
  MAX = 18446744073709551615

  [size_t]
  sizeof(size_t) = 8 byte(s) = 64 bit(s)
  MIN = 0
  MAX = 18446744073709551615

  [ptrdiff_t]
  sizeof(ptrdiff_t) = 8 byte(s) = 64 bit(s)
  MIN = -9223372036854775808
  MAX = 9223372036854775807

【六】平台指针宽度（判断 32 位 / 64 位）
------------------------------------------------------------------------
  sizeof(void*) = 8 byte(s)
  ➜ 当前为 64 位平台

════════════════════════════════════════════════════════════════════════
检测完毕！

检测脚本：

#include <iostream>
#include <climits>
#include <cstdint>
#include <limits>
#include <cstddef>
#include <iomanip>

// ─── 辅助宏：打印一行分隔符 ───────────────────────────────────────────────────
#define SEP() std::cout << std::string(72, '-') << "\n"

// ─── 辅助宏：打印类型的 sizeof ────────────────────────────────────────────────
#define PRINT_SIZE(T) \
    std::cout << "  sizeof(" #T ") = " << sizeof(T) << " byte(s) = " \
              << sizeof(T)*8 << " bit(s)\n"

// ─── 辅助宏：用 numeric_limits 打印有符号类型范围 ────────────────────────────
#define PRINT_SIGNED(T) \
    std::cout << "  [" #T "]\n"; \
    PRINT_SIZE(T); \
    std::cout << "  MIN = " << (long long)std::numeric_limits<T>::min() << "\n"; \
    std::cout << "  MAX = " << (long long)std::numeric_limits<T>::max() << "\n\n"

// ─── 辅助宏：用 numeric_limits 打印无符号类型范围 ────────────────────────────
#define PRINT_UNSIGNED(T) \
    std::cout << "  [" #T "]\n"; \
    PRINT_SIZE(T); \
    std::cout << "  MIN = 0\n"; \
    std::cout << "  MAX = " << (unsigned long long)std::numeric_limits<T>::max() << "\n\n"

// ─── 辅助宏：打印 <climits> 宏的值 ───────────────────────────────────────────
#define PRINT_MACRO(name) \
    std::cout << "  " #name " = " << (long long)(name) << "\n"
#define PRINT_UMACRO(name) \
    std::cout << "  " #name " = " << (unsigned long long)(name) << "\n"

int main()
{
    std::cout << std::left;

    // ════════════════════════════════════════════════════════════════════════
    std::cout << "╔══════════════════════════════════════════════════════════════════════╗\n";
    std::cout << "║          整数类型取值范围检测（C++ integer type ranges）            ║\n";
    std::cout << "╚══════════════════════════════════════════════════════════════════════╝\n\n";

    // ════════════════════════════════════════════════════════════════════════
    std::cout << "【一】平台基本整数类型（大小因平台/编译器而异）\n";
    SEP();

    PRINT_SIGNED(short);
    PRINT_SIGNED(int);
    PRINT_SIGNED(long);
    PRINT_SIGNED(long long);

    PRINT_UNSIGNED(unsigned short);
    PRINT_UNSIGNED(unsigned int);
    PRINT_UNSIGNED(unsigned long);
    PRINT_UNSIGNED(unsigned long long);

    // ════════════════════════════════════════════════════════════════════════
    std::cout << "【二】<climits> 极值宏（对应基本类型）\n";
    SEP();

    std::cout << "  -- short --\n";
    PRINT_MACRO(SHRT_MIN);
    PRINT_MACRO(SHRT_MAX);
    PRINT_UMACRO(USHRT_MAX);

    std::cout << "\n  -- int --\n";
    PRINT_MACRO(INT_MIN);
    PRINT_MACRO(INT_MAX);
    PRINT_UMACRO(UINT_MAX);

    std::cout << "\n  -- long --\n";
    PRINT_MACRO(LONG_MIN);
    PRINT_MACRO(LONG_MAX);
    PRINT_UMACRO(ULONG_MAX);

    std::cout << "\n  -- long long --\n";
    PRINT_MACRO(LLONG_MIN);
    PRINT_MACRO(LLONG_MAX);
    PRINT_UMACRO(ULLONG_MAX);
    std::cout << "\n";

    // ════════════════════════════════════════════════════════════════════════
    std::cout << "【三】<cstdint> 固定宽度整数类型（大小严格固定，跨平台首选）\n";
    SEP();

    PRINT_SIGNED(int8_t);
    PRINT_SIGNED(int16_t);
    PRINT_SIGNED(int32_t);
    PRINT_SIGNED(int64_t);

    PRINT_UNSIGNED(uint8_t);
    PRINT_UNSIGNED(uint16_t);
    PRINT_UNSIGNED(uint32_t);
    PRINT_UNSIGNED(uint64_t);

    // ════════════════════════════════════════════════════════════════════════
    std::cout << "【四】<cstdint> 固定宽度类型的极值宏\n";
    SEP();

    std::cout << "  -- int8_t / uint8_t --\n";
    PRINT_MACRO(INT8_MIN);   PRINT_MACRO(INT8_MAX);   PRINT_UMACRO(UINT8_MAX);
    std::cout << "\n  -- int16_t / uint16_t --\n";
    PRINT_MACRO(INT16_MIN);  PRINT_MACRO(INT16_MAX);  PRINT_UMACRO(UINT16_MAX);
    std::cout << "\n  -- int32_t / uint32_t --\n";
    PRINT_MACRO(INT32_MIN);  PRINT_MACRO(INT32_MAX);  PRINT_UMACRO(UINT32_MAX);
    std::cout << "\n  -- int64_t / uint64_t --\n";
    PRINT_MACRO(INT64_MIN);  PRINT_MACRO(INT64_MAX);  PRINT_UMACRO(UINT64_MAX);
    std::cout << "\n";

    // ════════════════════════════════════════════════════════════════════════
    std::cout << "【五】最大/最小宽度类型（intmax_t / intptr_t / size_t / ptrdiff_t）\n";
    SEP();

    PRINT_SIGNED(intmax_t);
    PRINT_UNSIGNED(uintmax_t);
    PRINT_SIGNED(intptr_t);
    PRINT_UNSIGNED(uintptr_t);
    PRINT_UNSIGNED(size_t);
    PRINT_SIGNED(ptrdiff_t);

    // ════════════════════════════════════════════════════════════════════════
    std::cout << "【六】平台指针宽度（判断 32 位 / 64 位）\n";
    SEP();

    std::cout << "  sizeof(void*) = " << sizeof(void*) << " byte(s)\n";
    if (sizeof(void*) == 8)
        std::cout << "  ➜ 当前为 64 位平台\n\n";
    else if (sizeof(void*) == 4)
        std::cout << "  ➜ 当前为 32 位平台\n\n";
    else
        std::cout << "  ➜ 未知平台\n\n";

    std::cout << "════════════════════════════════════════════════════════════════════════\n";
    std::cout << "检测完毕！\n";

    return 0;
}

善用tie和pair

1 2	stack<pair<TreeNode*, int>> st; auto [node, depth] = st.top();

函数返回pair，可以用tie

pair<ListNode*, ListNode*> myReverse(head, tail);

// 这里是 C++17 的写法，也可以写成
// pair<ListNode*, ListNode*> result = myReverse(head, tail);
// head = result.first;
// tail = result.second;
tie(head, tail) = myReverse(head, tail);

双重遍历优化思路

对比两个数组中相同的元素，可以将一个数组存入 unordered_set（哈希表）中，然后再遍历另一个数组去哈希表中查找。这样可以将寻找交点的时间复杂度从 $O(N^2)$ 降到 $O(N)$ 。

树形动态规划

在树的动态规划问题中，通常只要是从底向上（后序遍历）收集信息，我们都可以尝试在递归归的过程中直接消化掉这些信息，从而省去额外的存储结构。

两种搜索方法

广度优先搜索（BFS）：就像一块石头丢进水里，水波纹一层一层向外扩散。通常借助**队列（Queue）来实现。
深度优先搜索（DFS）：就像走迷宫，认准一个方向一条路走到黑，碰壁了再退回来走另一条路。通常借助递归（Recursion）或栈（Stack）**来实现。

数组初始化

一些数组初始化赋值方法。

class A {
public: 
    vector<vector<int>> graph;
    vector<int> visited;
void buildGraph(int num) {
    // graph = vector<vector<int>>(num);
    graph.resize(num);
    // visited = vector<int>(num, 0);
    visited.assign(numCourses, 0);
}

三色标记法

对于一些标记数组，可以不使用 true/false 的这种 bool 数组，而是使用 int 数组表示多种状态，如 0 表示未访问、1 表示访问中、2 表示已访问。

vector和list元素操作

vector：

vector<int> vec = {10, 20, 30, 40, 50};
vector<int> vec2 = {90, 100};

// ---访问元素---

int first = vec.front(); // 获取第一个元素 (10)
int last = vec.back();   // 获取最后一个元素 (50)
int second = vec[1];     // 通过索引访问 (20)

// ---插入元素---
vec.insert(vec.begin(), 10); // 在开头前插入一个元素（10）
// 现在 vec 变成: {10, 10, 20, 30, 40, 50}
vec.insert(vec.begin(), vec2.begin(), vec2.end()); // 在开头前插入一个vector
// 现在 vec 变成: {90, 100, 10, 10, 20, 30, 40, 50}

vec.emplace(vec.begin() + 1, 20); // 在第二个元素前插入一个元素（20）
// 现在 vec 变成: {90, 20, 100, 10, 10, 20, 30, 40, 50}

// ---删除元素---

// 1. 删除最后一个元素
vec.pop_back(); 
// 现在 vec 变成: {90, 20, 100, 10, 10, 20, 30, 40}

// 2. 删除索引为 2 的元素 (即第三个元素 '100')
vec.erase(vec.begin() + 2); 
// 现在 vec 变成: {90, 20, 10, 10, 20, 30, 40}

// 3. 删除一个区间，左闭右开区间 [first, last)
// 删除从索引 1 到 2 的元素
vec.erase(vec.begin() + 1, vec.begin() + 3);
// 现在 vec 变成: {90, 10, 20, 30, 40}

list：

list<int> lst = {10, 20, 20, 30, 40, 50};

// ---访问元素---

int first = lst.front(); // 返回10
int last = lst.back();   // 返回50
// 注意：不能使用 lst[1] 访问！

// ---插入元素---

// 在头部插入一个元素
lst.push_front(10);
// 现在 lst 变成: {10, 10, 20, 20, 30, 40, 50}

// 在尾部插入一个元素
lst.push_back(10);
// 现在 lst 变成: {10, 10, 20, 20, 30, 40, 50, 10}

// ---删除元素---

// 删除头部元素
lst.pop_front();
// 现在 lst 变成: {10, 20, 20, 30, 40, 50, 10}

// 删除尾部元素
lst.pop_back();
// 现在 lst 变成: {10, 20, 20, 30, 40, 50}

// 删除指定值
lst.remove(20);
// 现在 lst 变成: {10, 30, 40, 50}

// 转化为vector
vector<int> vec(lst.begin(), lst.end());
vector<int> vec = vector<int>(lst.begin(), lst.end());

获取字符串子串

使用成员函数 substr()。该函数接受两个参数：起始位置（pos）和长度（len），并返回一个从指定位置开始、指定长度的子串。若不指定长度，则默认提取到字符串结尾。

string s1 = "Hello, World!";
// 从下标7开始，截取5个字符
string s2 = s1.substr(7, 5); // s2 = "World"
// 从下标7开始，截取到末尾
string s3 = s1.substr(7);    // s3 = "World!"

枚举思路——以N皇后为例

我们很容易看出需要使用枚举的方法来求解这个问题，当我们不知道用什么办法来枚举是最优的时候，可以从下面三个方向考虑：

子集枚举：可以把问题转化成「从 $n^2$ 个格子中选一个子集，使得子集中恰好有 $n$ 个格子，且任意选出两个都不在同行、同列或者同对角线」，这里枚举的规模是 $2^{n^2}$ ；
组合枚举：可以把问题转化成「从 $n^2$ 个格子中选择 $n$ 个，且任意选出两个都不在同行、同列或者同对角线」，这里的枚举规模是 $\binom{n^2}{n}$ ；
排列枚举：因为这里每行只能放置一个皇后，而所有行中皇后的列号正好构成一个 $1$ 到 $n$ 的排列，所以我们可以把问题转化为一个排列枚举，规模是 $n!$ 。

带入一些 $n$ 进这三种方法验证，就可以知道哪种方法的枚举规模是最小的，这里我们发现第三种方法的枚举规模最小。这道题给出的两个方法其实和排列枚举的本质是类似的。

二分法

可以手写/调库。

// 手动实现二分法
int left = 0, right = end_col;
while (left <= right) {
    int mid = left + (right - left) / 2;
    if (matrix[i][mid] == target) {
        return true;
    } else if (matrix[i][mid] < target) {
        left = mid + 1;
    } else {
        right = mid - 1;
    }
}
// 调库二分法 [左闭右开)
// lower_bound：在一个已排序的范围内，查找第一个大于等于（即 >=）给定值的元素，返回指向该元素的迭代器。
// upper_bound：找第一个 大于 target 的位置
vector<int> v = {10, 20, 30, 30, 30, 40, 50};
int target = 30;
// 这里 auto 是 vector<int>::iterator
auto lo = lower_bound(v.begin(), v.end(), target, less<int>());
auto hi = upper_bound(v.begin(), v.end(), target, less<int>());

// upper_bound内部比较器逻辑
comp(target, *it)   // 第一个参数是 target，第二个参数是容器中的元素

// 直接返回存在/不存在
bool exists = std::binary_search(v.begin(), v.end(), target, less<int>());

// 转为下标
// 如果目标不存在，两者都指向第一个比它大的元素
int lo_idx = lo - v.begin(); // 2
int hi_idx = hi - v.begin(); // 5

// 注意不能直接用 *lo == target 而不检查 lo != v.end()，否则越界
if (lo != v.end() && *lo == target) {
    // target 存在
} else {
    // target 不存在
}

字符串转数字

使用 stoi 函数：

1
2
3

std::string s = "12345";
int i = std::stoi(s); // 将 "12345" 转换为整数 12345
std::cout << i << std::endl;

可以用：

isdigit：检查是否为数字
isalpha: 检查是否为字母。
isalnum: 检查是否为字母或数字。
islower / isupper: 检查是否为小写/大写字母。
isspace: 检查是否为空格、制表符或换行符。

这些函数返回的是 int 而非 bool，非零值表示真，0 表示假。

string s = "5aZ \t!";

s.size(); // 返回6

isdigit(s[0]); // 返回非零值
isalpha(s[1]); // 返回非零值
isalnum(s[2]); // 返回非零值
islower(s[1]); // 返回非零值
isupper(s[2]); // 返回非零值
isspace(s[3]); // 返回非零值
isspace(s[4]); // 返回非零值
isalnum(s[5]); // 返回0

multiset（多重有序集合）性质

multiset 和 set 很像，但它允许重复元素。
可以把它理解为一个自动排序的有序容器（默认从小到大），但它不支持像 nums.begin() + x 这样的随机访问，只能通过 ++ 或 -- 逐步移动迭代器。

// 默认从小到大
multiset<int> ms;

// 从大到小
multiset<int, std::greater<int>> ms2 = {5, 1, 3, 1, 4};
// 遍历结果: 5 4 3 1 1

// 插入元素
ms.insert(60);
ms.insert(20);
ms.insert(20);
ms.insert(10);
ms.insert(10);
ms.insert(10);

// 删除所有的 10
ms.erase(10);
// 结果: 20 20 60

multiset<int>::iterator it = ms.begin(); // 指向第一个20
it++; // 指向第二个20
it++; // 指向60

判断奇数

可以使用 n & 1 判断是否为奇数。

数字 1 的二进制表示非常特殊：它的最低位是 1，前面的所有高位都是 0（例如对于 8 位整数，它是 0000 0001）。

在计算机中，二进制数的最低位（最后一位）决定了奇偶性：

偶数的二进制最低位一定是 0。
奇数的二进制最低位一定是 1。

所以，当我们计算 n & 1 时：

假如 n 是奇数（例如 5）：

  5 的二进制:  ...0000 0101
  1 的二进制:  ...0000 0001
---------------------------
  按位与结果:  ...0000 0001  (十进制为 1，在 if 语句中代表 true)

假如 n 是偶数（例如 4）：

  4 的二进制:  ...0000 0100
  1 的二进制:  ...0000 0001
---------------------------
  按位与结果:  ...0000 0000  (十进制为 0，在 if 语句中代表 false)

获取最值

可以使用 max_element 和 min_element 获取最大和最小值。

// static bool abs_compare(int a, int b) {
//     return (abs(a) < abs(b));
// }

struct abs_compare {
    bool operator()(int a, int b) {
        return (abs(a) < abs(b));
    }
};

int main() {
    vector<int> v = {3, 1, -14, 1, 5, 9};
    vector<int>::iterator result;
    result = max_element(v.begin(), v.end());
    cout << "max element at:" << distance(v.begin(), result) << endl;
    
    // result = max_element(v.begin(), v.end(), abs_compare);   // 传函数指针
    result = max_element(v.begin(), v.end(), abs_compare()); // 传结构体实例，加括号
    cout << "max element (absolute) at:" << distance(v.begin(), result) << endl;
    return 0;
}

// max_element 的大致内部逻辑
// 传入的比较函数 comp 能够回答一个问题：“前一个元素是否比后一个元素小？”s
auto current_max = first; // 假设第一个元素就是最大值
for (auto it = first + 1; it != last; ++it) {
    // 【关键点】如果当前认为的最大值，"小于"下一个元素
    if ( comp(*current_max, *it) ) { 
        current_max = it; // 那么最大值易主
    }
}
return current_max;