3.21 贝壳服务端笔试
A了2 3 第一题没看出来是动态规划 结束后做出来了
第一题 对于dp[j] 意为0~j这一段字串最大的得分，通过最大的dp[i]+score(i+1,j)获得，其中i=0~j-1，score(i+1,j)为i+1~j这段字串的得分
import java.util.ArrayList;
import java.util.Scanner;
public class Beike_01 {
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int n=in.nextInt();
in.nextLine();
String s=in.nextLine();
System.out.println(maxScore(s));
}
public static int maxScore(String s){
int[] dp=new int[s.length()];
dp[0]=-1;
for(int i=1;i<s.length();i++){
dp[i]=score(s.substring(0,i+1));
for(int j=0;j<i;j++){
dp[i]=Math.max(dp[i],dp[j]+score(s.substring(j+1,i+1)));
}
}
return dp[s.length()-1];
}
public static int score(String s){
int[] cnt=new int[26];
for(int i=0;i<s.length();i++){
int index=s.charAt(i)-'a';
cnt[index]++;
}
int score=0;
for(int i=0;i<26;i++){
if(cnt[i]==0) continue;
if(cnt[i]%2==0) score++;
else score--;
}
return score;
}
} 第二题 我用暴力会超时 所以维护了一个动态数组来记录各位和 注意输入是有界的 所以多写几个判断就好了 import java.util.Scanner;
public class Beike_02 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int t = in.nextInt();
for (int i = 0; i < t; i++) {
int l = in.nextInt();
int r = in.nextInt();
System.out.println(numOfModNum(l, r));
}
}
public static int numOfModNum(int l, int r) {
int[] bitI = new int[6];
int j = 0;
int tmp = l;
l--;
while (l > 0) {
for (int i = 0; i <= j; i++) bitI[i] += l % 10;
l /= 10;
j++;
}
l = tmp;
int ret = 0;
for (int i = l; i <= r; i++) {
if (i == 1000000) continue;
if (i % 100000 == 0) {
bitI[5]++;
for (int k = 0; k < 5; k++) bitI[k] = bitI[5];
} else if (i % 10000 == 0) {
bitI[4]++;
for (int k = 0; k < 4; k++) bitI[k] = bitI[4];
} else if (i % 1000 == 0) {
bitI[3]++;
for (int k = 0; k < 3; k++) bitI[k] = bitI[3];
} else if (i % 100 == 0) {
bitI[2]++;
for (int k = 0; k < 2; k++) bitI[k] = bitI[2];
} else if (i % 10 == 0) {
bitI[1]++;
for (int k = 0; k < 1; k++) bitI[k] = bitI[1];
} else bitI[0]++;
if (i % bitI[0] == 1) ret++;
}
return ret;
}
} 第三题 BFS 和普通的BFS的区别在于只有两个方向而且需要区别以下，但是不用标记是否访问过了 import java.util.Arrays;
import java.util.Scanner;
public class Beike_03 {
static int stringSum = 0;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
in.nextLine();
String s = in.nextLine();
String[] ans = new String[n];
for (int i = 0; i < n; i++) ans[i] = in.nextLine();
char[][] board = new char[n][n];
for (int i = 0; i < n; i++) {
board[i] = ans[i].toCharArray();
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dfs(n, i, j, 0, s, board, true);
dfs(n, i, j, 0, s, board, false);
}
}
System.out.println(stringSum);
}
public static void dfs(int n, int i, int j, int index, String s, char[][] board, boolean direct) {
if (index == s.length()) {
stringSum++;
return;
}
if (i < 0 || i >= n || j < 0 || j >= n) return;
char c = s.charAt(index);
if (board[i][j] != c) return;
if (direct) dfs(n, i, j + 1, index + 1, s, board, direct);
else dfs(n, i + 1, j, index + 1, s, board, direct);
}
}
