9.2 美团笔试面经- 编程题 & 题解

考试平台： 牛客

时间： 2023-09-02

考试题型： 5道编程题 （每题 20 分）

T1 小美的升序数组（20分）

给定一个大小为n的数组a，请你判断一个数组是否满足以下条件:

1. 数组严格升序，即 < <...< 。

2. 对于1 ≤ i ≤ n-1，我们定义 = - ，则数组b严格降序，即 > > ... > 。

输入描述

第一行输入一个正整数n，代表数组的大小 第二行输入n个正整数a，代表给定的数组 3 ≤ n ≤ 1 ≤ ≤

输出描述

若满足给定的两个条件，则输出 Yes。否则输出No

示例1

输入

3

1 3 4

输出

Yes

示例2

输入

3

1 3 3

输出

NO

示例3

输入

4

1 2 3 4

输出

NO

题解

简单模拟即可

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[n];

        for (int i = 0; i < n; i++) a[i] = scanner.nextInt();

        String rs = "YES";
        for (int i = 1, prevB = Integer.MAX_VALUE; i < n; i++) {
            int b = a[i] - a[i - 1];
            if (a[i - 1] < a[i] && prevB > b) {
                prevB = b;
            } else {
                rs = "NO";
                break;
            }
        }

        System.out.println(rs);
    }
}

T2 小美的子序列（20分）

小美在 n 行 m 列的本子上写了许多字母，她会在每一行中找出一个字母，然后组成一个字符串。 小美想知道，组成的字符串中是否存在至少一个字符串包含“meituan”子序列。

输入描述

第一行输入2个整数n,m (1 ≤ n,m ≤1000)。 接下来n行，每行输入一个长度为 m 的字符串表示小美写下的字母。

输出描述

若存在至少一个字符串包含"meituan"子序列，则输出"YES”，否则输出“NO”.

示例1

输入

3 3
abc
def
ghi

输出

NO

显然并不能找到meituan子序列。

示例2

输入

8 2
nm
ex
it
td
ul
qu
ac
nt

输出

YES

第1行选择第2个字母

第2行选择第1个字母。

第3行选择第1个字母

第4行选择第1个字母

第5行选择第2个字母

第6行选择第2个字母

第7行选择第1个字母

第8行选择第1个字母组成字符串”meitluan”，其中存在"meituan"子序列。

当然，第6行选第1个字母且第5行选第1个字母组成的字符串"meituqan”中也存在"meituan"子序列。

题解

双指针

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), m = scanner.nextInt();
        String[] words = new String[n];
        for (int i = 0; i < n; i++) words[i] = scanner.next();

        String rs = "meituan";
        int len = rs.length(), idx = 0;
        for (int i = 0; i < n && idx < len; i++) {
            if (words[i].indexOf(rs.charAt(idx)) > -1) idx++;
        }

        System.out.println(idx == len ? "YES" : "NO");
    }
}

当然也可以使用动态规划去解。

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), m = scanner.nextInt();
        String[] words = new String[n];
        for (int i = 0; i < n; i++) words[i] = scanner.next();

        String rs = "meituan";
        int len = rs.length();


        // dp[i][j] 为 true 表示前 rs[0, i) 在 words[0, j) 可以组成子序列
        boolean[][] dp = new boolean[len + 1][n + 1];
        dp[0][0] = true;

        for (int i = 0; i < len; i++) {
            char c = rs.charAt(i);
            for (int j = 0; j < n; j++) {
                dp[i + 1][j + 1] |= dp[i + 1][j];
                if (words[j].indexOf(c) > -1 && dp[i][j]) {
                    dp[i + 1][j + 1] = true;
                }
            }
        }


        System.out.println(dp[len][n] ? "YES" : "NO");
    }
}

T3 小美的数组（20分）

小美拿到了一个数组。她每次可以进行如下操作之一：

1. 选择一个元素，使其乘以 2。

2. 选择一个元素，使其除以 2，向下取整。

小美希望第一个元素变成所有元素的最大值。请你判断小美最少需要操作多少次?

输入描述

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

第二行输入n个正整数，代表小美拿到的数组 1 ≤ n ≤ 1 ≤ ≤

输出描述

输出最小操作次数。

示例1

输入

4
1 2 3 4

输