登录
  • #刷题

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

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



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

Before:
if (keyValueMap.find(key) != keyValueMap.end()) {[br][/br][br][/br]    ...[br][/br][br][/br]}


After:
if (keyValueMap.count(key)) {    ...[br][/br][br][/br]}


2. 【中级】pair可以直接用auto取值或者取址

2.1 用于直观iterate map/unordered_map

Before:
for (auto it = keyValueMap.begin(); it != keyValueMap.end(); it++) {[br][/br][br][/br]    auto key = it->first;[br][/br][br][/br]    auto value = it->second;[br][/br][br][/br]    ...[br][/br][br][/br]}


After:

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


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

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


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

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


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


这里分享给大家,抛砖引玉。

如果感觉有用,欢迎加米,谢谢!

补充内容 (2021-07-10 13:18 +8:00):

经楼下提醒,我觉得有必要补充一下:第三个技巧仅限在OJ上刷题时使用(尤其参数特别多顺序容易错那种),可以非常清楚地列出来参与递归的参数。

但是建议

面试的时候谨慎使用!!

面试的时候谨慎使用!!

面试的时候谨慎使用!!

假如你不打招呼直接这么写,很有可能面试官看不懂,回头feedback给你个差评说你一个dfs非要用lambda,或者看懂了觉得你在炫技。得不偿失。

面试时还是乖乖把helper拎出来写比较好。
37条回复
热度排序

发表回复