✅ 春招备战指南 ✅

💡 学习建议：

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

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

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

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

题目总结

题目一：区间未出现的最小值之和

1️⃣：统计全为1的子数组数量和全为0的子数组数量，利用公式计算

2️⃣：利用数学公式 n(n+1) - 2N0 - N1 计算最终答案

难度：中等

这道题目的关键在于理解 mex 的概念，并发现对于只含 0 和 1 的数组，mex 值只可能是 0、1 或 2。通过数学推导，我们可以得到一个 O(n) 的高效解法，避免了暴力枚举所有子数组。

题目二：信用评分特征选择

1️⃣：解析输入的二维列表数据

2️⃣：使用决策树算法评估特征重要性

3️⃣：返回重要性最高的特征索引

难度：中等

这道题目结合了数据解析和机器学习算法，需要理解决策树中特征重要性的计算方法。通过计算基尼不纯度或信息增益，可以找出对分类最有帮助的特征。

题目三：棋盘炮台攻击计数

1️⃣：使用哈希表存储每个坐标轴上的炮台位置

2️⃣：对坐标列表排序，便于二分查找

3️⃣：对每个炮台，检查四个方向是否能形成攻击链

难度：中等偏难

这道题目需要理解特殊的攻击规则，并设计高效的数据结构来存储和查询炮台位置。通过二分查找，我们可以快速定位炮台并检查是否能形成攻击链，实现 O(n log n) 的时间复杂度。

01. 区间未出现的最小值之和

问题描述

小基 最近在研究一种特殊的数列性质。她定义了一个数组的 值为：该数组中没有出现过的最小非负整数。例如，数组 的 值是 ，数组 的 值是 。

现在，小基 有一个只包含 和 的数组，她想知道这个数组所有可能的连续子数组的 值之和是多少。

请注意，一个长度为 的数组共有 个连续子数组。

输入格式

第一行输入一个正整数 ，代表数组的大小。

第二行输入 个非负整数 ，代表数组的元素。

输出格式

输出一个整数，表示所有连续子数组的 值之和。

样例输入

3
1 1 0

样例输出

5

样例1	区间 的 是 区间 和 的 是 其余区间的 是

数据范围

题解

这道题目看起来可能有些复杂，但实际上有一个非常巧妙的解法。让我们一步步来分析。

首先，我们需要理解 的概念：一个数组的 是该数组中未出现的最小非负整数。由于题目中的数组只包含 和 ，所以任何子数组的 值只可能是 、 或 ：

• 如果子数组中没有 （即全是 ），那么
• 如果子数组中没有 （即全是 ），那么
• 如果子数组中既有 又有 ，那么

我们的目标是计算所有子数组的 值之和。一个直观的思路是枚举所有子数组，但这样做的时间复杂度是 ，对于 最大为 的情况会超时。

更高效的方法是：

1. 计算 的子数组数量（记为 ）
2. 计算 的子数组数量（记为 ）
3. 计算 的子数组数量（记为 ）

然后总和就是 。

由于总子数组数量是 ，所以 ，因此 。

代入公式，我们得到：

所以我们只需要计算 和 即可。

• 是全为 的子数组数量：我们可以找出所有连续的 的段落，对于长度为 的段落，它包含 个子数组。
• 是全为 的子数组数量：同理，对于长度为 的连续 段落，它包含 个子数组。

最终的答案就是 。

时间复杂度：，我们只需要遍历数组两次，分别计算 和 。 空间复杂度：，用于存储输入数组。

这个解法的巧妙之处在于，我们没有直接枚举所有子数组，而是通过数学方法计算出了答案，大大降低了时间复杂度。

参考代码

• Python

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

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

# 计算全为1的子数组数量 N0
n0 = 0
c = 0
for i in range(n):
    if a[i] == 1:  # 如果当前元素是1
        c += 1     # 连续1的计数器加1
    else:
        # 计算当前连续1段的子数组数量并累加
        n0 += c * (c + 1) // 2
        c = 0      # 重置计数器
# 处理数组末尾可能的连续1
n0 += c * (c + 1) // 2

# 计算全为0的子数组数量 N1
n1 = 0
c = 0
for i in range(n):
    if a[i] == 0:  # 如果当前元素是0
        c += 1     # 连续0的计数器加1
    else:
        # 计算当前连续0段的子数组数量并累加
        n1 += c * (c + 1) // 2
        c = 0      # 重置计数器
# 处理数组末尾可能的连续0
n1 += c * (c + 1) // 2

# 计算最终答案：n(n+1) - 2*N0 - N1
ans = n * (n + 1) - 2 * n0 - n1
print(ans)

• Cpp

#include <iostream>
using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // 读取输入
    int n;
    cin >> n;
    int* arr = new int[n];
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    // 计算全为1的子数组数量 n0
    ll n0 = 0;
    ll cnt = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] == 1) {  // 如果当前元素是1
            cnt++;          // 连续1的计数器加1
        } else {
            // 计算当前连续1段的子数组数量并累加
            n0 += cnt * (cnt + 1) / 2;
            cnt = 0;        // 重置计数器
        }
    }
    // 处理数组末尾可能的连续1
    n0 += cnt * (cnt + 1) / 2;
    
    // 计算全为0的子数组数量 n1
    ll n1 = 0;
    cnt = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] == 0) {  // 如果当前元素是0
            cnt++;          // 连续0的计数器加1
        } else {
            // 计算当前连续0段的子数组数量并累加
            n1 += cnt * (cnt + 1) / 2;
            cnt = 0;        // 重置计数器
        }
    }
    // 处理数组末尾可能的连续0
    n1 += cnt * (cnt + 1) / 2;
    
    // 计算最终答案：n(n+1) - 2*n0 - n1
    ll ans = (ll)n * (n + 1) - 2 * n0 - n1;
    cout << ans << "\n";
    
    delete[] arr;
    return 0;
}

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 读取输入
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        
        // 计算全为1的子数组数量 n0
        long n0 = 0;
        long cnt = 0;
        for (int i = 0; i < n; i++) {
            if (arr[i] == 1) {  // 如果当前元素是1
                cnt++;          // 连续1的计数器加1
            } else {
                // 计算当前连续1段的子数组数量并累加
                n0 += cnt * (cnt + 1) / 2;
                cnt = 0;        // 重置计数器
            }
        }
        // 处理数组末尾可能的连续1
        n0 += cnt * (cnt + 1) / 2;
        
        // 计算全为0的子数组数量 n1
        long n1 = 0;
        cnt = 0;
        for (int i = 0; i < n; i++) {
            if (arr[i] == 0) {  // 如果当前元素是0
                cnt++;          // 连续0的计数器加1
            } else {
                // 计算当前连续0段的子数组数量并累加
                n1 += cnt * (cnt + 1) / 2;
                cnt = 0;        // 重置计数器
            }
        }
        // 处理数组末尾可能的连续0
        n1 += cnt * (cnt + 1) / 2;
        
        // 计算最终答案：n(n+1) - 2*n0 - n1
        long ans = (long) n * (n + 1) - 2 * n0 - n1;
        System.out.println(ans);
        
        sc.close();
    }
}

02. 信用评分特征选择

问题描述

小柯是一家金融科技公司的数据科学家，她正在开发一个信用评分系统，用于评估客户的信用风险。目前，她已经收集了一系列客户的特征数据，并且标记了这些客户的信用状况（"Good"表示信用良好，"Bad"表示信用不佳）。

为了提高模型的准确性和解释性，小柯需要从众多特征中选择最具有预测能力的特征。她决定使用决策树算法来评估每个特征的重要性，并选择最重要的特征用于后续的模型构建。

请你帮助小柯编写一个程序，从给定的数据集中找出对信用评分最重要的特征。

输入格式

输入数据为一个二维列表，其中每一行代表一个客户的记录，每一列代表一个特征。其中最后一列是目标变量，值为 "Good" 表示信用良好，"Bad" 表示信用不佳。倒数第二列也是字符串特征，其余特征值可以是整数或浮点数。

输出格式

输出一个整数，表示最重要的特征的索引（从 开始计数）。

样例输入

[[50000,1,'Yes','Good'],[5000,2,'No','Bad'],[70000,''3','Yes','Good'],[40000,4,'No','Bad']]

样例输出

2

数据范围

• 输入数据的行数（客户数量）：
• 输入数据的列数（特征数量 + 1）：
• 字符串特征的长度：

题解

这道题目要求我们从给定的数据集中找出对信用评分最重要的特征。这是一个典型的特征选择问题，在机器学习中非常常见。

首先，让我们理解一下什么是"最重要的特征"。在决策树算法中，特征的重要性通常通过信息增益（Information Gain）或基尼不纯度（Gini Impurity）来衡量。一个特征的重要性越高，意味着它能够更好地将数据分成不同的类别。

在这个问题中，我们需要：

1. 解析输入的二维列表数据
2. 将数据转换为适合决策树算法处理的格式
3. 使用决策树算法评估每个特征的重要性
4. 返回最重要特征的索引

对于决策树算法，我们可以使用Python的scikit-learn库中的DecisionTreeClassifier。这个分类器会自动计算每个特征的重要性，我们只需要找出重要性最高的特征即可。

需要注意的是，输入数据中包含了不同类型的特征（数值型和字符串型），我们需要对字符串特征进行编码，将其转换为数值型特征，才能用于决策树算法。

时间复杂度分析：

• 数据预处理的时间复杂度为O(n*m)，其中n是样本数量，m是特征数量
• 决策树训练的时间复杂度为O(nmlog(n))
• 总体时间复杂度为O(nmlog(n))

空间复杂度分析：

• 存储原始数据需要O(n*m)的空间
• 存储转换后的数据也需要O(n*m)的空间
• 决策树模型需要O(n)的空间
• 总体空间复杂度为O(n*m)

这个解法的优点是简单直观，能够有效地评估特征的重要性。缺点是对于大规模数据集可能会比较慢，而且决策树算法可能会受到过拟合的影响。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()
import ast
from sklearn.tree import DecisionTreeClassifier
from sklearn.preprocessing import LabelEncoder
import numpy as np

def find_most_important_feature(data):
    # 提取特征和目标变量
    X = [row[:-1] for row in data]  # 所有特征
    y = [row[-1] for row in data]   # 目标变量
    
    # 对特征进行预处理
    X_processed = []
    encoders = []
    
    # 对每一列特征进行处理
    for j in range(len(X[0])):
        col = [row[j] for row in X]
        # 检查是否为字符串类型
        if any(isinstance(val, str) for val in col):
            # 对字符串特征进行编码
            le = LabelEncoder()
            col_encoded = le.fit_transform([str(val) for val in col])
            X_processed.append(col_encoded)
            encoders.append(le)
        else:
            # 数值型特征直接使用
            X_processed.append([float(val) if val != '' else 0.0 for val in col])
    
    # 转置特征矩阵，使其符合scikit-learn的输入格式
    X_processed = np.array(X_processed).T
    
    # 对目标变量进行编码
    le_y = LabelEncoder()
    y_encoded = le_y.fit_transform(y)
    
    # 训练决策树模型
    clf = DecisionTreeClassifier(random_state=42)
    clf.fit(X_processed, y_encoded)
    
    # 获取特征重要性
    importances = clf.feature_importances_
    
    # 返回最重要特征的索引
    return np.argmax(importances)

# 主函数
def main():
    # 读取输入数据
    data_str = input()
    # 解析输入的二维列表
    data = ast.literal_eval(data_str)
    
    # 找出最重要的特征
    result = find_most_important_feature(data)
    
    # 输出结果
    print(result)

if __name__ == "__main__":
    main()

• Cpp

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

// 定义数据类型
typedef vector<vector<string>> Dataset;

// 计算基尼不纯度
double calc_gini(const vector<string>& labels) {
    map<string, int> cnt;
    for (const auto& label : labels) {
        cnt[label]++;
    }
    
    double gini = 1.0;
    for (const auto& pair : cnt) {
        double p = static_cast<double>(pair.second) / labels.size();
        gini -= p * p;
    }
    
    return gini;
}

// 计算特征的基尼增益
double calc_gain(const vector<string>& feat, const vector<string>& labels) {
    map<string, vector<int>> split;
    
    // 按特征值分组
    for (int i = 0; i < feat.size(); i++) {
        split[feat[i]].push_back(i);
    }
    
    // 计算加权基尼不纯度
    double w_gini = 0.0;
    for (const auto& pair : split) {
        vector<string> sub_labels;
        for (int idx : pair.second) {
            sub_labels.push_back(labels[idx]);
        }
        double weight = static_cast<double>(sub_labels.size()) / labels.size();
        w_gini += weight * calc_gini(sub_labels);
    }
    
    // 计算基尼增益
    double gain = calc_gini(labels) - w_gini;
    return gain;
}

// 解析输入数据
Dataset parse_input(const string& input) {
    Dataset data;
    string s = input;
    
    // 移除所有空格
    s.erase(remove(s.begin(), s.end(), ' '), s.end());
    
    // 移除外层括号
    s = s.substr(2, s.length() - 4);
    
    // 分割每条记录
    vector<string> records;
    int start = 0;
    int bracket_count = 0;