交付四种找法一起验收

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

这是这条路线的最终作品。线性、二分、左右边界、前缀搜索的代码都已给出，其中二分的比较、右边界的记录、前缀树的递归收集三处还空着。补全后一次验完五条：线性找 17 得 2、找 20 得 -1；二分找 24 得 4、找 13 得 0、找 20 得 -1；重复元素里 17 的左右边界是 2 和 4、出现 3 次；补全 app 得到 app、apple、apply；同一个目标二分 3 步、线性 5 步。五条全过输出 验收通过，否则输出 验收失败。

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

提交你的答案

请登录后提交答案。

去登录

← 第四步前缀搜索对拍用的标准答案怎么写 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

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

int lfind(const vector<int>& a, int target) {
    // 线性查找：从头逐个比，找不到返回 -1
    for (int i = 0; i < (int)a.size(); i++) {
        if (a[i] == target) return i;
    }
    return -1;
}

int lsteps(const vector<int>& a, int target) {
    // 线性查找比了几次：找到就停，找不到就是全部比一遍
    int n = 0;
    for (int x : a) {
        n++;
        if (x == target) return n;
    }
    return n;
}

int bfind(const vector<int>& a, int target) {
    // 二分查找（闭区间 [lo, hi]）：找不到返回 -1
    int lo = 0, hi = (int)a.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        // TODO: 相等返回 mid；中点小了 lo = mid + 1；大了 hi = mid - 1
        break;
    }
    return -1;
}

int bsteps(const vector<int>& a, int target) {
    // 二分查找比了几次
    int lo = 0, hi = (int)a.size() - 1;
    int n = 0;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        n++;
        if (a[mid] == target) return n;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return n;
}

int left_bound(const vector<int>& a, int target) {
    // 最左边那个 target 的下标，没有返回 -1
    int lo = 0, hi = (int)a.size() - 1, got = -1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == target) {
            got = mid;
            hi = mid - 1;
        } else if (a[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return got;
}

int right_bound(const vector<int>& a, int target) {
    // 最右边那个 target 的下标，没有返回 -1
    int lo = 0, hi = (int)a.size() - 1, got = -1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == target) {
            // TODO: 相等时记进 got，然后 lo = mid + 1 继续往右找
            break;
        } else if (a[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return got;
}

#include <algorithm>
#include <map>

struct TNode {
    map<char, TNode*> kids;
    bool end = false;      // 有没有一个词在这里结束
};

TNode* build_trie(const vector<string>& words) {
    TNode* root = new TNode();
    for (const string& w : words) {
        TNode* node = root;
        for (char ch : w) {
            if (!node->kids.count(ch)) node->kids[ch] = new TNode();
            node = node->kids[ch];
        }
        node->end = true;
    }
    return root;
}

TNode* walk(TNode* t, const string& pre) {
    // 沿着前缀往下走，走不通返回 nullptr
    TNode* node = t;
    for (char ch : pre) {
        if (!node->kids.count(ch)) return nullptr;
        node = node->kids[ch];
    }
    return node;
}

void collect(TNode* node, const string& cur, vector<string>& out) {
    // 把 node 下面所有的词收进 out
    if (node->end) out.push_back(cur);
    // TODO: 对每个孩子递归收集，路径上加上这个孩子的字符
}

vector<string> suggest(TNode* t, const string& pre) {
    // 所有以 pre 开头的词，按字典序排好
    vector<string> out;
    TNode* node = walk(t, pre);
    if (node != nullptr) collect(node, pre, out);
    sort(out.begin(), out.end());
    return out;
}

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

int main() {
    vector<int> A = {13, 15, 17, 23, 24};
    vector<int> B = {13, 15, 17, 17, 17, 23, 24};
    TNode* t = build_trie({"apple", "app", "apply", "banana"});
    bool c1 = lfind(A, 17) == 2 && lfind(A, 20) == -1;
    bool c2 = bfind(A, 24) == 4 && bfind(A, 13) == 0 && bfind(A, 20) == -1;
    bool c3 = left_bound(B, 17) == 2 && right_bound(B, 17) == 4;
    bool c4 = join(suggest(t, "app")) == "app/apple/apply";
    bool c5 = bsteps(A, 24) == 3 && lsteps(A, 24) == 5 && bfind(A, 24) == lfind(A, 24);
    cout << (c1 && c2 && c3 && c4 && c5 ? "验收通过" : "验收失败") << endl;
}

本次输入：

输出：

👩‍🏫

AI

💬 题目评论

🔒 登录并作答后可看讨论