8.10 贝壳笔试真题 个人记录

第一题 计算绝对值

这题的数据范围较大,应该用 long long

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;

int main(){
    int n;
    cin >> n;
    vector<long long> arr(n);
    for(int i=0; i<n; i++)
        cin >> arr[i];
    // 记录差值最小的两个数的第一个数的下标
    int res = 0;
    long long iMin = abs(arr[0] - arr[1]);
    for(int i=0; i<n-1; i++){
        long long cur = abs(arr[i] -  arr[i+1]);
        // 当前差值较小,更新最小差值以及下标
        if(iMin > cur){
            iMin = cur;
            res = i;
        }
    }
    cout << arr[res] << ' ' << arr[res+1] << endl;
    return 0;
}

第二题 月光宝盒的密码

最长严格上升子序列,无脑暴力 N^2 能过 82,通过二分法来计算 100

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> arr(n);
    for(int i=0; i<n; i++)
        cin >> arr[i];
    int res = 0;
    vector<int> dp;
    dp.push_back(arr[0]);
    for(int i=1; i<n; i++){
        // 当前元素,大于上升序列数组中的最大值,直接放到最后
        if(arr[i] > dp.back()) dp.push_back(arr[i]);
        else {
            // 找到刚好大于当前数在上升序列数组中的下标
            auto it = upper_bound(dp.begin(), dp.end(), arr[i]);
            // 因为是严格上升,需要判断一下,前面的数是否等于现在的数
            if(it == dp.begin() || *(it-1) != arr[i]){
                *it = arr[i];
            }
        }
    }
    cout << dp.size() << endl;
    return 0;
}

第三题 检查卫生

涉及到连续的题目通常需要部分和思路来计算

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int n, m;
    cin >> n >> m;
    vector<int> arr(n+1, 0);
    // 在赋值的过程中,完成部分和的计算
    for(int i=1; i<=n; i++)
        cin >> arr[i], arr[i] += arr[i-1];
    // 所得分数比较大,用 long long 存放
    long long res = 0;
    // 记录老师们的打分区间,通过部分和的思路,计算出,重叠区域的最大值
    vector<int> brr(n+1, 0);
    for(int i=0; i<m; i++){
        int st, end;
        cin >> st >> end;
        // 如果没有房间会重新打扫的话,应该获得的分数
        res += arr[end] - arr[st-1];
        brr[st-1]++;
        brr[end]--;
    }
    // 计算老师们的打分区间,并算出哪个房间被老师关顾最多,打扫那个房间即可
    int iMax = 0;
    for(int i=1; i<=n; i++)
        brr[i] += brr[i-1], iMax = max(iMax, brr[i]);

    cout << res + iMax << endl;

    return 0;
}

第四题 特殊的测试

不知道为什么,我的代码时间复杂度是 O(N)
就是只过 82%, 改了好多版本,最后优化成下面的样子

#include <iostream>
#include <vector>
using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> arr(n);
    vector<int> dp(n, 0);
    for(int i=0; i<n; i++)
        cin >> arr[i];

    int pre = arr[0];
    for(int i=1; i<n; i++){
        // 把数组从 0 到 i  加成递增需要的数量
        dp[i] = dp[i-1] + max(0, pre - arr[i] + 1);
        pre = max(pre + 1, arr[i]);
    }

    int res = dp.back(), cur = 0;
    pre = arr.back();
    for(int i=n-2; i>=0; i--){
        // 重复加 的部分
        int repeat = min(dp[i] - (i==0 ? 0 : dp[i-1]) , max(0, pre - arr[i] + 1));

        // 把数组从 i 到 n-1 加成递减需要的数量
        cur += max(0, pre - arr[i] + 1);
        pre = max(pre + 1, arr[i]);
        // dp[i] + cur - repeat  这个值为把第 i 个元素变成最大的元素,往左递减,往右递减,需要花费的最小代价
        // 算出每一个情况,取最小
        res = min(dp[i] + cur - repeat, res);
    }
    cout << res << endl;

    return 0;
}

图片说明

#贝壳找房##笔试题目##笔经##秋招##春招##面经#
全部评论
最后一题怕是开long long就过了(
点赞 回复
分享
发布于 2019-08-10 21:05
有题目没大佬
点赞 回复
分享
发布于 2019-08-10 21:05
英特尔
校招火热招聘中
官网直投
第一道题真的一毛一样,我只过了百分之十八😂
点赞 回复
分享
发布于 2019-08-10 21:08
大佬你投的什么岗,我投的测试,好像有三个题是一样的
点赞 回复
分享
发布于 2019-08-10 21:11
大佬你好厉害!
点赞 回复
分享
发布于 2019-08-10 21:18

相关推荐

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