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




#贝壳笔试##贝壳找房#
全部评论
求dl贴一份代码,让我学习学习🤣第一题(字符串分组)完全没有思路,第三题(查找字符串在矩阵中的次数)也不知道如何优化暴力
6 回复 分享
发布于 2022-03-21 20:19
我是垃圾  一个也没写出来  是不是凉了
4 回复 分享
发布于 2022-03-21 21:05
没有0的选项,我不是很认可😥 感觉会俩题,结果不知到细节哪错了
3 回复 分享
发布于 2022-03-21 21:04
暴力,竟然能过。。我一直在找规律,好吧,我真傻
2 回复 分享
发布于 2022-03-21 21:07
楼主第一题真妙啊,我用DFS超时只A了18
2 回复 分享
发布于 2022-03-21 21:04
我是废物😂
1 回复 分享
发布于 2022-03-21 20:52
第三题。。。测试案例都过了 结果是0%
1 回复 分享
发布于 2022-03-21 20:26
贝壳不至于小厂吧。。
点赞 回复 分享
发布于 2022-03-29 10:26
1.4 23号接到面试。。。
点赞 回复 分享
发布于 2022-03-25 13:00
7:11收到面试通知,笔试做了1.65道
点赞 回复 分享
发布于 2022-03-24 19:37
有没有做完笔试到现在没收到面试的 感觉好多人都收到了 现在没收到怕不是凉了
点赞 回复 分享
发布于 2022-03-24 11:43
一道没a的是不是无了😭
点赞 回复 分享
发布于 2022-03-23 16:30
没想到要用动态规划,我是sb🙃
点赞 回复 分享
发布于 2022-03-23 14:52
收到面试通知了吗楼主
点赞 回复 分享
发布于 2022-03-22 19:43
第一题昨晚睡觉突然想到,贴一份Java的,测试用例是过了,笔的时候没a出来,裂开     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         while (sc.hasNext()){             String str = sc.next();             int n = str.length();             int[] dp = new int[n+1];             Arrays.fill(dp,Integer.MIN_VALUE);             dp[0] = 0;             for (int i = 1; i <= n; i++) {                 for (int j = i; j > 0 ; j--) {                     dp[i] = Math.max(dp[i],dp[j-1] + sum(str,j-1,i-1));// 枚举每个分组情况                 }             }             System.out.println(dp[n]);         }     }     // 统计字符串从start 到 end的得分     private static int sum(String str,int start,int end){         int[] ch = new int[26];         for (int i = start; i <= end; i++) {             ch[str.charAt(i) - 'a&(417)#39;]++;         }         int val = 0;         for (int i : ch) {             if (i == 0) continue;             if ((i & 1) == 0) val++;             else val--;         }         return val;     }
点赞 回复 分享
发布于 2022-03-22 09:13
没有0-1的选项我不是很认可
点赞 回复 分享
发布于 2022-03-21 21:36
第一题我看数据量为3*10^3,O(n^2)不得到10^7了。。。回溯肯定也要超时。。。想了半天贪心也不行。。。最后卡了18.5%。。。 不过感觉第一题这个dp有点巧妙,顺向+逆向处理。
点赞 回复 分享
发布于 2022-03-21 21:29
第二题这个为什么ac 0啊 import java.util.Scanner; public class Main2 {     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int t = sc.nextInt();         boolean[] flag = new boolean[10000000 + 1];         for (int i = 0; i < t; i++) {             int l = sc.nextInt();             int r = sc.nextInt();             int sum = 0;             for (int j = l; j <= r; j++) {                 if( flag[i] || isZiYuShu(j, flag))                     sum++;             }             System.out.println(sum);         }     }     private static boolean isZiYuShu(int i, boolean[] flag)     {         int sum = 0;         int n = i;         while (n > 0)         {             sum += (n % 10);             n /= 10;         }         if(i % sum == 1)         {             flag[i] = true;             return true;         }         return false;     } }
点赞 回复 分享
发布于 2022-03-21 21:23
第一题用回溯超时了。。。
点赞 回复 分享
发布于 2022-03-21 21:19
第三题暴力搜索就行吧,直接对每个字符所在行和所在列进行验证,然后我就过了,第一题我后面才反应过来可以用递归划分,然后递归超时,想用递归改动态规划就来不及了,只有25%,第二题暴力超时80%
点赞 回复 分享
发布于 2022-03-21 21:13

相关推荐

一tiao酸菜鱼:秋招还没正式开始呢,就准备有结果了。。。。?
点赞 评论 收藏
分享
评论
13
30
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务