C++技巧

C++ 技巧与笔记

算法专题：LeetCode 373. 查找和最小的 K 对数字

核心思维切入点

1. “求前 K 个最小/大”：第一反应永远是 堆（优先队列，Priority Queue）。
2. “多个有序数组”：立刻联想到 多路归并（Multi-way Merge），模型类似于“合并 K 个有序链表”。

多路归并模型

将题目看作 $m$ 个有序链表（其中 $m = \text{nums1.size()}$）：

• 链表 1: (nums1[0], nums2[0]), (nums1[0], nums2[1]), (nums1[0], nums2[2])...
• 链表 2: (nums1[1], nums2[0]), (nums1[1], nums2[1]), (nums1[1], nums2[2])...
• …
• 链表 i: (nums1[i], nums2[0]), (nums1[i], nums2[1]), (nums1[i], nums2[2])...

利用最小堆维护每个链表的当前指针，每次弹出堆顶（当前最小和），并将该链表的下一个元素推入堆中。

C++ std::priority_queue 进阶用法

1. 最大堆 vs 最小堆

• 最大堆（默认）: std::priority_queue<int> pq;
• 最小堆: std::priority_queue<int, std::vector<int>, std::greater<int>> pq;

2. 自定义比较函数（Lambda 或 Struct）

在处理复杂对象（如坐标索引）时，通常需要自定义比较逻辑：

// 使用 Struct 定义（推荐，易于重用）
struct Compare {
    bool operator()(const vector<int>& a, const vector<int>& b) {
        // 返回 true 表示 a 的优先级低于 b（即 a 排在后面）
        // 在 priority_queue 中，若要实现【最小堆】，需要让大的值返回 true
        return a[0] + a[1] > b[0] + b[1]; 
    }
};
priority_queue<vector<int>, vector<vector<int>>, Compare> minHeap;

// 使用 Lambda 表达式
auto cmp = [](const pair<int, int>& a, const pair<int, int>& b) {
    return a.first + a.second > b.first + b.second; // 最小堆
};
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);

字符串处理：C++17 std::from_chars

在 C++17 中，<charconv> 头文件提供了极高性能的字符/数字转换函数，适用于对性能有严苛要求且不需要区域设置（Locale）支持的场景。

判断字符串是否为数字

相比 stoi（会抛异常）或 sscanf（速度慢且不够安全），std::from_chars 是最佳实践。

#include <charconv>
#include <string_view>
#include <system_error>

bool isNumber(std::string_view sv) {
    double val;
    // std::from_chars 返回 std::from_chars_result 结构体
    // ptr: 指向第一个未转换字符的指针
    // ec:  错误码 (std::errc)
    auto [ptr, ec] = std::from_chars(sv.data(), sv.data() + sv.size(), val);
    
    // 检查是否转换成功，且转换到了字符串末尾
    return ec == std::errc{} && ptr == sv.data() + sv.size();
}

核心优势

• No Exceptions: 不会抛出异常，通过返回错误码处理。
• No Allocation: 零内存分配。
• Locale Independent: 不受系统语言环境影响，结果确定。
• Fast: 比 stringstream 或 sprintf 快得多。