分享几个C++刷题小技巧

烤馒头

注册一亩三分地论坛，查看更多干货！

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

本帖最后由烤馒头于 2021-7-9 09:02 编辑

看隔壁问C++刷题有感，分享几个我从刷题中get的小技巧。有些非常好用甚至反哺到我工作当中。

1. 【初级】把count用做contain查看map/set/unordered_map/unordered_set里是否含有key
Before:

if (keyValueMap.find(key) != keyValueMap.end()) {
...
}

复制代码

After:

if (keyValueMap.count(key)) { ...
}

复制代码

2. 【中级】pair可以直接用auto取值或者取址
2.1 用于直观iterate map/unordered_map
Before:

for (auto it = keyValueMap.begin(); it != keyValueMap.end(); it++) {
auto key = it->first;
auto value = it->second;
...
}

复制代码

After:

for (auto& [key, value] : keyValueMap) {
...
}

复制代码

2.2 直角网格题遍历上下左右四个方向
After:

vector<pair<int, int>> dirs {{0,1}, {1,0}, {0,-1}, {-1,0}};
for (auto& [dx, dy] : dirs) {
int x = i + dx;
int y = j + dy;
...
}

复制代码

3. 【高级】可以用lambda function+capture &节省helper method要写的一堆input argument。例：LC 212
Before:

vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
auto root = buildTrie(words);
unordered_set<string> ans;
int m = board.size();
int n = board[0].size();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
dfs(board, m, n, ans, i, j, root);
}
}
...
}
void dfs(vector<vector<char>>& board, int m, int n, unordered_set<string>& ans, int x, int y, TrieNode* node) {
...
dfs(board, m, n, ans, x+1, y, node);
dfs(board, m, n, ans, x-1, y, node);
dfs(board, m, n, ans, x, y+1, node);
dfs(board, m, n, ans, x, y-1, node);
...
}

复制代码

After:

vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
auto root = buildTrie(words);
unordered_set<string> ans;
int m = board.size();
int n = board[0].size();
function<void(int, int, TrieNode*)> dfs = [&](int x, int y, TrieNode* node) {
...
for (auto& [dx, dy] : dirs) {
dfs(x + dx, y + dy, node);
}
...
};
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
dfs(i, j, root);
}
}
...
}

复制代码

这里分享给大家，抛砖引玉。
如果感觉有用，欢迎加米，谢谢！

补充内容 (2021-07-10 13:18 +8:00):
经楼下提醒，我觉得有必要补充一下：第三个技巧仅限在OJ上刷题时使用（尤其参数特别多顺序容易错那种），可以非常清楚地列出来参与递归的参数。
但是建议
面试的时候谨慎使用！！
面试的时候谨慎使用！！
面试的时候谨慎使用！！
假如你不打招呼直接这么写，很有可能面试官看不懂，回头feedback给你个差评说你一个dfs非要用lambda，或者看懂了觉得你在炫技。得不偿失。
面试时还是乖乖把helper拎出来写比较好。

feitao

1和3都是before比after好

three0s

std::function会对性能有影响，可能会导致被多问问题，啥是type erasure blah blah。能写auto l = []() { ... }的话则没有这个影响（然后可以y-combinator递归...）。lamba的话[&]一般工作也不会这样写。。建议慎用

insomniadog

可能这些刷题能用但是工作中这样写不一定就是好得。代码写的短!=代码写得好。

1 after 这样有个问题：一般对于元素是否包含得判断。都会跟一个如果含了这个元素然后xxx得逻辑，
也就是说会变成

if (keyValueMap.count(key)) {
auto value = keyValueMap[key];
....
}

复制代码

这样就是查找了两次了，还是老老实实用iterator吧。

3 after 存在得问题就是function body 太长。
如果让我来写，应该会尽量把逻辑拆开多加helper function 也就是说反而是1 before更好. 这样至少有以下好处：
A. 能用命名表示这段得逻辑，虽然注释还是要写，但是一个好得命名函数也很重要。在主函数里面看一眼你得helper function，甚至都不用去读那一堆定义。
B. 能在函数声明得时候加各种宏定义，包括不限于const/锁等。
C. 能复用

troybitchen

前两个常用，第三个学习了

烤馒头

troybitchen 发表于 2021-7-9 09:00
前两个常用，第三个学习了

第三个在OJ上做DFS/backtracking比较好用（比如要加visited那种），可以非常清楚地列出来参与递归的参数。
但是面试的时候建议谨慎使用，最好提前询问面试官，不然面试官可能看不懂，回头review说你一个dfs非要用lambda，或者看懂了觉得你炫技。。。

應方

第三個是c++有別於c的進化之一，就是經過一學期的程式設計課後都還未使用就是🤣🤣。這篇好啊，希望更多大佬分享coding小技巧

DriftKingKZ

第三个秀的呀！感谢

dogeyy

第三个直接用auto关键字又可以偷一点懒hhh

烤馒头

dogeyy 发表于 2021-07-09 17:44:09
第三个直接用auto关键字又可以偷一点懒hhh

如果你指的是lambda function定义，在写递归函数时不能用auto。
思考题：想想为什么？

enthusiastic

mark了！很有用~不过我记得auto and lambda是cpp11的嘛，会不会存在面试官编译不了的情况啊（好像国内是会的）

dogeyy

烤馒头发表于 2021-7-10 09:04
如果你指的是lambda function定义，在写递归函数时不能用auto。
思考题：想想为什么？

原来如此，确实是我学艺不精hhh

edwardifun

学习了。。谢谢分享

[学C/C++] 分享几个C++刷题小技巧

注册一亩三分地论坛，查看更多干货！

评分

相关帖子

本帖被以下淘专辑推荐:

评分

评分

评分