小红书0326开发岗笔试总结

写在前面：

小红书的题目算是除拼多多之外比较简单的，就是想不明白为什么第三题可以暴力直接过。

本篇文章仅分享本人解答代码做学习交流，若涉密或侵权可联系我删除。

题目 1

题目描述

凯撒加密，已知密文和滚动长度 3 求明文。

解题方法

水题。

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    for (int i = 0; i < n; i++) {
        s[i] = 'a' + (s[i] - 'a' - 3 + 26)%26;
    }
    cout << s << endl;
}

题目 2

题目描述

在算法中，有各种各样的排序算法，例如归并排序，冒泡排序，快速排序等等。本题中，我们会使用一种新的排序算法：K 排序。

K 排序算法描述如下：首先，算法需要按照某种规则选择该数列上至多 K 个位置，将其对应的数抽出来，其他的数都往左对齐，之后这 K 个数排好序之后依次放在原数列未尾。以上过程算作一次操作。

例如，对于数列 [1, 3, 5, 4, 2]，当 K = 2 时可以选择数字 5 和 4 ，之后数列变成 [1, 3, 2, 4, 5]。

你的任务是：对于给定的数列，你需要计算出最少需要多少次上述操作使得整个数列从小到大排好序?

解题方法

思维题。首先我们可以明确的是：

1. 每一次操作可排序的数为 K 个；
2. 对于未被抽出的数会向左对齐。

因此我们可以得到以下过程：

[1, 3, 5, 4, 2] -> [1, #, #, #, 2] -> [1, 2, #, #, #] -> [1, 2, 3, 4, 5]

我们可以从 1 出发寻找一个上升序列，根据第 2 点这个上升序列我们是不需要排序的，将其余的部分通过若干次排序即可。通过反证法可以得出从 1 出发的必要性。代码如下：

#include<bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        int cnt = 1;
        for (int i = 1; i <= n; i++) {
            int tmp;
            cin >> tmp;
            if (tmp == cnt) {
                cnt++;
            }
        }
        int res = n - cnt + 1;
        cout << res/k + (res%k != 0) << endl;
    }
    return 0;
}

题目 3

题目描述

给出一个数组。你需要求出按顺序对其进行一系列区间操作后最终所得的数组。

操作有三种:

1. 将下标在 L 到 R 之间的元素全部或上 X
2. 将下标在 L 到 R 之间的元素全部与上 X
3. 将下标在 L 到 R 之间的元素全部设为 X

经过一系列操作后输出数组

解题方法

在笔试过程中看到这道题以及数据范围的第一反应是线段树或者差分的方法，调了半天后没调出来，后来暴力过了 82% 就很抽象。赛后看到牛客上基本上都是暴力解法，甚至还有暴力通过 100% 的。先贴一个 82% 的暴力解法，后面等调出来线段树再分享一下。

#include<bits/stdc++.h>

using namespace std;

int main() {
    // 上个读写挂，试图加速
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    int m;
    cin >> m;
    vector<int> ll(m), rr(m), xx(m);
    string sym;
    for (int i = 0; i < m; i++) {
        cin >> ll[i];
    }
    for (int i = 0; i < m; i++) {
        cin >> rr[i];
    }
    cin >> sym;
    for (int i = 0; i < m; i++) {
        cin >> xx[i];
    }
    for (int i = 0; i < m; i++) {
        int l = ll[i] - 1, r = rr[i] - 1, x = xx[i];
        char ch = sym[i];
        if (ch == '=') {
            for (int j = l; j <= r; j++) {
                nums[j] = x;
            }
        }
        else if (ch == '|') {
            for (int j = l; j <= r; j++) {
                nums[j] = nums[j] | x;
            }
        }
        else {
            for (int j = l; j <= r; j++) {
                nums[j] = nums[j] & x;
            }
        }
    }
    cout << nums[0];
    for (int i = 1; i < n; i++) {
        cout << " " << nums[i];
    }
    cout << endl;
}