金山笔试金山wps 金山秋招 0927

笔试时间：2025年9月27日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：dd爱科学

大科学家dd最近在研究转基因白菜，白菜的基因序列由一串大写英文字母构成。dd经过严谨的推理证明发现，只有当白菜的基因序列呈按位非递减形式时，这株白菜的高附加值将达到最高。于是dd开始着手修改白菜的基因序列，dd每次修改基因序列的任意位需要的代价是1，dd想知道，修改白菜的基因序列使其高附加值达到最高，所需要的最小代价是多少。

输入描述

第一行一个正整数n(1 ≤ n ≤ 1000000)，表示字符串长度。第二行一个长度为n的字符串，表示所给白菜的基因序列，保证给出字符串中仅有大写英文字母。

输出描述

输出一行，表示最小代价。

样例输入

5

ACEBF

样例输出

1

样例说明

改成ACEEF或者ACEFF，都只用改动一个字符，所需代价最小为1。

参考题解

解题思路：

问题转换：要让修改次数最少，就要让保留的字符最多。可以保留的字符必须构成一个"非递减子序列"。因此，问题转化为求最长非递减子序列的长度。
使用贪心+二分优化解法：维护一个辅助数组tails，遍历每个字符，如果能接在末尾就直接追加，否则用二分查找替换。
最终答案：字符串总长度 - 最长非递减子序列的长度 = 最小修改次数。

C++：

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

int main() {
    int n;
    string s;
    cin >> n >> s;
    
    if (n == 0) {
        cout << 0 << endl;
        return 0;
    }
    
    vector<char> tails;
    
    for (char c : s) {
        int left = 0, right = tails.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (tails[mid] > c) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        if (left == tails.size()) {
            tails.push_back(c);
        } else {
            tails[left] = c;
        }
    }
    
    cout << n - tails.size() << endl;
    return 0;
}

Java：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner inputReader = new Scanner(System.in);
        int sequenceLength = inputReader.nextInt();
        String dnaString = inputReader.next();
        
        if (sequenceLength == 0) {
            System.out.println(0);
            inputReader.close();
            return;
        }
        
        char[] trackingArray = new char[sequenceLength];
        int currentLength = 0;
        
        for (char character : dnaString.toCharArray()) {
            int left = 0;
            int right = currentLength;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (trackingArray[mid] > character) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            
            trackingArray[left] = character;
            if (left == currentLength) {
                currentLength++;
            }
        }
        
        System.out.println(sequenceLength - currentLength);
        inputReader.close();
    }
}

Python：

n = int(input())
s = input()

if n == 0:
    print(0)
else:
    tails = []
    
    for c in s:
        left, right = 0, len(tails)
        while left < right:
            mid = left + (right - left) // 2
            if tails[mid] > c:
                right = mid
            else:
                left = mid + 1
        
        if left == len(tails):
            tails.append(c)
        else:
            tails[left] = c
    
    print(n - len(tails))

第二题：实现二分类的F-Score

实现一个函数来计算二分类问题中的F-Score。F-Score是精确率（Precision）和召回率（Recall）的加权调和平均，用于评估分类模型的性能。

输入描述

第一行输入一个数组，表示真实标签。第二行输入一个数组，表示预测标签。第三行输入一个浮点数，表示β参数。

输出描述

返回一个浮点数，表示计算得到的F-Score；结果保留3位小数。

样例输入

[1,1,0,0]

[1,0,0,1]

1.0

样例输出

0.500

参考题解

解题思路：

读取输入并解析数组字符串
统计TP（真正例）、FP（假正例）、FN（假反例）
计算精确率 Precision = TP/(TP+FP) 和召回率 Recall = TP/(TP+FN)
应用F-Score公式：F-Score = (1+β²)×(Precision×Recall)/(β²×Precision+Recall)

Python：

import re

# 读取输入
true_labels_str = input()
pred_labels_str = input()
beta = float(input())

# 解析数组字符串
def parse_array(s):
    s = re.sub(r'[\[\] ]', '', s)
    if not s:
        return []
    return [int(x) for x in s.split(',')]

y_true = parse_array(true_labels_str)
y_pred = parse_array(pred_labels_str)

# 计算TP、FP、FN
tp = fp = fn = 0

for i in range(len(y_true)):
    if y_true[i] == 1 and y_pred[i] == 1:
        tp += 1
    elif y_true[i] == 0 and y_pred[i] == 1:
        fp += 1
    elif y_true[i] == 1 and y_pred[i] == 0:
        fn += 1

# 计算precision和recall
precision = tp / (tp + fp) if (tp + fp) > 0 else 0.0
recall = tp / (tp + fn) if (tp + fn) > 0 else 0.0

# 计算F-Score
f_score = 0.0
beta_squared = beta * beta
denominator = (beta_squared * precision) + recall
if denominator > 0:
    f_score = (1 + beta_squared) * (precision * recall) / denominator

print(f"{f_score:.3f}")