3.21晚 贝壳笔试编程题统计
第一次AK，果然还是小厂比较轻松
第一题
动态规划，`dp[i]`表示`[0,i]`能得到的最大分数
package beike.q1;
// 本题为考试单行多行输入输出规范示例，无需提交，不计分。
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextInt()) {// 注意，如果输入是多个测试用例，请通过while循环处理多个测试用例
/*
dp[i] 表示0..i能够得到的最大分数
dp[i] = dp[j] + score(j..i) for j in 0..i
*/
int n = in.nextInt();
String s = in.next();
int[] dp = new int[s.length()];
Arrays.fill(dp, Integer.MIN_VALUE);
dp[0] = -1;
for (int i = 1 ; i < s.length() ; i++) {
int score = dp[i-1] - 1;
int[] freq = new int[26];
for (int j = i ; j >= 0 ; j--) {
freq[s.charAt(j)-'a']++;
int sc = cal(freq);
if (j > 0) {
score = Math.max(sc+dp[j-1], score);
} else {
score = Math.max(sc, score);
}
}
dp[i] = score;
}
System.out.println(dp[s.length()-1]);
}
}
private static int cal(int[] freq) {
int score = 0;
for (int i : freq) {
if (i != 0) {
if (i % 2 == 1) {
score --;
} else {
score ++;
}
}
}
return score;
}
} 第二题
直接算，缓存一下提高效率，你要想写还可以用前缀和，我直接循环竟然过了
package beike.q2;
// 本题为考试单行多行输入输出规范示例，无需提交，不计分。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int[] cache = new int[1000003];
for (int i = 1 ; i < cache.length ; i++) {
if (match(i)) {
cache[i] = 1;
} else {
cache[i] = 2;
}
}
while (in.hasNextInt()) {// 注意，如果输入是多个测试用例，请通过while循环处理多个测试用例
int t = in.nextInt();
while (t-- > 0) {
int l = in.nextInt();
int r = in.nextInt();
int cnt = 0;
for (int i = l ; i <= r ; i++) {
if (cache[i] == 1) cnt++;
}
System.out.println(cnt);
}
}
}
private static boolean match(int s) {
int t = s;
int ss = 0;
while (t > 0) {
ss += t % 10;
t /= 10;
}
if (s % ss == 1) {
return true;
}
return false;
}
} 第三题
矩阵里面逐个匹配即可
package beike.q3;
// 本题为考试单行多行输入输出规范示例，无需提交，不计分。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextInt()) {// 注意，如果输入是多个测试用例，请通过while循环处理多个测试用例
int n = in.nextInt();
String s = in.next();
int[][] matrix = new int[n][n];
for (int i = 0 ; i < n ; i++) {
String line = in.next();
for (int j = 0 ; j < n ; j++) {
matrix[i][j] = line.charAt(j);
}
}
System.out.println(match(matrix, n, s));
}
}
private static int match(int[][] matrix, int n, String s) {
int cnt = 0;
for (int r = 0 ; r < n ; r++) {
for (int c = 0 ; c < n ; c++) {
if (matrix[r][c] == s.charAt(0)) {
// 开始四个方向匹配
// up
if (r-s.length()+1 >= 0) {
boolean m = true;
for (int j = 0 ; j < s.length() ; j++) {
if (matrix[r-j][c] != s.charAt(j)) {
m = false;
break;
}
}
if (m) cnt++;
}
if (s.length() == 1) continue;
// down
if (r+s.length()-1 < n) {
boolean m = true;
for (int j = 0 ; j < s.length() ; j++) {
if (matrix[r+j][c] != s.charAt(j)) {
m = false;
break;
}
}
if (m) cnt++;
}
// right
if (c+s.length()-1 < n) {
boolean m = true;
for (int j = 0 ; j < s.length() ; j++) {
if (matrix[r][c+j] != s.charAt(j)) {
m = false;
break;
}
}
if (m) cnt++;
}
// left
if (c-s.length()+1 > 0) {
boolean m = true;
for (int j = 0 ; j < s.length() ; j++) {
if (matrix[r][c-j] != s.charAt(j)) {
m = false;
break;
}
}
if (m) cnt++;
}
}
}
}
return cnt;
}
} 
