金山笔试 金山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。

参考题解

解题思路:

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

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

参考题解

解题思路:

  1. 读取输入并解析数组字符串
  2. 统计TP(真正例)、FP(假正例)、FN(假反例)
  3. 计算精确率 Precision = TP/(TP+FP) 和召回率 Recall = TP/(TP+FN)
  4. 应用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}")

第三题:神秘串

给定一个仅由小写英文字母组成的字

剩余60%内容,订阅专栏后可继续查看/也可单篇购买

2025 春招笔试合集 文章被收录于专栏

2025打怪升级记录,大厂笔试合集 C++, Java, Python等多种语言做法集合指南

全部评论
进面试了吗
点赞 回复 分享
发布于 10-09 20:31 湖北

相关推荐

评论
点赞
4
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务