笔试笔试2024vivo春季笔试真题
玦尘本文为原创内容，转载请注明出处并附带原文链接。感谢您的尊重与支持！
1.计算出非回文子串长度
题目描述
给定一个字符串s，将字符串清理后，求字符串的非回文子串长度。
清理操作是指只保留数字字符和英文字母。
回文串的定义为，忽略英文字母的大小写，正着读和反着读都一样的字符串。
输入描述
待测试的字符串s，仅包含大小写字母，数字，以及”!@#$%&*?”。
1 ≤ s.length ≤ 100
输出描述
输出一个数组a，数组的长度为原始字符串的长度。
数组中下标为i的元素表示，是否存在长度为i+1的子串是非回文的。如果存在，则这个元素为i+1，即a[i]=i+1，否则为-1，即a[i]=-1。
输入示例
$dda*ADD%
输出示例
[-1,2,3,4,5,-1,-1,-1,-1]
提示信息
说明
字符串的长度为9，所以输出的数组的长度也为9.
由于字符串中包含特殊的字符，经过清理后，字符串变为（ddaADD），长度为6，所以不存在长度为9,8,7的非回文子串。这些位置都用-1替代。
长度为6的非回文子串也不存在。
长度为5的非回文子串存在（ddaAD），所以数组第五个数字是5。
长度为4的非回文子串存在（daDD），所以数组的第4个数字是4。
长度为3的非回文子串存在（ADD），所以数组的第3个数字是3。
长度为2的非回文子串存在（da），所以数组的第2个数字是2。
长度为1的非回文子串不存在，所以数组的第1个数字是-1。
综上，输出的数组为[-1,2,3,4,5,-1,-1,-1,-1]，注意需要输出括号。
时间限制：c/c++/go：1s；其他语言：3s。
参考答案：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String x = sc.nextLine();
int length = x.length();
int[] res = new int[length];
Arrays.fill(res, -1);
StringBuilder sb = new StringBuilder();
for(char ch : x.toCharArray()){
if(Character.isLetter(ch) || Character.isDigit(ch)){
sb.append(ch);
}
}
String cur = sb.toString().toLowerCase();
int newLength = cur.length();
for(int i = 1;i <= newLength;i++){
boolean isPalindrome = true;
for(int j = 0;j <= newLength - i;j++){
if(!palindrome(cur.substring(j,j+i))){
isPalindrome = false;
break;
}
}
if(!isPalindrome) res[i - 1] = i;
}
System.out.print("[");
for (int i = 0; i < length; i++) {
if (i > 0) System.out.print(",");
System.out.print(res[i]);
}
System.out.println("]");
}
public static boolean palindrome(String cur){
int left = 0;
int right = cur.length() - 1;
while(left < right){
if(cur.charAt(left) == cur.charAt(right)){
left++;
right--;
}else {
return false;
}
}
return true;
}
}
|
2.排列字串搜索
题目描述
给定一个文本字符串text和模板字符串pat，请你求出所有的pat的排列在text串中出现的次数。
排列的定义：如果两个字符串排序过后完全相等，那么就认为这个字符串就是另一个字符串的排列。即两个字符串出现的字符的种类和数量完全相等。
输入描述
输入共2行，第一行是pat，第二行是text。字符串仅包含小写字母。
1 <= pat.length, text.length <= 10000.
输出描述
输出一个整数，表示出现的次数。
输入示例
abcd
bacdgabcda
输出示例
3
提示信息
pat的排列 → “bacd”，位于text的位置为 0；pat的排列 → “abcd”，位于text的位置为 5；pat的排列 → “bcda”，位于 text的位置为6.
一共出现了3次。
时间限制：c/c++/go：1s；其他语言：3s。
参考答案：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String text = sc.nextLine();
String pat = sc.nextLine();
Map<Character, Integer> need = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
for (char ch : pat.toCharArray()) {
need.put(ch, need.getOrDefault(ch, 0) + 1);
}
int left = 0, right = 0, valid = 0, res = 0;
while (right < text.length()) {
char a = text.charAt(right);
right++;
if (need.containsKey(a)) {
window.put(a, window.getOrDefault(a, 0) + 1);
if (window.get(a).equals(need.get(a))) {
valid++;
}
}
while (right - left == pat.length()) {
if (valid == need.size()) {
res++;
}
char b = text.charAt(left);
left++;
if (need.containsKey(b)) {
if (window.get(b).equals(need.get(b))) {
valid--;
}
window.put(b, window.get(b) - 1);
}
}
}
System.out.println(res);
}
}
|
3.计算最高运行效率
题目描述
计算摄影时代，AI等智能算法在手机影像中扮演着十分重要的角色，通过在相机拍摄过程中实时检测用户主体、场景，自适应调整优化策略等，实现哇塞的拍照效果。而智能手机作为消费级产品，对各个场景下功耗等有严格要求，这对算力要求高、功耗开销高的AI算法并不友好。因此，异构计算为算法能在手机端运行提供了有效的解决方案，使得算法可以跑在更合适运行的硬件环境上。
现有如下场景：
打开手机相机，进行拍照过程中，有N个算法需要执行，当前由于系统策略考虑，建议这些算法优先跑在NPU或者GPU上，且不同算法在这两个硬件上的运算速度均有不同，且NPU及GPU均有算力容量限制，如果GPU或NPU无法完成所有算法的执行，遗留的算法将仍由CPU完成，由CPU执行的算法，将不计算效率。
我们的目标是符合NPU及GPU的算力容量限制的情况下，合理安排这些算力在GPU/NPU上执行，使这些算法的运行效率最高。
输入描述
算法参数列表包括所有算法的参数，具体如下:
[算法1算力要求，算法1 NPU运行效率，算法1 GPU运行效率]，
[算法2算力要求，算法2 NPU运行效率，算法2 GPU运行效率]，
…
[算法N算力要求，算法N NPU运行效率，算法N GPU运行效率]。
输入共n+1行：
第一行输入三个整数k,m,n，k表示NPU算力容量，m表示GPU算力容量，n是算法数量。
接下来n行表示本次拍照需要实现的算法列表，具体含义见上面描述。
0 <= k, m <= 100.
1 <= n <= 100.
输出描述
输出一个整数，表示最高的效率。
输入示例
30 15 5
5 3 2
5 1 3
14 2 4
21 5 3
2 2 3
输出示例
14
提示信息
[5,3,2] [21,5,3] [2,2,3]执行在NPU，消耗NPU 5+21+2=28的算力，获得3+5+2=10的效率，[14,2,4]执行在GPU，消耗GPU 14的算力，获得4的效率，[5,1,3]因NPU\GPU算力限制，只能执行在CPU（不计效率），总效率 = 3+5+2+4=14。
时间限制：c/c++/go：1s；java：3s；其他语言：4s。
参考答案：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int maxNPU = sc.nextInt();
int maxGPU = sc.nextInt();
int numAlgorithms = sc.nextInt();
sc.nextLine();
int[][] algorithms = new int[numAlgorithms][3];
for (int i = 0; i < numAlgorithms; i++) {
algorithms[i][0] = sc.nextInt();
algorithms[i][1] = sc.nextInt();
algorithms[i][2] = sc.nextInt();
}
System.out.println(getMaxPerformance(maxNPU, maxGPU, numAlgorithms, algorithms));
}
public static int getMaxPerformance(int maxNPU, int maxGPU, int numAlgorithms, int[][] algorithms) {
int[][][] dp = new int[numAlgorithms + 1][maxNPU + 1][maxGPU + 1];
int maxPerformance = 0;
for (int i = numAlgorithms - 1; i >= 0; i--) {
int cost = algorithms[i][0];
int efficiencyNPU = algorithms[i][1];
int efficiencyGPU = algorithms[i][2];
for (int npuPower = 0; npuPower <= maxNPU; npuPower++) {
for (int gpuPower = 0; gpuPower <= maxGPU; gpuPower++) {
dp[i][npuPower][gpuPower] = dp[i + 1][npuPower][gpuPower];
if (npuPower >= cost) {
dp[i][npuPower][gpuPower] = Math.max(dp[i][npuPower][gpuPower],
dp[i + 1][npuPower - cost][gpuPower] + efficiencyNPU);
}
if (gpuPower >= cost) {
dp[i][npuPower][gpuPower] = Math.max(dp[i][npuPower][gpuPower],
dp[i + 1][npuPower][gpuPower - cost] + efficiencyGPU);
}
maxPerformance = Math.max(maxPerformance, dp[i][npuPower][gpuPower]);
}
}
}
return maxPerformance;
}
}
|
