科大讯飞
考试平台： 牛客网
考试题型： 选择题（50 分） + 编程题（50分）
T1
小红定义一个正整数x为完美偶数满足以下两个条件:
- x是偶数
- x不小于l，不大于r
小红拿到了一个长度为n的数组a。她想知道这个数组内有多少个完美偶数?
输入描述
第一行输入三个正整数n，l, r 用空格隔开。
第二行输入n个正整数ai，代表小红拿到的数组。
1 ≤ n, ≤ 100
1 ≤ l ≤ r ≤ 100
输出描述
该数组中完美偶数的数量。
示例
输入
5 3 8
1 2 6 8 7
输出
2
说明
只有6和8两个完美偶数。
题解
简单签到题
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(), l = scanner.nextInt(), r = scanner.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = scanner.nextInt();
int cnt = 0;
for (int x : a) {
if (x % 2 == 0 && x >= l && x <= r) cnt++;
}
System.out.println(cnt);
}
}
T2 科大讯飞智能语音模型训练
小红是科大讯飞智能语音项目的员工，她正在训练智能语音的AI模型。
所谓智能语音，即智能语音技术，是实现人机语言的通信，包括语音识别技术(ASR)和语音合成技术(TTS)。
在语音识别技术中，需要将人类的语音中的词汇内容转换为计算机可读的输入，因此对于音节的相似度的匹配处理是非常重要的。
小红正在研究基于模式匹配法的语音识别技术。现在给定了一个AI转化的字符串，以及一个模式匹配串，
请你帮小红求出两个字符串的相似度。
我们将相似度定义如下:
- 两个字符串长度相同，则相似度加1。
- 两个字符串使用了同样的字符集，则相似度加1。(我们认为，字符集分为:数字字符、英文字符和其他字符三种)。
输入描述
第一行输入一个正整数t，代表询问次数。
对于每次询问，输入两行字符串。
第一行字符串为Al转化的字符串，第二个字符串为模式匹配串。1 ≤t≤10
字符串的长度均不超过100。
输出描述
输出t行，每行输出一个整数，代表相似度。
示例
输入
3
abcd
1234
abc.
S?AD
aha
a ha
输出
1
2
0
题解
中等，先预处理每个字符串的字符特征，再根据字符特征算计相似度。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int t = Integer.parseInt(scanner.nextLine());
while (t-- > 0) {
String a = scanner.nextLine(), b = scanner.nextLine();
System.out.println(compare(a, b));
}
}
public static int compare(String str1, String str2) {
int ans = (str1.length() == str2.length()) ? 1 : 0;
boolean[] b1 = type(str1), b2 = type(str2);
boolean same = true;
for (int i = 0; i < 3; i++) {
if (b1[i] != b2[i]) {
same = false;
break;
}
}
return same ? ans + 1 : ans;
}
// 返回字符串 a 的字符串特征
public static boolean[] type(String a) {
boolean[] b = new boolean[3];
for (char c : a.toCharArray()) {
if (Character.isDigit(c)) {
b[0] = true;
} else if (Character.isLetter(c)) {
b[1] = true;
} else {
b[2] = true;
}
}
return b;
}
}T3 小红的问号替换
小红拿到了一个字符串，其中有一些字符变成了 ‘?’。小红希望你将所有的 ‘?’ 替换成任意一个数字字符，使得最终字符串代表的十进制整数是p的倍数。请你告诉小红最终有多少种方案。注:可以包含前导零。
由于答案过大，请对10^9+7取模。
输入描述
第一行输入一个仅由数字和 ? 组成的字符串。
第二行输入一个正整数 p。
字符串长度不超过100。
1 ≤ p ≤ 10^4
输出描述
一个整数，代表方案数对10^9^+7取模的值。
示例1
输入
??
1
输出
100
说明
修改为00~99均可。
示例2
输入
????1
12
输出
0
说明
显然无论怎么修改都是奇数，不可能是 12 的倍数。
题解
1、难点一：怎么定义 dp 规则转移；
2、难点二：超大数字取余，这里会用到 BigInteger，对这块不熟的需要后续加强。
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
Solution solution = new Solution();
System.out.println(solution.solve(scanner.next(), scanner.nextInt()));
}
}
class Solution {
private int MOD = (int) 1e9 + 7;
private int P;
public int solve(String s, int p) {
this.P = p;
int n = s.length();
// dp[i][j] 表示前 i 为取模 p 等于 j 的方案数
int[][] dp = new int[n][p];
dfs(new StringBuilder(s).reverse().toString().toCharArray(), 0, dp);
return dp[n - 1][0];
}
public void dfs(char[] s, int idx, int[][] dp) {
if (idx == s.length) return;
char c = s[idx];
int up = (c == '?') ? 9 : c - '0';
for (int d = (c == '?' ? 0 : c - '0'); d <= up; d++) {
BigInteger t = new BigInteger(pow(d, idx));
int r = t.mod(BigInteger.valueOf(P)).intValue(); // 与P取模后的余数
if (idx == 0) {
dp[idx][r]++;
} else {
for (int x = 0; x < P; x++) {
int nr = (r + x) % P;
dp[idx][nr] = (dp[idx][nr] + dp[idx - 1][x]) % MOD;
}
}
}
dfs(s, idx + 1, dp);
}
public String pow(int d, int bits) {
StringBuilder num = new StringBuilder();
num.append(d);
for (int b = 0; b < bits; b++) num.append(0);
return num.toString();
}
}🙏如果有帮助到您，请给点个赞 ❤️ 和收藏 ⭐，让更多的人看到。
