【每日算法Day 100】字节跳动 AI Lab 面试编程题（三道）

今天连着面了两次字节跳动，勉强撑到了明天三面。一共三道编程题，做的很烂，这里分享一下。

第一题

给出一条长度为 L 的线段，除了头和尾两个点以外，上面还有 n 个整数点，需要在上面再放 k 个新的点，使得相邻的两个点之间的最大距离最小，求这个最小的距离。

题解

我当时太紧张了，真是脑抽了，还想着弄个优先队列，划分最大的，然后丢进去，再划分最大的，但是是错的。

正确解法小姐姐走了我才想起来，二分答案 m ，然后扫描一遍判断将每一段划分成小于等于 m 的一共需要多少次。如果次数大于 k ，说明 m 太短了，否则说明 m 太长了。

代码

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

int main() {
    int L, n, k;
    scanf("%d%d%d", &L, &n, &k);
    vector<int> a(n+2, 0);
    a[0] = 1;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    a[n+1] = L;
    int l = 1, r = L-1;
    while (l < r) {
        int m = l + (r - l) / 2;
        int cnt = 0;
        for (int i = 1; i <= n+1; ++i) {
            cnt += (a[i] - a[i-1] - 1) / m;
        }
        if (cnt > k) l = m + 1;
        else r = m;
    }
    cout << l << endl;
    return 0;
}

第二题

给出一个数组 A，找到最大的 A[i] - A[j]，要求 i > j。

题解

这题很简单，直接遍历每个 A[i]，维护它前面最小的那个数 minn，然后求出最大的 A[i] - minn 就行了。

代码

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

int main() {
    int n;
    scanf("%d", &n);
    vector<int> a(n, 0);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }
    int minn = a[0], res = INT_MIN;
    for (int i = 1; i < n; ++i) {
        res = max(res, a[i]-minn);
        minn = min(minn, a[i]);
    }
    cout << res << endl;
}

第三题

给定一个字符串，对该字符串进行删除操作，保留 k 个字符且相对位置不变，使字典序最小。

题解

这题也脑抽了，想了一堆方法，dp 复杂度太高，线段树太麻烦，最后用 map 勉强写了一下。

主要思想是这样的，最后要保留 k 个字符，那么第一个字符只能在下标 0 ~ n-k 中寻找，那肯定找最小的啊，如果有多个就找最前面那个，把它的位置记为 pos。

然后第二个字符肯定得在下标 pos ~ n-k+1 中寻找，还是一样的思路，找到以后更新 pos 位置，依次找下去找到 k 个为止。

所以我就利用了 map 的特性，把寻找窗口内的字符个数做一下统计，然后取出 map 中的第一个字符就是字典序最小的了，次数减一，如果减到 0 了就删除掉。

然后从 pos 位置开始遍历，直到第一个等于你刚刚取出的字符为止，更新 pos 位置。

最终的时间复杂度是 $O(n \log n + n \log k)$ ，可以直接看作 $O(n \log n)$ 。

最优解：

最优解当时没想出来，是用单调栈。维护一个递增的单调栈，我们的目标是保留 k 个字符，也就是删除 n-k 个字符。

那么如果栈顶元素大于当前遍历元素，并且还没删够 n-k 个，就出栈，当作删除了一个元素。否则的话如果删够了，不管大小关系统统入栈，因为你没法删了。

最后全遍历完了，如果还没删够，那就继续出栈，直到删够为止。最后把栈里的字符拼接成一个字符串就是答案了。

时间复杂度是 $O(n)$ 的。

代码

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

string f(string s, int k) {
    int n = s.size();
    map<char, int> mp;
    for (int i = 0; i <= n-k; ++i) {
        mp[s[i]]++;
    }
    string res = "";
    int pos = 0;
    for (int i = k; i >= 1; --i) {
        char c = mp.begin()->first;
        res += c;
        for (int j = pos; j <= n-i; ++j) {
            mp[s[j]]--;
            if (!mp[s[j]]) mp.erase(s[j]);
            if (s[j] == c) {
                pos = j + 1;
                break;
            }
        }
        if (i == 1) break;
        mp[s[n-i+1]]++;
    }
    return res;
}

int main() {
    string s;
    int k;
    cin >> s >> k;
    cout << f(s, k) << endl;
}

最优解：

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

string f(string s, int k) {
    int n = s.size();
    k = n - k;
    stack<char> st;
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && st.top() > s[i] && k) {
            st.pop();
            k--;
        }
        st.push(s[i]);
    }
    string res = "";
    while (!st.empty()) {
        if (k) k--;
        else res += st.top();
        st.pop();
    }
    reverse(res.begin(), res.end());
    return res;
}

int main() {
    string s;
    int k;
    cin >> s >> k;
    cout << f(s, k) << endl;
}

关注公众号【算法码上来】，每日算法干货马上就来！