【牛客】【刷题节】美团2024届秋招笔试第一场编程真题

1.小美的外卖订单【简单题】

题意理解：

这道题是简单题，主要是一个逻辑实现和判断的问题。但是简单题一般喜欢加一点小障碍，所以读题的时候就要比较注意一些约束条件。就比如这道题：过了15/20个测试用例，出现error, 当时没明白到底哪里校验有问题，最后发现：原价、折扣、满减都是正实数。所谓正实数：没有0！！！

正实数：是实数（real numbers）中的一个重要概念，它们是大于0的所有实数。正实数包括正整数、正分数（即正小数）以及正无理数。

还涉及一些边边角角的考核：小数点保留两位

解题思路：

1.计算每道菜的折扣价原价-折扣价，注意约束条件判断：原价>=折扣价>0

2.统计所有菜原价sum1

3.统计所有菜折扣价sum2

4.判断原价是否满足满减 sum1>=满减>0,并返回满减后的价格给sum1

5.返回最优惠min(sum1,sum2)

1.题目实现

import java.text.DecimalFormat;
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        double[][] prices = new double[n][2];
        for (int i = 0; i < n; i++) {
            prices[i][0] = in.nextDouble();
            prices[i][1] = in.nextDouble();
        }
        double x = in.nextDouble();
        double y = in.nextDouble();
        System.out.println(main.compute(prices, x, y));
    }

    public String compute(double[][] prices, double x, double y) {
        if (x==0||y==0||x < y|| y<0) return "error";
        double cost1 = 0.0;
        double cost2 = 0.0;
        for (int i = 0; i < prices.length; i++) {
            if(prices[i][0]==0||prices[i][0]==0) return "error";
            if (prices[i][0] >= prices[i][1]&&prices[i][1]>0) {
                cost1 += prices[i][0];
                cost2 += prices[i][1];
            } else {
                return "error";
            }
        }
        double minCost = cost2;
        //满减否
        if (cost1 >= x) { //满足满减条件
            minCost = Math.min(minCost, cost1 - y);
        }
        DecimalFormat df = new DecimalFormat("#.00");
        return df.format(minCost);
    }
}

2.复杂度分析

时间复杂度：O(n) 遍历菜的时间损耗

空间复杂度：O(n) 存储菜的空间损耗

2.小美的字符串匹配度【不难，但题看错了气死！】

题意理解：

这道题想复杂了，原因是题没读明白，所以读题真的太重要了！！！

这题给定两个字符串，从头开始往后匹配

对于字符串可以操作一次两个元素换位置，最多操作一次，可以不操作

最终，我们能获得的最大匹配是多少？

解题思路：

实现：借鉴大佬思路

遍历s和t,将对应位置上匹配到的元素剔除，删除后，上下元素坐标一致且值不同

如："abacd"和"aabdd“ 操作完 ”bca“ 和”abd“

bac和abd中，遍历s: bac ，若取到b,i=0；

在t:abd中找可以匹配的b ,如j=1时，匹配

此时有个需要额外注意的点：

s[i]=b == t[j]==b 将t串，i|j位置互换，在i位置上获得一个匹配，+1

额外的判断： s[j]==t[i] 交换后，对应的j位置是否能再次获得一个匹配呢？

1.题目实现

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        in.nextLine();
        String s1 = in.nextLine();
        String s2 = in.nextLine();
        System.out.println(main.compute(s1, s2));
    }

    public int compute(String s1, String s2) {
        int pairs = 0;
        int len = s1.length(); //s1和s2等长
        StringBuilder sb1 = new StringBuilder(s1);
        StringBuilder sb2 = new StringBuilder(s2);
        //在s2中找s1的匹配
        for (int i = 0; i < len; i++) {
            if (sb1.charAt(i) == sb2.charAt(i)) {
                sb1.deleteCharAt(i);
                sb2.deleteCharAt(i);
                i--;//第i个被删除后，回溯到前一个
                len--;
                pairs++;
            }
        }
        len = sb1.length();
        int changePairs = 0;
        for (int i = 0; i < len; i++) {
            for (int j = i; j < len; j++) {
                if (sb1.charAt(i) == sb2.charAt(j) || sb1.charAt(i) == sb2.charAt(j)) {
                    changePairs = Math.max(1, changePairs);
                } 
                if (sb1.charAt(i) == sb2.charAt(j) && sb1.charAt(j) == sb2.charAt(i)) {
                    changePairs = 2;
                    break;//最多增加两个匹配，不会再多了，所以可以退出了
                }
            }
        }
        return pairs+changePairs;
    }
}

2.复杂度分析

时间复杂度：O(n^2) 双for时间损耗

空间复杂度：O(2n) 两字符串长度空间损耗

3.小美的树上染色【有难度，但是很大原因是题看错了】

题意理解：

按照要求对节点染色，要求染色的节点最多。

相邻为染色且和为平方数的两节点染色。

这道题目是：一定要染红嘛？想复杂了，如果可以染色，一定要染。然后这道题变成了简单题。一定要仔细看题看题。

看了大佬解题思路有个地方不明白，为什么要从后往前遍历边呢？

反着测试用例过不去，不理解！有懂得大佬能给我讲讲嘛~

解题思路：

1.遍历所有的边，判断两节点是否满足染色要求：相邻为染色且和为平方数的两节点染色。

2.符合条件：两节点染色，sum+=2

1.题目实现

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Main solution=new Main();
        Scanner in = new Scanner(System.in);
        int n=in.nextInt();
        int[][] node=new int[n][2];
        for(int i=0;i<n;i++){
            node[i][0]=in.nextInt();
            node[i][1]=0;
        }
        int[][] lines=new int[n-1][2];
        for(int i=0;i<n-1;i++){
            lines[i][0]=in.nextInt()-1;
            lines[i][1]=in.nextInt()-1;
        }
        System.out.println(solution.compute(n,node,lines));
    }

    /**
     * 计算染色节点
     * @param n 节点个数
     * @param node  0是权值，1是颜色；（0白色1红色）
     * @param lines 边关系
     * @return
     */
    public int compute(int n,int[][] node,int[][] lines){
        int result=0;
        for(int i=lines.length-1;i>=0;i--){
            //两个相邻白色节点
            if(node[lines[i][0]][1]==0&&node[lines[i][1]][1]==0){
                //是平方数
                float product=node[lines[i][0]][0]*node[lines[i][1]][0];
                if(Math.sqrt(product)-(int)Math.sqrt(product)==0){
                    node[lines[i][0]][1]=1;
                    node[lines[i][1]][1]=1;
                    result+=2;
                }
            }
        }
        return result;
    }
}

2.复杂度分析

时间复杂度: O(n)遍历边

空间复杂度：O(n^2) 边、节点的存储

4.小美的排列询问【简单题】

题意理解：

遍历数组，查看给出的元素是否相邻即可

解题思路：

1.遍历数组，找到其中一个元素

2.查看另一个元素是否在该元素的左|右

3.若在Yes

4.不在则下一个，遍历完都找不到，No

1.题目实现

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = in.nextInt();
        }
        int x = in.nextInt();
        int y = in.nextInt();
        System.out.println(main.compute(nums, x, y));
    }
    public String compute(int[] nums, int x, int y) {
        int a = Math.min(x, y);
        int b = Math.max(x, y);
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == a && ((i + 1) < nums.length && nums[i + 1] == b || i - 1 >= 0 &&
                                 nums[i - 1] == b)) return "Yes";
            else if (nums[i] == a && !((i + 1) < nums.length && nums[i + 1] == b ||
                                       i - 1 >= 0 && nums[i - 1] == b)) return "No";
        }
        return "No";
    }
}

2.复杂度分析

时间复杂度：O(n) 遍历数组的时间损耗

空间复杂度：O(n) 数组存储的空间损耗

5.小美的排列构造【这也是道简单题】

题意理解：

首先明确：数组权值：对相邻两项求和，其中最大值和最小值的差值

为了绕让权值尽可能的小

就要使相临两数之间的和差不多的大。

一个思路是：首先对数组进行排序。

从数组末尾取数据，往数组前面的元素间插入，总是一个小值，一个大值的。

但是测试没过，不知道哪里的问题。——错在了，奇数个元素时，漏了一个元素

解题思路：

1.题目实现

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        System.out.println(main.compute(n));
    }
    public String compute(int n){
        StringBuilder sb=new StringBuilder();
        for(int i=1;i<=n/2;i++){
            sb.append(i+" "+(n-i+1)+" ");
        }
        if(n%2!=0){
            sb.append((n+1)/2);
        }
        return sb.toString();
    }
}

2.复杂度分析

特别有意思的一点：【记录一下】

用String result+""拼接字符串，超时了

但是用StringBulider是可以的

时间复杂度：O(n/2)遍历一半数据的时间损耗

空间复杂度：O(n)存储数据的空间损耗

6.小美走公路【简单题】

题意理解：

由于是环形公路，所有从x到y站无非两种方式：顺时针|逆时针

可以统计全程sum，和x到y的顺时针长度len1,则逆时针sum-len1

解题思路：

1.遍历所有的站点到下一站距离

2.统计全程长度sum

3.当遍历到x站点开始统计长度len1,到站点y结束

4.返回min（sum-le1,len1）

1.题目实现

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Main main=new Main();
        Scanner in = new Scanner(System.in);
        int n=in.nextInt();
        long[] a=new long[n];
        for(int i=0;i<n;i++){
            a[i]=in.nextLong();
        }
        long x=in.nextLong();
        long y=in.nextLong();
        System.out.println(main.compute(a,x,y));
    }
    public long compute(long[] a,long x,long y){
        long start=Math.min(x,y);
        long end=Math.max(x,y);
        long sum=0;//整圈
        long left=0;//从start->end
        for(int i=0;i<a.length;i++){
            if(i>=start-1&&i<end-1) left+=a[i];
            sum+=a[i];
        }
        return Math.min(left,sum-left);
    }
}

2.复杂度分析

时间复杂度分析：O(n) 遍历站点的时间损耗

空间复杂度分析：O(n) 站点存储的时间损耗

7.小美的好矩阵【感觉自己思路没错，但是测试用例没过】

题意理解：

在n*m的矩阵中找到一个符合好矩阵的条件矩阵。有多少个？

解题思路：

row[i][j]:第i行，第j个位置，构造一个行，是否满足好矩阵一个行的条件：true|false

思路是这样的，首先对每行的每个位置开始，构造一个行，判断其是否符合好矩阵的行。

contains[i][j][k]:第i行，第j个位置，构造一个行，包含ABC的个数:k=0:A,k=1:B,k=3:C

col[i][j]:第i列，第j个位置，构造一个列，是否满足好矩阵一个列的条件：true|false

对每列的每个位置开始，构造一个列，判断其是否符合好矩阵的列。

1.题目实现

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Main main=new Main();
        Scanner in = new Scanner(System.in);
        int n=in.nextInt();
        int m=in.nextInt();
        in.nextLine();
        char[][] map=new char[n][m];
        for(int i=0;i<n;i++){
            map[i]=in.nextLine().toCharArray();
        }
        System.out.println(main.compute(map,n,m));
    }

    public int compute(char[][] map,int n,int m) {
        boolean[][] row = new boolean[n][m];
        boolean[][] col = new boolean[n][m];
        boolean[][][] contains=new boolean[n][m][3];
        Deque<int[]> queue = new LinkedList<>();
        //初始化:行检测
        for (int i = 0; i < n; i++) {//行检测
            for (int j = 0; j < m; j++) {
                if (queue.size() == 3) {
                    queue.pollFirst();
                }
                if ("ABC".contains(Character.toString(map[i][j]))) {
                    if(!queue.isEmpty()){
                        int pre_i = queue.peekLast()[0], pre_j = queue.peekLast()[1];
                        if (map[pre_i][pre_j] == map[i][j]) {//与前一个重复，丢弃前面的
                            queue.clear();
                        }
                    }
                    queue.offerLast(new int[]{i, j});//加入最新元素
                    if (queue.size() == 3) {
                        row[i][j] = true;//当前及前两个构成一个结果
                        if(map[i][j]=='A'||map[i][j-1]=='A'||map[i][j-2]=='A') contains[i][j][0]=true;
                        if(map[i][j]=='B'||map[i][j-1]=='B'||map[i][j-2]=='B') contains[i][j][1]=true;
                        if(map[i][j]=='C'||map[i][j-1]=='C'||map[i][j-2]=='C') contains[i][j][2]=true;
                    }

                } else {
                    queue.clear();
                }
            }
            queue.clear();
        }
        queue.clear();
        //初始化:列检测
        for (int j = 0; j < m; j++) { //列检测
            for (int i = 0; i < n; i++) {
                if (queue.size() == 3) {
                    queue.pollFirst();
                }
                if ("ABC".contains(Character.toString(map[i][j]))) {
                    if(!queue.isEmpty()){
                        int pre_i = queue.peekLast()[0], pre_j = queue.peekLast()[1];
                        if (map[pre_i][pre_j] == map[i][j]) {//与前一个重复，丢弃前面的
                            queue.clear();
                        }
                    }
                    queue.offerLast(new int[]{i, j});//加入最新元素
                    if (queue.size() == 3) {
                        col[i][j] = true;//当前及前两个构成一个结果
                    }

                } else {
                    queue.clear();
                }
            }
            queue.clear();
        }
        //九宫格检查
        int result = 0;
        for (int i = 2; i < n; i++) {
            for (int j = 2; j < m; j++) {
                //矩阵里有没有ABC:查三行元素
                //containsC[i][j]||containsC[i-1][j]||containsC[i-2][j])
                //三行检测:倒着数三行
                //row[i][j]&&row[i-1][j]&&row[i-2][j]
                //三列检测:倒着数三行
                //col[i][j]&&col[i][j-1]&&col[i][j-2]
                if ((contains[i][j][0]||contains[i-1][j][0]||contains[i-2][j][0])&&//有A
                        (contains[i][j][1]||contains[i-1][j][1]||contains[i-2][j][1])&&//有B
                        (contains[i][j][2]||contains[i-1][j][2]||contains[i-2][j][2])&&//有C
                        row[i][j] && row[i - 1][j] && row[i - 2][j] &&
                                col[i][j] && col[i][j - 1] && col[i][j - 2]) {
                    result++;
                }

            }
        }
        return result;
    }
}

2.复杂度分析

时间复杂度：O(n*m) 双for的时间损耗

空间复杂度：O(n*m*3) contains的空间损耗

这道题主要难在了判断和分析上，要做到准确且不漏

8.小美的蛋糕切割【简单题】

题意理解：

切蛋糕，这里把蛋糕看成n*m个小格子组成的整体，不能把小格子切开，所以切蛋糕的位置就是（n+m），切开之后，美味度是每部分小格子权值和

解题思路：

1.遍历横切n个位置，求每次的最小美味度差值

2.遍历竖切m个位置，求每次的最小美味度差值

3.返回最小美味度差值（此处差值求绝对值）

1.题目实现

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Main main=new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[][] cake=new int[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                cake[i][j]=in.nextInt();
            }
        }
        System.out.println(main.compute(cake,n,m));
    }

    public int compute(int[][] cake,int n,int m){
        long[] row=new long[n];
        long[] col=new long[m];
        long sum=0;
        long minResult=Integer.MAX_VALUE;
        //行计数+总和计数
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                row[i]+=cake[i][j];
            }
            sum+=row[i];
        }
        //列计数
        for(int j=0;j<m;j++){
            for(int i=0;i<n;i++){
                col[j]+=cake[i][j];
            }
        }
        //遍历横刀切
        long cake1=0,cake2=0;
        for(int i=0;i<=n-1;i++){
            cake1+=row[i];
            cake2=sum-cake1;
            minResult=Math.min(minResult,Math.abs(cake1-cake2));
        }
        //遍历横刀切
        cake1=0;cake2=0;
        for(int j=0;j<=m-1;j++){
            cake1+=col[j];
            cake2=sum-cake1;
            minResult=Math.min(minResult,Math.abs(cake1-cake2));
        }
        return (int)minResult;
    }
}

2.复杂度分析

时间复杂度：O(n^2) 双for循环损耗

空间复杂度：O(n^2) cake数组空间损耗

9.小美的字符串变换【困难：图相关的没复习】

题意理解：

看大佬的做法，这是dfs，深度遍历，但是emmmm，图论没有好好复习哎。

借鉴了下大佬思路，其实不难。就是递归遍历图，和遍历树是一样的。只是这里借助一个uesd存储访问状态。

解题思路：

将字符串n铺成一个矩阵

该矩阵的权值：连通块数

欲求最小的连通块数。

1.遍历所有可能的矩阵组合，即n%i==0

2.在每一个可能的矩阵组合中，统计联通图个数。

3.统计连通图个数用count来维护，dfs(map, used, x, y, ++count);

每找到一个连通图，count++(同一块，count相同)

如：矩阵：aababbabb used中的count: [1, 1, 2, 3, 4, 4, 5, 6, 6]

1.解题思路

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        in.nextLine();
        String input = in.nextLine();
        
        Main main = new Main();
        System.out.println(main.compute(n, input));
    }
    
    public int compute(int n, String s) {
        int res = Integer.MAX_VALUE;
        for (int i = 1; i <= n; i++) {
            if (n % i == 0) { //摆阵

                char[][] map = new char[i][n / i];
                int[][] used = new int[i][n / i];
                //赋值
                int index = 0;
                for (int x = 0; x < i; x++) {
                    for (int y = 0; y < n / i; y++) {
                        map[x][y] = s.charAt(index++);
                    }
                }
                //dfs计算联通图树
                //赋值
                int count = 0;
                for (int x = 0; x < i; x++) {
                    for (int y = 0; y < n / i; y++) {
                        //寻找每一个
                        if (used[x][y] == 0) {
                            dfs(map, used, x, y, ++count);
                        }
                    }
                }
                res = Math.min(res, count);

            }
        }
        return res;
    }

    public void dfs(char[][] map, int[][] used, int i, int j, int count) {
        /**
         * i,j越界或该位置已被访问过
         */
        if (i < 0 || j < 0 || i > map.length - 1 || j > map[0].length - 1 ||
                used[i][j] != 0) return;
        used[i][j] = count;
        /**
         * 像四个位置尝试扩展
         */
        if (i > 0 && map[i][j] == map[i - 1][j]) {
            dfs(map, used, i - 1, j, count);
        }
        if (i < map.length - 1 && map[i][j] == map[i + 1][j]) {
            dfs(map, used, i + 1, j, count);
        }
        if (j > 0 && map[i][j] == map[i][j - 1]) {
            dfs(map, used, i, j - 1, count);
        }
        if (j < map[0].length - 1 && map[i][j] == map[i][j + 1]) {
            dfs(map, used, i, j + 1, count);
        }
    }
}

2.复杂度分析