【农场做题家】C++复习笔记 (基于479道LC Easy 2022/06)

刷完了所有的免费简单题，精炼一下值得复习的C++知识点。出发点是为了帮助更好的做题，不用纠结一些edge case的细节。

• 除了可以用`container.begin()`/`container.end()`，也可以用`begin(container)`/`end(container)`
• 匿名函数`[] (int a, int b) -> bool {...}`，通常和STL一起用
• `INT_MAX`和`INT_MIN`表示32位int的最大值和最小值，此外`std::numeric_limits<int>::max()`和`std::numeric_limits<int>::min()`也可以
• `accumulate` 类似JavaScript里的 `reduce`，可用作对一组数据进行聚合操作，比如：
  

1. std::vector<int> v{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
   
2. int sum = std::accumulate(v.begin(), v.end(), 0); // 1+2+..+10 = 55
   
3. int product = std::accumulate(v.begin(), v.end(), 1, std::multiplies<int>()); // 10! = 3628800

复制代码

• - `stoi`可以把字符串尽可能地转成数字，包括把`30th`转成数字`30`。注意，如果字符串无法转换，会抛出异常。
• `unique` STL方法可以用作去重，不过要注意的是返回值是一个迭代器，通常要配合`resize`或者`erase`使用。
• `next`和`prev`可以用来移动迭代器往后一位和往前一位，类似等同于++和--。
• `all_of`, `any_of` , `none_of` 可以用来简化for循环的判断
• 用C++处理问题时，如果输入是无序的，永远要想一想如果是有序的，解决方案会怎样，很多情况下会有意想不到的惊喜。
• 对`map`按照value排序可以考虑把键值对存放到`vector<pair<K, V>>`，再结合sort函数以及按值的判断式（predicate）。
• `rbegin`和`rbegin`可以用来进行逆序排序，而不需要使用`greater<T>`。也可以用作逆转字符串（比如，回文判断）。
• 全排列可以使用 `do {} while(next_permutation(s.begin(), s.end()))`。
• `priority_queue`默认是最大堆，使用的比较函数是`less<T>`。如果使用最小堆，可以用`priority_queue<int, vector<int>, greater<int>`。
• 如果要同时取最小值和最大值，可以使用`minmax_element`，不过要注意的是，这个函数的返回值是两个迭代器/指针，而非结果数值！
• `string::substr`输入是起始下标及长度，而不是起始和结束下标！
• `bitset` 在初始化的时候只能接受静态预设的长度。
• `toupper`/`tolower`分别用于将字符变成大写和小写。
• `string b = a`, 按值复制，a和b为互不干扰的独立的字符串。
• `nth_element`是quick select算法。
• `iota(s.begin(), s.end(), val)`可以用来生成序列`[val, val + 1, ..)`。注意这里的`s`需要预设长度。
• `equal_range`可以同时返回二分搜索的下限和上限，返回值均为迭代器/指针。
• `isdigit`判断字符是否是数字，`islower`/`isupper`判断字符是否是小/大写，`isalpha`判断字符是否是英文字母，`isalnum`检查字符是否是英文字母或者数字。
• 如果使用匿名函数包括递归，返回值需要使用`function<return_type(argument_types)>`，不能用`auto`。
• 使用`vector.erase(remove_if(vector.begin(), vector.end(), [](int v) {}), vector.end())`可以批量删除元素。
• 使用`unordered_set<char> h(str.begin(), str.end())`可以快速去重字符串中的字符。
• `vector<vector<int>>`之间的比较可以直接使用`==`, 并不需要两层循环。
• `multiset`可以存储多个相同的值，使用`ms.count()`可以拿到对应值出现的次数。
• `vector<T>`的赋值是深度操作，所以可以直接使用`vec_a = vec_b`而无需`vec_a(vec_b.begin(), vec_b.end())`。
• `set_intersection`函数需要输入序列是有序的。
• `set_intersection`函数如果输入是`multiset`，其结果是可以包含重复值的。
• 字符串的startsWith操作可以使用`str.rfind(sub, 0) == 0`完成。
• 使用`vector.back()`可以获取末端的值，通常可以直接拿到上一次计算的结果而不需要使用额外的变量。
• `partial_sum`可以用于计算前缀和。注意目标序列需要有足够的空间。如果不想处理one-off下标的问题，可以用`partial_sum(data.begin(), data.end(), sum.begin() + 1)`。
• 可以使用C语言里的`sscanf(date.c_str(), "%d-%d-%d", &y, &m, &d)`来解析`string`字符串。
• 使用正则表达式仅替换第一次出现的结果`regex_replace("source", regex("pattern"), "replacement", regex_constants::format_first_only)`。
• 多个元素取最值可以使用类似`min({a, b, c})`。
• `is_sorted`函数可以用于检查一个序列是否有序。
• `stringstream(str)`结合`>>`可以用作分割由空格字符隔开的字符串。
• 对于非空格字符隔开的字符串，要完成分割并没有很多其他程序设计语言那么容易。这里有几个常见的方法：
  

1.     // 方法#1：使用C语言里的strtok函数
   
2.     const char* DELIMETERS = " !?',;.";
   
3.     char* pch = strtok(const_cast<char *>(str.c_str()), DELIMETERS);
   
4.     while (pch != NULL) {
   
5.         word = string(pch);
   
6.         pch = strtok(NULL, DELIMETERS);
   
7.     }
   
8.     // 方法#2：使用regex_replace将分割字符替换成空格，接着使用istringstream
   
9.     regex_replace(paragraph, regex("[? ',;.]"), " ");
   
10.     // 方法#3：使用带有引用的range loop来替换分割字符为空格，接着使用istringstream
    
11.     for (auto& c: str) ...

复制代码

• `class`内定义常量数组可以使用`constexpr static int dx[] = {0, 1, 0, -1};`
• `vector.resize(n, 0)`和`vector.assign(n, 0)对于空vector而言均可用于赋值初始值。但若对于非空数组，`resize`仅会对新元素赋值初始值。
• `v << 1`看起来很酷，但是不要滥用，`v + v`和`v * 2`并没有看起来那么糟糕。优先级不清楚就多加括号。
• 移除`vector`末端元素可以考虑`pop_back`或者`resize(a.size() - 1)`。
• 如果输入的类型不匹配，`min`和`max`函数会报错，比如`int`和`unsigned long`，需要将类型统一化再使用。
• 指针地址可以用作哈希表的键值，比如`unordered_map<TreeNode*, int>`。
• GCC常用内置函数：`__builtin_clz`返回二进制表示前置0的个数（Count Leading Zero），数字0需要特殊处理；`__builtin_popcount`返回二进制表示下的1的个数。
• 不管使用`int`类型还是`unsigned int`表示，`-1`的二进制表示都是一样的。
• 字符串从左往右查找第一次出现的字符：`find_first_of("aeiou", c)`；从右向左第一次出现的字符`find_last_of("aeiou", c)`。
• 对于`istringstream`，可以使用`(!(ss >> s))`检查是否还有输入；使用`ss.eof`判断是否到达文件末尾。
• `stable_partition`可以用作将序列分成两组，保证相对位置不变。例如 `stable_partition(v.begin(), v.end(), [](int n){return n>0;})`可以保证前半部分全部是正数，而后半部分是非正数。返回值是指向第二组第一个数字的迭代器。
• `n & -n`取得最低位的数字，比如 `3 & -3 = 110 & 010 = 10`
• `ios_base::sync_with_stdio(0); cin.tie(0);`可以加速cin/cout。
• 对于较长类型，可以使用假名`using iter = vector<int>::const_iterator;`。
• `auto [first, second] = pairs`可以直接得到展开值。
• C++中生成随机数
  

1. #include <random>
   
2. using namespace std;
   
3. default_random_engine defaultEngine;
   
4. // [0, 100]范围，包括0和100
   
5. uniform_int_distribution<int> intDistribution(0, 100);
   
6. cout << intDistribution(defaultEngine);

复制代码

### 写点补充
(不知为何复制下来的文章会吞逗号，有人教教我嘛)
1. >`accumulate`类似JavaScript里的`reduce`可用作对一组数据进行聚合操作
cpp也有reduce,不知道与js的是否类似？
https://zh.cppreference.com/w/cpp/algorithm/reduce
2.
>使用`unordered_set<char>h(str.begin()str.end())`可以快速去重字符串中的字符

是指这种吗，建议发全，免得别人还得分心去搜 https://stackoverflow.com/a/24496379/13792395

3.对于非空格字符隔开的字符串要完成分割并没有很多其他程序设计语言那么容易这里有几个常见的方法：
这个做法更简单 https://stackoverflow.com/a/10058725/13792395

网不好，发重了，抱歉。

mingyEx 发表于 2022-6-15 07:11
### 写点补充
(不知为何复制下来的文章会吞逗号，有人教教我嘛)
1. >`accumulate`类似JavaScript里的`r ...

1. `reduce` 是C++ 17引入的，我还没有用过。刚刚学习了一下，找到一篇不错的关于`reduce`和`accumulate`区别和场景推荐的文章： https://blog.tartanllama.xyz/accumulate-vs-reduce/
不过话说回来，如果是真正在工作当中，我也许会考虑使用`reduce`来进行并行优化。单单是刷题方面，我没看出来非用它不可。

2. `unordered_set<char>h(str.begin(), str.end())` 是用来快速拿到字符串中去重后的字符集，比如从"aaabbbaaaaabbbbbbcccaa"拿到的是字符集{'a', 'b', 'c'}。你分享的stackflow方法是把输依旧保持为字符串"abc"。真正做题的时候，我还没有遇到过必须要转成字符串的情况，很多时候即使拿到目标串，也是要对其字符进行遍历的。写一个简单的for循环更快咯：

1. string str = "aaabbbaaaaabbbbbbcccaa";
   
2. string deduped;
   
3. unordered_set<char> h;
   
4. for (auto c: str) {
   
5.   if (h.count(c)) continue;
   
6.   h.insert(c);
   
7.   deduped += c;
   
8. }

复制代码

3. 感谢补充`std::getline(..)`的用法。唯一要注意的就是它仅仅支持单个的分割字符，比如：

1. string str = "a@b:c";
   
2. istringstream ss(str);
   
3. // 仅处理单个分割字符
   
4. for (string word; getline(ss, word, '@');)
   
5.   cout << word << endl; // a 和 b:c

复制代码

当有多个字符的时候，比较快捷的方法可以考虑使用：

1. string str = "a@b:c";
   
2. // 处理多个分割字符
   
3. for (auto& c: str) if (c == '@' || c == ':') c = ' ';
   
4. istringstream ss(str);
   
5. for (string word; ss >> word;)
   
6.   cout << word << endl; // a，b和c
   

复制代码

Mark, 我也要开始努力

以多个字符分割：
```cpp
vector<string> split(string s, string delimite=" ") {
  std::stringstream stringStream(s);
  std::string line;
  vector<string> wordVector;
  while (std::getline(stringStream, line))
  {
    std::size_t prev = 0, pos;
    while ((pos = line.find_first_of(delimiter, prev)) != std::string::npos)
    {
      if (pos > prev)
        wordVector.push_back(line.substr(prev, pos - prev));
      prev = pos + 1;
    }
    if (prev < line.length())
      wordVector.push_back(line.substr(prev, std::string::npos));
  }
  return wordVector;
}
```

链接很棒，搞题搞腻了可以翻翻那些博客。