华为笔试 华为秋招 0917
笔试时间：2025年9月17日
往年笔试合集：
第一题：最大化安全评分
安全分析师小王正在开发一款先进的入侵检测系统（IDS），需要在网络环境中从起始节点出发，到达终端节点（即最后一个监控点），同时最大化累积的安全评分。
整个网络被抽象为一个下标从0开始的整数数组，其中每个元素代表对应位置的安全评分。正值表示该位置是安全的或有正面的安全措施，而负值则表示存在潜在风险或威胁。分析师开始于位置0（入口节点），每一步可以前进最多k步，但不能超出数组边界。也就是说，如果当前位于下标i，则可以选择跳到[i+1, min(i+k, n-1)]包含两个端点的任意位置。目标是到达数组的最后一个位置（下标为n-1），并且在此过程中最大化累积的安全评分得分。
输入描述
每组数据第一行为最大前进步数k，第二行为节点数量n，第三行的n个数为每个节点的安全得分。
输入范围限制：
- 1 ≤ k ≤ 10^5
- 1 ≤ n ≤ 10^5
- -10^4 ≤ scores[i] ≤ 10^4
输出描述
到达最后一个节点时可以获得的最大安全得分。
样例输入
2
8
3 -5 -10 2 -1 5 -6 -5
样例输出
0
说明：最多可前进步数k=2，安全分数组长度n=8，数组scores的具体值为[3,-5,-10,2,-1,5,-6,-5]。可使安全评分最大的子序列[3,2,-1,-5]，因此最大安全得分为3+2-1-5=0。
参考题解
这是一个带步数限制的最大路径和问题，使用动态规划结合单调队列优化：
- 状态定义：dp[i]表示到达位置i时的最大得分
- 状态转移：dp[i] = scores[i] + max{dp[j]}，其中j∈[max(0, i-k), i-1]
- 使用单调递减队列维护滑动窗口内的最大值，将时间复杂度从O(nk)降为O(n)
C++：
#include <iostream>
#include <vector>
#include <deque>
#include <limits>
using namespace std;
int main() {
int k, n;
cin >> k >> n;
vector<int> scores(n);
for (int i = 0; i < n; i++) {
cin >> scores[i];
}
if (n == 1) {
cout << scores[0] << endl;
return 0;
}
const long long NEG_INF = -1e18;
vector<long long> dp(n, NEG_INF);
dp[0] = scores[0];
deque<int> dq;
dq.push_back(0);
for (int i = 1; i < n; i++) {
// 保证队首在范围内
while (!dq.empty() && dq.front() < i - k) {
dq.pop_front();
}
if (!dq.empty()) {
dp[i] = scores[i] + dp[dq.front()];
}
// 单调队列维护最大值
while (!dq.empty() && dp[dq.back()] <= dp[i]) {
dq.pop_back();
}
dq.push_back(i);
}
cout << dp[n - 1] << endl;
return 0;
}
Java：
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int k = sc.nextInt();
int n = sc.nextInt();
int[] scores = new int[n];
for (int i = 0; i < n; i++) {
scores[i] = sc.nextInt();
}
if (n == 1) {
System.out.println(scores[0]);
return;
}
long NEG_INF = (long) -1e18;
long[] dp = new long[n];
Arrays.fill(dp, NEG_INF);
dp[0] = scores[0];
Deque<Integer> dq = new ArrayDeque<>();
dq.addLast(0);
for (int i = 1; i < n; i++) {
// 保证队首在范围内
while (!dq.isEmpty() && dq.peekFirst() < i - k) {
dq.pollFirst();
}
if (!dq.isEmpty()) {
dp[i] = scores[i] + dp[dq.peekFirst()];
}
// 单调队列维护最大值
while (!dq.isEmpty() && dp[dq.peekLast()] <= dp[i]) {
dq.pollLast();
}
dq.addLast(i);
}
System.out.println(dp[n - 1]);
}
}
Python：
from collections import deque
def main():
k = int(input().strip())
n = int(input().strip())
scores = list(map(int, input().split()))
if n == 1:
print(scores[0])
return
# 用一个非常小的数初始化
NEG_INF = -10 ** 18
dp = [NEG_INF] * n
dp[0] = scores[0]
dq = deque([0])
for i in range(1, n):
# 保证队首在范围内
while dq and dq[0] < i - k:
dq.popleft()
if dq:
dp[i] = scores[i] + dp[dq[0]]
# 单调队列维护最大值
while dq and dp[dq[-1]] <= dp[i]:
dq.pop()
dq.append(i)
print(dp[n - 1])
if __name__ == "__main__":
main()
第二题：虚拟货币挖矿算力匹配
一个虚拟货币挖矿系统中，每个矿工拥有一定的算力值（范围在1到10^18之间）。系统需要为每个矿工分配一个算力档位，这个档位必须是小于等于矿工当前算力的最大"稳定算力档"，并且这个档位的算力值各个数位之和必须是一个质数（质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数）。"稳定算力档"定义为从左到右每一位数字都不小于前一位数字，例如123、111、399都是符合要求的稳定算力档，像132、200这种则不符合要求。
输入描述
给定一个正整数n（1 ≤ n ≤ 10^18）。
输出描述
返回小于等于n的最大稳定算力档，且该整数的所有数位之和为质数。如果不存在这样的整数，则返回-1。
样例输入
123
样例输出
122
样例说明1：首先小于等于123的"稳定算力档"有111、112、113等。123的数位之和为1+2+3=6，不是质数，不符合条件。再继续找是122，数位之和为1+2+2=5是质数符合"稳定算力档"条件。111的数位之和1+1+1=3也为质数也满足"稳定算力档"的条件，但111小于122，所以小于等于123的最大稳定算力档为122，函数返回122。
参考题解
解题思路：
- 预处理质数表（0-162范围内）
- 使用DFS从高位到低位构造数字，保持非递减性质
- 如果当前位数找不到解，尝试位数减一的最大稳定算力档
- 对于k位数，从最大可能数字和开始向下寻找质数，构造对应的稳定算力档
C++：
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
vector<bool> p(163, false);
string s;
int L;
long long R = -1;
vector<int> d;
void F(int m) {
p = vector<bool>(m + 1, true);
p[0] = p[1] = false;
for (int i = 2; i <= sqrt(m); i++) {
if (p[i]) {
for (int j = i * i; j <= m; j += i) {
p[j] = false;
}
}
}
}
void dfs(int i, int prev, int total, bool lt) {
if (R != -1) return;
if (i == L) {
if (p[total]) {
long long t = 0;
for (int j = 0; j < L; j++) {
t = t * 10 + d[j];
}
R = t;
}
return;
}
int ub = lt ? 9 : (s[i] - '0');
for (int x = ub; x >= prev; x--) {
d[i] = x;
dfs(i + 1, x, total + x, lt || (x < ub));
if (R != -1) return;
}
}
string build(int k, int ts, int md) {
if (k == 0) {
return ts == 0 ? "" : "fail";
}
for (int x = min(9, ts); x >= md; x--) {
int ns = ts - x;
int nk = k - 1;
if (ns >= 0 && nk * x <= ns && ns <= nk * 9) {
string r = build(nk, ns, x);
if (r != "fail") {
return to_string(x) + r;
}
}
}
return "fail";
}
int main() {
F(162);
long long n;
cin >> n;
s = to_string(n);
L = s.length();
d.resize(L);
dfs(0, 0, 0, false);
if (R != -1) {
cout << R << endl;
return 0;
}
if (L > 1) {
int k = L - 1;
int ms = 9 * k;
for (int i = ms; i > 1; i--) {
if (p[i]) {
string r = build(k, i, 1);
if (r != "fail") {
cout << r << endl;
return 0;
}
}
}
}
cout << -1 << endl;
return 0;
}
Java：
import java.util.*;
public class Main {
static boolean[] p = new boolean[163];
static String s;
static int L;
static long R = -1;
static int[] d;
static void F(int m) {
p = new boolean[m + 1];
Arrays.fill(p, true);
p[0] = p[1] = false;
for (int i = 2; i * i <= m; i++) {
if (p[i]) {
for (int j = i * i; j <= m; j += i) {
p[j] = false;
}
}
}
}
static void dfs(int i, int prev, int total, boolean lt) {
if (R != -1) return;
if (i == L) {
if (p[total]) {
long t = 0;
for (int j = 0; j < L; j++) {
t = t * 10 + d[j];
}
R = t;
}
return;
}
int ub = lt ? 9 : (s.charAt(i) - '0');
for (int x = ub; x >= prev; x--) {
d[i] = x;
dfs(i + 1, x, total + x, lt || (x < ub));
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
2025 春招笔试合集 文章被收录于专栏
2025打怪升级记录，大厂笔试合集 C++, Java, Python等多种语言做法集合指南
海康威视公司福利 1377人发布
