蓝桥杯高频考点——二分（含C++源码）

子串简写

题目链接

满分代码及思路

solution 1（暴力 模拟双指针70分）

对于这道题目其实我首先想到的就是双指针，具体拿这题来说就是，我们现在有两个指针left right 现在要做的就是 在给定的字符串中枚举出所有同时满足：

1.长度大于等于K；
2.以c1开头以c2结尾

以上两个条件的所有子串 对吧
那么就很好办了呀 我们先让left指针找到c1，然后通过不断移动right
枚举出所有以left此时位置为左端点 且满足条件的所有合法情况 每次更新答案count 就好 最后输出一下
但是有几个比较大的样例超时了 这时候我们就需要想办法优化一下：

因为我们这个双指针的方法 主要依靠两个for循环 时间复杂度是O(n*n)

Q:所以我们要思考的是我们可以去优化的点在哪啊？

也就是说这个代码有什么重复且不必要的操作吗？

我觉得这个思考很重要很重要

A:二分相对于双指针优化的点是不是在于c2位置的确定啊 因为双指针需要枚举right每一种情况吧 因为我们就像一个瞎子 我们的right只有走到它的儿子面前才能跟他相认

具体来说，在双指针方法里，对于每一个以 c1 开头的位置，代码需要从 left + K - 1 开始，逐个枚举所有可能的 right 位置，直到找到以 c2 结尾的位置，从而判断是否满足子串长度大于等于 K 的条件

二分查找方法首先记录下所有 c1 和 c2 出现的位置。对于每一个 c1 出现的位置，要寻找满足子串长度大于等于 K 的 c2 位置时，它利用 c2 位置数组的有序性（因为位置是按顺序记录的）进行二分查找
此时我们的right指针他是一个视力很好的人 他知道自己的子女 在这条路的哪个方位

二分查找每次将搜索范围缩小一半，其时间复杂度为 (O(log m))，其中 m 是 c2 出现的次数。对于所有 c1 出现的位置都进行二分查找，整体时间复杂度就是 (O(n log m))，在一般情况下可以近似看作 (O(n log n))，相比于双指针方法的 (O(n^2)) 有了显著的优化。

#include <iostream>
#include <string>

// 引入标准库命名空间
using namespace std;

// 双指针方法
int double_point(int K, const string& S, char c1, char c2) {
    int n = S.length();
    int count = 0;
    for (int left = 0; left < n; ++left) {
        if (S[left] == c1) {
            for (int right = left + K - 1; right < n; ++right) {
                if (S[right] == c2) {
                    ++count;
                }
            }
        }
    }
    return count;
}

int main() {
    int K;
    string S;
    char c1, char c2;

    // 读取输入
    cin >> K;
    cin >> S >> c1 >> c2;

    // 计算结果
    int result = double_point(K, S, c1, c2);

    // 输出结果
    cout << "双指针方法结果: " << result << endl;

    return 0;
}
    

solution 2（二分 AC）

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

// 二分查找方法
int binary_search(int K, const string& S, char c1, char c2) {
    int n = S.length();
    vector<int> start;
    vector<int> end;

    // 记录 c1 和 c2 出现的位置
    for (int i = 0; i < n; ++i) {
        if (S[i] == c1) {
            start.push_back(i);
        }
        if (S[i] == c2) {
            end.push_back(i);
        }
    }

    int count = 0;
    for (int s : start) {
        // 二分查找满足条件的 c2 位置
        int left = 0, right = end.size() - 1;
        int target = s + K - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (end[mid] >= target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        count += end.size() - left;
    }
    return count;
}

int main() {
    int K;
    string S;
    char c1, c2;

    // 读取输入
    cin >> K;
    cin >> S >> c1 >> c2;

    // 计算结果
    int result = binary_search(K, S, c1, c2);

    // 输出结果
    cout << "二分查找方法结果: " << result << endl;

    return 0;
}    

管道

题目链接

满分代码及思路

今天不适合学习 明天写一下