小红书笔试 java后端 时间2小时

题型 ： 20道选择题，3道算法题。

选择题目：

主要是操作系统和java基本知识，还有一些代码的执行，还有c++代码的执行，大概就这些吧，还有一些mysql的基本sql语句。（忘的差不多，20分钟速过）

算法题：

第一道：（通过率100%）

有一个操作，叫suc(), suc('a') = 'b', 定义一个操作是使用三次suc, 一次操作之后就是'a' 变成了‘d’, 'z' 变成'c',现在给你一个字符串是操作之后的，要你给出之前的，如给你一个def ， 你要输出abc

代码：

很简单，balalalalala

第二道：（通过率0%）

大概题意是，给一个无序数组，然后定义一种k排序方式，就是每次可以选择不多于k个数组中的位置的数，然后排序放在最后，问最少移动次数。这个k不要求连续的。（读错题.....）

样例要求：

n k

输入数组的数组a【】

样例1：

输入

5 2

1 2 3 4 5

输出

0

样例2

输入

5 2

5 4 3 2 1

输出

2

代码

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5+ 10;

int a[N];

int main()
{
    unordered_map<int,int> hash;
    priority_queue<int,vector<int>,greater<int>> heap;
    int n,k;
    cin >> n >> k;
    int res = 0;

    for(int i = 0 ; i < n ; i++) cin >> a[i];

    for(int i = 0 ; i < n ; i++)
    {
        hash[a[i]] = i;
        heap.push(a[i]);
    }
    
    auto t1 = heap.top();
    heap.pop();

    if(heap.size())
    {
        for(int i = 1 ; i < n ; i++)
        {
            auto t = heap.top();
            heap.pop();
            if(hash[t] > hash[t1]) {
                t1 = t;
                continue;
            }
            else {
                res = (n - i + k - 1) / k ;
                break;
            }
        }
    }
    
    cout << res;

    return 0;
}

第三题：（通过率86%）

给一个数组

定义三种操作

1.从l到r位置全部&x

2.从l到r位置全部 |x

3.从l到r位置全部 =x

问最后的数组，时间复杂度要求（n = 1e5）应该是要求nlogn了

代码：

我用暴力模拟的，但是正解应该是线段树，但是菜菜不会写啊！