在刷了几百道LeetCode之后，我总结出了这几条刷题技巧

作者 | 梁唐

大家好，我是梁唐。

最近参加了几周LeetCode周赛，找回了一些当年比赛的感觉，也简单总结了一些常用的技巧，希望能够帮助到大家。

string的修改

首先来聊聊string类型的修改，众所周知，string是C++当中的字符串类型，我们可以很方便地对字符串进行拼接以及比较等处理。

关于string类型要注意什么呢？要注意每一次的赋值是一个

的操作，这里的n指的是字符串的长度。

比如这周周赛有一题需要我们在一个字符串当中插入空格，很多同学是这样写的：

string ret;
if (xxxx) {
    ret = ret + ' ';
}else ret = ret + s[i];

C++在执行这样的语句的时候会首先执行等号右侧，将ret拼接上一个新的字符得到一个新的字符串之后存储在一个临时变量当中。在赋值的时候，再复制给左侧的ret。其中涉及到拷贝操作，是一个

的复杂度，非常容易超时。

正确的做法是什么呢？正确的做法是调用string当中的api直接对字符串本身进行修改。string类和vector类一样有push_back和pop_back的方法，调用这两个方法可以完成往末尾插入字符以及弹出字符的操作，所以正确的写法是：

string ret;
if (xxxx) {
    ret.push_back(' ');
}else ret.push_back(s[i]);

递归传引用

我们经常会有一些递归的问题，需要传入一个vector或者是map等容器。这个时候切记传入引用，原理和上述一样。因为如果是值传递的话，会涉及到大量的拷贝，会使得时间复杂度非常高。

而传引用的话则不会有这个问题。

void dfs(int n, vector<int> &nums, map<int, int> &mp) {
    ...
}

尤其是在面试的时候，面试官对于这些细节尤其在意，一不小心很容易扣分。

匿名函数

C++当中也有匿名函数，在一些情况下使用匿名函数会非常方便。

C++中的匿名函数有许多种用法，这里不一一列举，只说最简单的用法，其余的用法会在之后的EasyC++系列当中更新。

C++中匿名函数的写法是：

[capture list] (params list) mutable exception-> return type { function body }

Capture list 表示捕获外界变量列表， params list 表示的是参数列表，mutable 用来说明是否可以修改捕获的变量，exception 表示异常， return type是返回类型，function body则是函数体。

一般我们会进行一些省略，最常用的形式有以下三种：

[capture list] (params list) -> return type {function body}
[capture list] (params list) {function body}
[capture list] {function body}

第一种声明的是const类型的表达式，不能在函数体中修改捕获的外部变量。

第二种省略了return类型，编译器会根据函数体中的内容自行推断。

第三种省略了参数列表和返回类型，表示一个无参函数。

有了匿名函数，可以简化一些场景的代码编写，例如对一个复杂的结构体进行排序。通常我们需要单独实现一个cmp函数传入sort方法当中。有了匿名函数之后，我们可以通过匿名函数来实现这点：

sort(nodes.begin(), nodes.end(), [](auto &x1, auto &x2) -> bool {
    return x1.second < x2.second;
});

lower bound和upper bound

很多同学对于实现二分非常头疼，好在C++ STL当中也提供了现成的函数可以使用，分别是lower_bound和upper_bound。

这两者都是二分，二分的范围略有区别，lower_bound的定义是找到第一个可以插入 __val 的位置，并且不改变原有排序。假设我们二分的目标是x，也就是找到第一个大于等于x的位置。

而upper_bound的定义是找到最后一个可以插入 val 而不改变原来有序数组的排序位置，也就是找到第一个大于x的位置。

用法非常简单，传入三个参数，分别是数组的开始位置，数组的结束位置以及查找的值：

int x = 3;
auto it = upper_bound(nums.begin(), nums.end(), x)

函数返回的结果是一个迭代器，如果我们想要获取下标， 可以用它减去数组的初始位置：

int x = 3;
int p = upper_bound(nums.begin(), nums.end(), x) - nums.begin();

灵活使用这两个函数可以应付绝大多数二分的问题，不仅可以简化代码量，也可以提高准确度。

好了，关于LeetCode刷题中常用的几个技巧就先分享到这里，如果大家还知道一些其他的技巧，欢迎在评论区补充。