当前位置: 首页 > 面试经验 >

米哈游笔试前端9.14 AC C++

优质
小牛编辑
116浏览
2023-03-28

米哈游笔试前端9.14 AC C++

一个身高序列,排队,相邻两人身高平均数不是整数的,越多越好,输出最终队列

两种思路:

① 奇、偶身高分别一个栈,然后交替出栈入队,最后剩下的全入队。注意,因为每个人对左右都能产生共献,所以要人数多的先入队,比如【偶,奇,偶】

用到了O(N)的额外空间

#include <bits/stdc++.h>
using namespace std;

const size_t MAX_N = 100002;
uint a[MAX_N];

int main() {
    int n;
    cin >> n;
    stack<uint> odd, even;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        if(a[i] & 1) odd.push(a[i]);
        else even.push(a[i]);
    }

    vector<uint> order;
    while(odd.size() && even.size()) {
        if(odd.size() > even.size()) {
            order.push_back(odd.top());
            order.push_back(even.top());
        }
        else {
            order.push_back(even.top());
            order.push_back(odd.top());
        }
        odd.pop();
        even.pop();
    }

    while(odd.size()) {
        order.push_back(odd.top());
        odd.pop();
    }

    while(even.size()) {
        order.push_back(even.top());
        even.pop();
    }

    for(int i = 0; i < order.size(); i++)
        cout << order[i] << (i == order.size() - 1 ? "\n" : " ");
    return 0;
}

② 基本思路同上,但是奇偶各一个链表,少的往多的里面插,变成经典的合并链表,O(1)空间复杂度

代码略

给定字符串,查找存在连续k个"mihoyo"的最短字串,不存在输出-1,存在输出起始、末尾下标

基本思路:找到所有模式串的下标,保存到一个数组,然后按左右下标间隔k,遍历下标数组,计算最短长度

#include <bits/stdc++.h>
using namespace std;

const string TARGET = "mihoyo";
const size_t TARGET_LEN = TARGET.size();

int main() {
    int n, k;
    cin >> n >> k;
    string str;
    cin >> str;
    vector<size_t> mihoyoPosition;
    size_t p = -1;
    // 全部出现位置
    while((p = str.find(TARGET, p + 1)) != string::npos) mihoyoPosition.push_back(p);
    // 不足k个
    if(mihoyoPosition.size() < k) {
        cout << "-1\n";
        return 0;
    }
    // 找结果
    pair<int, int> answer;
    size_t minLength = UINT_MAX;
    int l = 0, r = k - 1;
    while(r < mihoyoPosition.size()) {
        size_t len = mihoyoPosition[r] - mihoyoPosition[l];
        if(len < minLength) {
            minLength = len;
            answer = {mihoyoPosition[l], mihoyoPosition[r] + TARGET_LEN - 1};
        }
        ++l, ++r;
    }
    cout << answer.first << ' ' << answer.second << '\n';
    return 0;
}

一个序列,每一次操作可以使一个数翻倍,使得序列成为严格递增的最少操作次数

计算每一个元素,严格大于前一个数需要翻倍的次数
设是的下一个数
对于,可以解出
再考虑对于每一个数被翻倍后,后面的数理应同等地一起进行翻倍(或者说,需要先翻完前一个数翻倍的次数,再去做“为了大于前一个数而进行的翻倍”)
因此将每一个数需要的存到一个数组里,然后计算前缀和,最后再求和
仔细考虑特殊情况:
① ,即已经满足了严格递增,解出的会是0或负数,负数实际有意义,说明前缀和累加到自己的时候,可以少翻几次。但是前缀和始终应当非负。
② 与恰好差了2的幂次倍数,为了“严格递增”,需要加一
代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const size_t MAX_N = 100002;
int a[MAX_N], mark[MAX_N]; /* 记录每个数的k(大于前一个数需要翻倍的次数) */

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

    for(int i = 1; i < n; i++) {
        int k = int(ceil(log2(a[i - 1]) - log2(a[i])));
        // 如果前后两个正好差2^t倍,多乘一个2(为了严格递增)
        double t = log2(a[i - 1] * 1.0 / a[i]);
        mark[i] = abs(ceil(t) - floor(t)) <= 1E-6 ? k + 1 : k;
    }
    LL ans = 0, sum = 0;
    for(int i = 1; i < n; i++) {
        sum = sum + mark[i];
        if(sum < 0) sum = 0;
        ans += sum;
    }
    cout << ans << '\n';
    return 0;
}
#笔试题目##米哈游笔试##米哈游秋招##米哈游23秋招笔试心得体会#
 类似资料: