EI Madrigal's Space
0%

笔试注意点

Posted on Edited on In
踩坑血泪...

输入输出

  1. cin的结束符是空格, 制表符和回车, 读完后结束符仍然在缓冲区. getline的结束符是回车, 读完后结束符不在缓冲区. 读取一行有空格字符串需要getline.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int n;
cin >> n;
cin.ignore();  // 忽略\n
vector<string> s(n);
for (int i = 0; i < n; ++i) {
    getline(cin, s[i]);
}

// 删掉该行所有的回车
string input;
getline(cin, input);
input.erase(remove(input.begin(), input.end(), '\r'), input.end());
input.erase(remove(input.begin(), input.end(), '\t'), input.end());
input.erase(remove(input.begin(), input.end(), '\n'), input.end());
  1. 将空格分隔的字符串读到vector
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
vector<string> split(string input) {
    vector<string> res;
    istringstream ss(input);
    string tmp;
    while (ss >> tmp) {
        res.push_back(tmp);
    }
    return res;
}

vector<string> split(const string &str) {
    vector<string> tokens;
    string::size_type start = 0, end = 0;
    while ((end = str.find(" ", start)) != string::npos) {
        tokens.push_back(str.substr(start, end - start));
        start = end + 1;
    }
    tokens.push_back(str.substr(start));
    return tokens;
}

// 逗号分隔
vector<string> split(string input) {
    vector<string> res;
    istringstream ss(input);
    string tmp;
    while (getline(ss, tmp, ',')) {
        res.push_back(tmp);
    }
    return res;
}
  1. 知道数组大小后，可以直接读到数组中
1
2
3
4
vector<int> nums(n);
for (int i = 0; i < n; ++i) {
    cin >> nums[i];
}
  1. 删除首尾空格
1
2
s.erase(s.find_last_not_of(" ") + 1);
s.erase(0, s.find_first_not_of(" "));
  1. 多个数最大/最小
1
2
min({a, b, c, d, e});
*max_element(nums.begin(), nums.end());

STL总结

  1. int stoi(const string& str, size_t* idx=0, int base=10)：idx指向第一个非数字字符
  2. isalpha(int ch): 头文件cctype
  3. 对map或unordered_map按值排序
1
2
3
4
5
6
7
8
unordered_map<string, int> record{{"a", 2}, {"b", 1}};
vector<pair<string, int>> vec(record.begin(), record.end());
std::sort(vec.begin(), vec.end(),
    [](const pair<string, int>& a, const pair<string, int>& b) {return a.second < b.second;});

for (auto it = vec.begin(); it != vec.end(); ++it) {
    cout << it->first << " ";
}
  1. unordered_map自定义key
    unordered_map<pair<int, int>, int>会报错，需要提供一个hash函数. 如果key不存在，访问仍然成功，返回value对象默认构造值

1
2
3
4
5
6
7
8
9
struct PairHash {
    template<typename T, typename U>
    size_t operator() (const pair<T, U> &x) const {
        auto h1 = hash<T>()(x.first), h2 = hash<U>()(x.second);
        return h1 ^ h2;
    }
};

unordered_map<pair<int, int>, int, PairHash> m;

但是`map`就不需要, map的key类型必须支持`<`运算符
  1. sort(v.begin(), v.end(), [](int a, int b) { return a > b; })或sort(v.rbegin(), v.rend())
  2. vector追加: dest.insert(dest.end(), src.begin(), src.end()). vector<vector<int>>每一维元素个数可以不同
  3. C++ 17的structured binding: for (auto [k, v] : unordered_map)
  4. std::lower_bound和std::upper_bound对于random-access iterators的时间复杂度是\(O(lgn)\)，但对于non-random-access iterators如set::iterator是\(O(n)\)的。这种情况下应使用set自带的setObj.upper_bound(target)，复杂度\(O(lgn)\)
  5. 反向迭代：for (auto it = nums.rbegin(); it != nums.rend(); ++it)
  6. sort记录原始索引：可以先过一遍数组，将数字和索引绑定，然后对pair排序。
  7. string(10, 'x') string res; res += string(10, 'x');

常见算法：

1. 二分答案
2. 数组、哈希表、优先队列、栈、双向队列（在头尾都操作的）
3. 深搜：建图转化
4. 排序
5. 贪心: 从大到小/从小到大排序、单位价值排序
6. 拓扑排序
7. 并查集
8. DP：线性、二维、背包
9. 双指针：对撞、快慢、滑动窗口
10. 模拟
11. 数学：猜答案、打表
12. 前缀和、差分
知识点 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 一维原本：preSum[r] - preSum[l - 1]
// [l, r]区间和：preSum[r + 1] - preSum[l]
vector<int> preSum(n + 1, 0);
for (int i = 1; i <= n; ++i) {
    preSum[i] = preSum[i - 1] + nums[i - 1];
}


// 二维原本：preSum[x2][y2] - preSum[x2][y1 - 1] - preSum[x1 - 1][y2] + preSum[x1 - 1][y1 - 1]
// [x1, y1] -> [x2, y2]区间和：preSum[x2 + 1][y2 + 1] - preSum[x2 + 1][y1] - preSum[x1][y2 + 1] + preSum[x1][y1]
vector<vector<int>> preSum(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; ++i) {
    for (int j = 1; j <= n; ++j) {
        preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + nums[i - 1][j - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Difference {
public:
    Difference(vector<int>& nums) {
        diff = vector<int>(nums.size(), 0);
        diff[0] = nums[0];
        for (int i = 1; i < nums.size(); ++i) {
            diff[i] = nums[i] - nums[i - 1];
        }
    }

    // for every num in [i, j] increase delta
    void increament(int i, int j, int delta) {
        diff[i] += delta;
        if (j + 1 < diff.size()) {
            diff[j + 1] -= delta;
        }
    }

    vector<int> getArr() {
        vector<int> ans(diff.size(), 0);
        ans[0] = diff[0];
        for (int i = 1; i < ans.size(); ++i) {
            ans[i] = ans[i - 1] + diff[i];
        }
        return ans;
    }
private:
    vector<int> diff;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// https://gregable.com/2007/10/reservoir-sampling.html

vector<int> reservoirSampling(vector<int>& nums, int k) {
    vector<int> res(k);
    const int n = nums.size();
    for (int i = 0; i < k; ++i) {
        res[i] = nums[i];
    }
    for (int i = k; i < n; ++i) {
        int random = rand() % i;  // [0, i - 1]
        if (random < k) {  // 概率是 k / i
            res[random] = nums[i];
        }
    }
    return res;
}