✅ 春招备战指南 ✅

💡 学习建议：

• 先尝试独立解题（建议用时：90分钟/套）
• 对照解析查漏补缺
• 配套练习题库

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

春秋招合集 -> 互联网必备刷题宝典🔗

题目一：V字形子数组检测

1️⃣：遍历数组，检查连续的三个元素

2️⃣：判断中间元素是否小于等于两侧元素

3️⃣：计算满足条件的子数组数量

难度：简单

这道题目要求识别数组中形成V形状的连续子数组。通过线性遍历数组并检查每个连续的三元素组是否满足a[i] >= a[i+1] <= a[i+2]的条件，我们可以在O(n)时间内得到答案，实现简单高效。

题目二：字符串有缘分对计数

1️⃣：将字符串按奇偶位置分组

2️⃣：统计各分组中每个字母的出现频率

3️⃣：计算满足字母表距离不超过g的字符对数量

难度：中等

这道题目考察字符串处理和计数技巧。通过将字符串按奇偶位置分组，并统计各组中字符的频率，我们可以快速计算出符合"有缘分"条件的字符对数量。利用数学组合和字母表位置差判断，实现了高效的O(n)时间复杂度解法。

题目三：二维人接雨水问题

1️⃣：按雨滴落地时间排序

2️⃣：计算从当前位置到下一雨滴位置所需的最小速度

3️⃣：维护所有雨滴收集过程中的最大所需速度

难度：中等偏难

这道题目描述了一个需要规划最优路径的时空问题。通过按雨滴落地时间排序，并贪心地计算每次移动所需的最小速度，我们可以确定完成任务所需的最小速度值。这种方法巧妙地处理了时间和空间的约束，时间复杂度为O(n log n)，主要消耗在排序上。

01. V字形子数组检测

问题描述

小基正在分析一些数据序列，他发现了一种特殊的模式，称为"V字形子数组"。对于给定的n个整数构成的数组，如果连续的三个元素a[i]、a[i+1]、a[i+2]满足a[i] >= a[i+1] <= a[i+2]，则这三个元素组成一个V字形子数组。

更形象地说，这样的子数组在图表上绘制时会呈现'V'状，即中间的元素不大于两侧的元素。

小基想知道在给定的数组中，有多少个这样的V字形子数组。请你帮他计算一下。

输入格式

第一行输入一个整数n，表示数组中的元素数量。

第二行输入n个整数，表示数组中的各个元素。

输出格式

输出一个整数，代表满足V字形条件的连续子数组数量。

样例输入

5
5 1 4 2 3

样例输出

2

数据范围

• 
• 

样例 解释说明

样例1	在数组[5,1,4,2,3]中，连续三元素[5,1,4]满足5>=1<=4，形成V字形；连续三元素[4,2,3]满足4>=2<=3，也形成V字形。因此共有2个V字形子数组。

题解

这道题目要求我们找出数组中所有的V字形子数组，即满足a[i] >= a[i+1] <= a[i+2]的连续三个元素。

解题思路非常直接：

1. 遍历数组，对于每个位置i（其中i+2 < n），检查元素a[i]、a[i+1]、a[i+2]是否满足V字形条件。
2. 如果满足条件，计数器加1。
3. 最终返回计数器的值。

这个问题的关键在于正确理解V字形的定义，即中间元素不大于两侧元素。需要注意的是，只需要检查相邻的三个元素，而不是任意三个元素。

时间复杂度分析：

• 我们只需要遍历数组一次，对每个位置执行常数时间的比较操作，因此时间复杂度为O(n)。

空间复杂度分析：

• 除了输入数组外，我们只需要常数级别的额外空间，因此空间复杂度为O(1)。

这种线性遍历的方法非常高效，适用于处理大规模数据。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 读取输入
n = int(input())
nums = list(map(int, input().split()))

# 统计V字形子数组
count = 0
for i in range(n - 2):
    # 检查是否满足a[i] >= a[i+1] <= a[i+2]
    if nums[i] >= nums[i+1] and nums[i+1] <= nums[i+2]:
        count += 1

# 输出结果
print(count)

• Cpp

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

int main() {
    // 读取数组长度
    int n;
    cin >> n;
    
    // 读取数组元素
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    // 计算V字形子数组数量
    int cnt = 0;
    for (int i = 0; i < n - 2; i++) {
        // 检查三个连续元素是否形成V字形
        if (arr[i] >= arr[i + 1] && arr[i + 1] <= arr[i + 2]) {
            cnt++;
        }
    }
    
    // 输出结果
    cout << cnt << endl;
    return 0;
}

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 读取数组长度
        int n = sc.nextInt();
        
        // 读取数组元素
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        // 计算V字形子数组的数量
        int count = 0;
        for (int i = 0; i < n - 2; i++) {
            // 判断是否满足V字形条件
            if (a[i] >= a[i + 1] && a[i + 1] <= a[i + 2]) {
                count++;
            }
        }
        
        // 输出结果
        System.out.println(count);
    }
}

02. 字符串有缘分对计数

问题描述

小柯最近发明了一个名为"有缘分"的字符串位置匹配规则。对于一个长度为 的由小写字母组成的字符串 ，如果有两个不同的位置 和 ，它们满足以下条件：

1. 和 的奇偶性相同（要么都是奇数位置，要么都是偶数位置）
2. 位置 上的字符 和位置 上的字符 在字母表中的位置差不超过

那么，位置 和 被称为是"有缘分的"。

字母表中，'a'是第1个字母，'z'是第26个字母。两个字符在字母表中的位置差，是它们在字母表中相隔的字母个数。例如，'a'与'd'之间隔了'b'和'c'两个字母，所以位置差为2。

现在，小柯想知道，对于给定的参数 和字符串 ，有多少对位置是"有缘分的"。

输入格式

第一行包含两个整数 和 ，分别表示字符串的长度和字母表位置差的约束。

第二行是一个长度为 的字符串 ，仅由小写字母组成。

输出格式

输出一个整数，表示字符串 中有多少对"有缘分的"位置。

样例输入

3 25
aaa

样例输出

1

数据范围

• 
• 
• 字符串 仅由小写英文字母组成

样例 解释说明

样例1	在字符串"aaa"中，位置1和位置3都是奇数位置（位置从1开始计数），且都是字符'a'，位置差为0小于等于25，所以它们是"有缘分的"。总共有1对"有缘分"的位置。
样例2（输入：4 1 acbd，输出：2）	在字符串"acbd"中，位置对(1,3)中的'a'和'b'在字母表中相差1，位置对(2,4)中的'c'和'd'在字母表中相差1，均满足位置差不超过1的条件。所以有2对"有缘分"的位置。

题解

这道题目要求我们计算一个字符串中满足特定条件的位置对数量。"有缘分"的位置对需要满足两个条件：奇偶性相同，以及对应字符在字母表中的位置差不超过g。

解题思路如下：

1. 首先，根据奇偶性将字符串中的字符分成两组：奇数位置组和偶数位置组。

2. 对于每个组，分别统计各个字母的出现频率。我们可以使用一个大小为26的数组，其中索引i对应字母'a'+i的频率。

3. 对于每个组，遍历字母表中的每个字母c：

   • 对于同一个字母，如果它出现了freq次，那么可以形成的"有缘分"对数为freq * (freq - 1) / 2（即从freq个位置中选择2个位置的组合数）。
   • 对于不同的字母对(c1, c2)，如果它们在字母表中的位置差不超过g，那么它们可以形成的"有缘分"对数为freq(c1) * freq(c2)。

4. 将奇数位置组和偶数位置组的结果相加，得到最终答案。

时间复杂度分析：

• 遍历字符串统计频率：
• 计算每个组内的"有缘分"对数：（常数级别）
• 总体时间复杂度：

空间复杂度分析：

• 需要两个大小为26的数组来存储每组的字母频率，空间复杂度为（常数级别）

这种基于频率统计的方法高效处理了问题中的两个约束条件，适合大规模数据处理。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 读取输入
n, g = map(int, input().split())
s = input()

# 按奇偶位置分组统计字符频率
odd_counts = [0] * 26
even_counts = [0] * 26

for i in range(n):
    char_idx = ord(s[i]) - ord('a')
    if i % 2 == 0:  # 偶数位置（从0开始计数）
        even_counts[char_idx] += 1
    else:  # 奇数位置
        odd_counts[char_idx] += 1

# 计算"有缘分"的位置对数量
def count_pairs(counts, g):
    result = 0
    # 计算每个字符自身形成的对数
    for freq in counts:
        result += freq * (freq - 1) // 2
    
    # 计算不同字符之间形成的对数
    for i in range(26):
        for j in range(i + 1, min(i + g + 1, 26)):
            result += counts[i] * counts[j]
    
    return result

# 分别计算奇数位置组和偶数位置组的结果并求和
result = count_pairs(odd_counts, g) + count_pairs(even_counts, g)
print(result)

• Cpp

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

// 计算一个频率数组中的"有缘分"对数
long long count_pairs(const vector<int>& counts, int g) {
    long long result = 0;
    
    // 计算同一字符形成的对数
    for (int freq : counts) {
        result += (long long)freq * (freq - 1) / 2;
    }
    
    // 计算不同字符之间形成的对数
    for (int i = 0; i < 26; i++) {
        for (int j = i + 1; j < 26 && j <= i + g; j++) {
            result += (long long)counts[i] * counts[j];
        }
    }
    
    return result;
}

int main() {
    int n, g;
    string s;
    
    // 读取输入
    cin >> n >> g;
    cin >> s;
    
    // 按奇偶位置分组统计字符频率
    vector<int> odd_counts(26, 0);
    vector<int> even_counts(26, 0);
    
    for (int i = 0; i < n; i++) {
        int char_idx = s[i] - 'a';
        if (i % 2 == 0) { // 偶数位置（