蚂蚁集团笔试 蚂蚁集团软件算法笔试

订阅专栏，方便查阅，时刻更新各厂软件算法笔试https://blog.nowcoder.net/zhuanlan/0oDWVm

题目1：

小红拿到了一个数组，她可以进行怡好一次操作:选择两个相邻元素将它们合井，合并后的新元素为原来的两个元素之和。

小红想知道，操作1次后数组的极差的最小值是多少？

数组的极差为:数组的最大值减最小值。

输入描述

第二行输入n个正整数ai，代表数组的元素。

2<=n<10^5，1<ai<10^9

输出描述

一个整数，代表操作后的极差最小值。

输入

3

1 4 5

输出

0

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

int n;
vector<int> a, pre_max, pre_min, suf_max, suf_min;

int get_max(int i) {
    int ret = a[i] + a[i+1];
    if (i+2 < n) {
        ret = max(ret, suf_max[i+2]);
    }
    if (i-1 >= 0) {
        ret = max(ret, pre_max[i-1]);
    }
    return ret;
}

int get_min(int i) {
    int ret = a[i] + a[i+1];
    if (i+2 < n) {
        ret = min(ret, suf_min[i+2]);
    }
    if (i-1 >= 0) {
        ret = min(ret, pre_min[i-1]);
    }
    return ret;
}

int main() {
    cin >> n;
    a.resize(n);
    pre_max.resize(n);
    pre_min.resize(n);
    suf_max.resize(n);
    suf_min.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    pre_max[0] = pre_min[0] = a[0];
    for (int i = 1; i < n; i++) {
        pre_max[i] = max(pre_max[i-1], a[i]);
        pre_min[i] = min(pre_min[i-1], a[i]);
    }

    suf_max[n-1] = suf_min[n-1] = a[n-1];
    for (int i = n-2; i >= 0; i--) {
        suf_max[i] = max(suf_max[i+1], a[i]);
        suf_min[i] = min(suf_min[i+1], a[i]);
    }

    int ans = INT_MAX;
    for (int i = 0; i < n-1; i++) {
        int mx = get_max(i);
        int mi = get_min(i);
        ans = min(ans, mx-mi);
    }

    cout << ans << endl;
    return 0;
}

题目2：

小红非常喜欢‘R’字符，而不喜欢‘B’字符。因此她定义字符串的权值为字符‘R’的出现次数。例如