金山笔试 金山wps 金山秋招 0927
笔试时间:2025年9月27日
往年笔试合集:
第一题: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}")
第三题:神秘串
给定一个仅由小写英文字母组成的字
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
2025打怪升级记录,大厂笔试合集 C++, Java, Python等多种语言做法集合指南