交付四种技巧一起验收

👁️ 2 人浏览 💬 0 人评论 ❤️ 添加收藏

这是这条路线的最终作品。对撞、快慢指针、固定窗口、暴力对照和差分都已给好，补全三处关键函数：has_cycle、min_len、restore。然后一次验完五条：对撞找和为 40 的两个下标是 2 和 3；中点是 2、无环判 false、有环判 true；固定窗口 k=3 的最大和是 66；可变窗口求出的最短长度和暴力枚举一样；差分做两次区间加后还原成 5 7 7 2 0。五条全过输出 验收通过，否则输出 验收失败。

（本题用 g++ -std=c++17 -O0 编译。）

提交你的答案

请登录后提交答案。

去登录

← 第四步差分百万数据的双重循环 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <utility>
#include <vector>
using namespace std;

string join(const vector<int>& v) {
    string s;
    for (size_t i = 0; i < v.size(); i++) s += (i ? "/" : "") + to_string(v[i]);
    return s;
}

pair<int, int> two_sum(const vector<int>& a, int target) {
    int lo = 0;
    int hi = (int)a.size() - 1;
    while (lo < hi) {
        int s = a[lo] + a[hi];
        if (s == target) return {lo, hi};
        if (s < target) lo++;
        else hi--;
    }
    return {-1, -1};
}

int mid_index(const vector<int>& a) {
    int slow = 0;
    int fast = 0;
    while (fast + 1 < (int)a.size()) {
        slow += 1;
        fast += 2;
    }
    return slow;
}

bool has_cycle(const vector<int>& nxt) {
    // TODO: 先查快指针还能再走两步，再慢一步快两步，相遇返回 true
    return false;
}

int max_window(const vector<int>& a, int k) {
    int s = 0;
    for (int i = 0; i < k; i++) s += a[i];
    int best = s;
    for (int i = k; i < (int)a.size(); i++) {
        s += a[i] - a[i - k];
        if (s > best) best = s;
    }
    return best;
}

int min_len(const vector<int>& a, int target) {
    // TODO: 右端扩大，满足 s >= target 就记长度并收左端
    return -1;
}

int brute_len(const vector<int>& a, int target) {
    int n = (int)a.size();
    int best = n + 1;
    for (int i = 0; i < n; i++) {
        int s = 0;
        for (int j = i; j < n; j++) {
            s += a[j];
            if (s >= target) {
                best = min(best, j - i + 1);
                break;
            }
        }
    }
    return best;
}

void range_add(vector<int>& d, int l, int r, int v) {
    d[l] += v;
    d[r + 1] -= v;
}

vector<int> restore(const vector<int>& d, int n) {
    // TODO: 一路累加，还原出前 n 个位置
    (void)d; (void)n;
    return {};
}

int main() {
    vector<int> a = {13, 15, 17, 23, 24};
    vector<int> w = {17, 8, 15, 13, 23, 24, 19};
    vector<bool> checks;
    auto p = two_sum(a, 40);
    checks.push_back(p.first == 2 && p.second == 3);
    checks.push_back(mid_index(a) == 2 && !has_cycle({1, 2, 3, 4, -1}) && has_cycle({1, 2, 3, 4, 1}));
    checks.push_back(max_window(w, 3) == 66);
    checks.push_back(min_len(w, 50) == brute_len(w, 50));
    vector<int> d(6, 0);
    range_add(d, 0, 2, 5);
    range_add(d, 1, 3, 2);
    checks.push_back(join(restore(d, 5)) == "5/7/7/2/0");
    bool ok = true;
    for (bool c : checks) ok = ok && c;
    cout << (ok ? "验收通过" : "验收失败") << endl;
}

本次输入：

输出：

👩‍🏫

AI

💬 题目评论

🔒 登录并作答后可看讨论