9.13百度笔试-算法

一共两道编程题,比较简单,AK了,记录一下第二题的思路:

题目:给定一个n个数的数组,然后进行m次操作,每一次有两个变量t和k,t=1代表对数组前k个数升序排列,t=2代表对数组前k个数降序排列

思路:
看着比较简单,首先用暴力每一次操作以后都重新排序,只能过81%
后来仔细一想,实际是一个单调栈问题,无论前面操作了多少次,只要有一个更大的k值,前面的排序就是无用的,故只需记录一个递减单调栈即可。
还需要注意的一点是,记录了单调递减的单调栈后,由于要依次由栈底到栈顶做排序,故再新创建一个栈(类似于两个栈实现队列功能),利用两个栈实现最终按k值由大到小每次排序。

附上代码:
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    stack<pair<int, int>> q, q2;
    int t, k;
    for (int i = 0; i < m; i++) {
        cin >> t >> k;
        while (!q.empty() && q.top().second < k) {
            q.pop();
        }
        q.push({ t,k });
    }

    while (!q.empty()) {
        q2.push(q.top());
        q.pop();
    }

    while (!q2.empty()) {
        auto temp = q2.top();
        if (temp.first == 1) {
            sort(nums.begin(), nums.begin() + temp.second);
        }
        else {
            sort(nums.begin(), nums.begin() + temp.second, [](int& a, int& b) {
                return a > b;
                });
        }
        q2.pop();
    }

    for (int i = 0; i < n; i++) {
        cout << nums[i] << " ";
    }
}


#百度笔试##百度23秋招笔试编程题有点儿简单啊#
全部评论
第一题可以说下思路吗
点赞 回复 分享
发布于 2022-09-14 16:13 陕西
第一道题是通关吗
点赞 回复 分享
发布于 2022-09-13 22:14 北京
好厉害!!请问您是计算机科班么,我只会傻傻暴力..大佬刷了多少题呀
点赞 回复 分享
发布于 2022-09-13 23:44 湖南
请教一下暴力为什么只能过81%呀?按理来说暴力应该答案也是对的吧,是因为内存的限制吗?
点赞 回复 分享
发布于 2022-09-17 21:39 北京
思路太强了!
点赞 回复 分享
发布于 2022-09-14 14:20 福建
哇 大佬好厉害啊😯
点赞 回复 分享
发布于 2022-09-14 22:12 浙江

相关推荐

4 10 评论
分享
牛客网
牛客企业服务