页面启动中 . . .

美团0309春招实习笔试

2024暑期
笔试真题
发布日期:   2024-03-09
更新日期:   2024-03-09
文章字数:   2k
阅读时长:   8 分
阅读次数:  

美团0309春招实习笔试

个人参加的第一场笔试，之前虽然了解过相关的笔试题型（公众号）。自己参加，感叹还得多练啊~

0309.T1

1. 题目说明

MT 是美团的缩写，因此小美很喜欢这两个字母。

现在小美拿到了一个仅由大写字母组成字符串，她可以最多操作k次，每次可以修改任意一个字符。小美想知道，操作结束后最多共有多少个’M’和’T’字符？

输入描述

第一行输入两个正整数，代表字符串长度和操作次数。第二行输入一个长度为的、仅由大写字母组成的字符串。1<=k<=n<=10^5

输出描述

输出操作结束后最多共有多少个’M’和’T’字符。

示例 1

输入

5 2
MTUAN

输出

4

说明

修改第三个和第五个字符，形成的字符串为 MTTAM，这样共有 4 个’M’和’T’。

2. 解答分析

  • 基础字符的处理，只用找出包含M和T的数量，统计计算即可；

    ​

3. 具体代码

import java.util.Scanner;

public class test111 {
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            int a=in.nextInt();
            int k=in.nextInt();
            String s=in.next();
            int count=0;
            for(int i=0;i<a;i++){
                if(s.charAt(i)=='M' || s.charAt(i)=='T'){
                    count++;
                }else if((s.charAt(i)!='M' || s.charAt(i)!='T') && k>0){
                    count++;
                    k--;
                }
            }
            System.out.println(count);
        }
}
  • 复杂度：
    • 时间复杂度： O(n)O(n)。指的是数组的长度n
    • 空间复杂度：O(1)O(1)，并未用到其余结构

0309.T2

1. 题目说明

小美拿到了一个由正整数组成的数组，但其中有一些元素是未知的（用 0 来表示）。

现在小美想知道，如果那些未知的元素在区间[l,r]范围内随机取值的话，数组所有元素之和的最小值和最大值分别是多少？

共有q次询问。

输入描述

第一行输入两个正整数n,q，代表数组大小和询问次数。

第二行输入n个整数ai，其中如果输入ai的为 0，那么说明ai是未知的。

接下来的q行，每行输入两个正整数l,r，代表一次询问。

1<=n,q<=10^5
0<=ai<=10^9
1<=l<=r<=10^9

输出描述

输出q行，每行输出两个正整数，代表所有元素之和的最小值和最大值。

示例 1

输入

3 2
1 0 3
1 2
4 4

输出

5 6
8 8

说明

只有第二个元素是未知的。
第一次询问，数组最小的和是 1+1=3=5，最大的和是 1+2+3=6。
第二次询问，显然数组的元素和必然为 8。

​

2. 解答分析

  • 这里最初的想法是统计0出现的个数，但是这样写会导致时间复杂度的增加，从而超时。

  • 回头想想，0出现的次序貌似并不重要，我们最后只需要求最大值和最小值，所以只用统计0的个数即可，最后在sum上加减即可。

  • 还要注意的是long类型的问题，一般要看清楚输入的数值的取值大小

    ​

3. 具体代码

import java.util.Scanner;

public class test222 {
    public static void main(String[] args) {
//        Scanner in = new Scanner(System.in);
//        int n=in.nextInt(); //数组大小
//        int q=in.nextInt(); //访问次数
//        long[]a =new long[n];
//        int count=0; //统计a[i]为0的个数
//        long res=0; //统计非0元素之和
//
//        for(int i=0;i<n;i++){
//            a[i]=in.nextLong();
//            res+=a[i];
//            if(a[i]==0){
//                count++;
//            }
//        }
//        for(int j=0;j<q;j++){
//            long l=in.nextLong();
//            long r=in.nextLong();
//            long res1=res,res2=res;
//            for(int i=0;i<count;i++){
//                res1+=l;
//                res2+=r;
//            }
//            System.out.println(res1+" "+res2);
//        }
// 上述代码的通过率只有86%，存在超时的情况...

        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int q = in.nextInt();

        int[] a = new int[n];
        int cnt = 0;
        int sum = 0;

        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
            if (a[i] == 0) {
                cnt++;
            }
            sum += a[i];
        }

        for (int j = 0; j < q; j++) {
            int l = in.nextInt();
            int r = in.nextInt();
            System.out.println((sum + zeros * l) + " " + (sum + zeros * r));
        }
    }
}

  • 复杂度：

    • 时间复杂度：O(n)

      ​

前两道题目都是常规的思路，基本上看完题目就可以写出来。但是需要注意超时的问题，下面的第三题开始就需要技巧了。

0309.T3

1. 题目说明

小美拿到了一个n*n 的矩阵，其中每个元素是 0 或者 1。

小美认为一个矩形区域是完美的，当且仅当该区域内 0 的数量恰好等于 1 的数量。

现在，小美希望你回答有多少个i*i的完美矩形区域。你需要回答1<=i<=n的所有答案。

输入描述

第一行输入一个正整数n，代表矩阵大小。

接下来的n行，每行输入一个长度为n的01 串，用来表示矩阵。（1<=n<=200）

输出描述

输出n行，第i行输出的I*I 完美矩形区域的数量。

示例 1

输入

4
1010
0101
1100
0011

输出

0
7
0
1
  • 这里要注意输入字符的顺序吧，比如1010，实际输入的顺序中含有空格：1 0 1 0；

2. 解答分析

  • 这里真的不用遍历二维数组的每一个位置，而是统计数组中的元素之和。

  • 直接枚举所有的边长i的正方形，判断正方形的和是否为i*i/2即可，用到的方法是二维前缀和；

    ​

3. 具体代码

  • 在列出常规的代码之前，先利用的是比较通俗的解法，或者说是直接看出来的解法：
import java.util.Arrays;
import java.util.Scanner;

public class test222_1 {

    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int n = in.nextInt(); //行列的数值
        int q = 0; // 下标
        char[][] arr=new char[n][n];
        in.nextLine(); // 读入字符串
        while(q < n){
            arr[q]=in.nextLine().toCharArray(); //将字符串优化成数组
            q++;
        }
      // 
        int[][][] dp = new int[n + 1][n + 1][2];
        int [] ans=new int[n ];

        for(int i = 0; i < n; i++){ //按照行进行遍历
            for(int j = 0; j < n; j++){	//按照列进行遍历
                for(int k = 0; k<Math.min(n - i,n - j); k++){ //边长为k的子矩阵
                    int count = 0;
                    for(int l = i; l <= i + k; l++){ //子矩阵的行中含有1的个数
                        if(arr[l][j + k] == '1') count++;
                    }
                    for(int l = j; l< j + k; l++){ //子矩阵的列中含有1的个数（第一列和第一行存在重复的元素，所以这里就没有遍历不等
                        if(arr[i + k][l] == '1') count++;
                    }
                    dp[i][j][1]=dp[i][j][0] + count; //统计得到的1的元素的个数，原先的+新统计的
                    if(dp[i][j][1] *2==(k + 1)*(k + 1)) ans[k]++; //注意数组的下标，判断，并且直接在ans数组上累计
                    dp[i][j][0]=dp[i][j][1]; //更新统计
                }
            }
        }
        for(int temp : ans){
            System.out.println(temp);
        }
    }
}
  • 前缀和
import java.util.Scanner;

public class test222 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[][] dp = new int[n][n];
        // 按照上述进行遍历元素也可，下面这个方法比较常规
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = scanner.nextInt(); //遍历数组
            }
        }
        // 前缀和数组
        int[][] pre = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + dp[i - 1][j - 1]; //前缀和
            }
        }
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    if (i + k >= n || j + k >= n) break;
                    int subMatrix = getSubMatrix(pre, i, j, i + k, j + k);
                    if (subMatrix * 2 == Math.pow(k + 1, 2)) {
                        ans[k]++;
                    }
                }
            }
        }
        for (int a : ans) {
            System.out.println(a);
        }
    }
    private static int getSubMatrix(int[][] pre, int x1, int y1, int x2, int y2) {
        return pre[x2 + 1][y2 + 1] - pre[x1][y2 + 1] - pre[x2 + 1][y1] + pre[x1][y1];
    }
}
//
文章作者: XKJ
文章链接: https://shakeJ96.github.io/2024/03/09/mei-tuan-0309-chun-zhao-shi-xi-bi-shi/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 XKJ !
2024暑期
赏
  目录