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;
    }
}

#贝壳笔试##贝壳找房#