面试复盘|美团一面挂

美团

美团到家事业群，内推：微信 base：北京

投递：20210815 后端开发工程师

笔试：20210822

全排列问题；字符串；括号匹配；数组操作问题

1. 全排列+字典序排序

   package meituan;

   import java.util.*;

   /**
    * 全排列问题
    * 给定数组长度和数组；输出排列数和排列（按字典序给出）
    * 60%的样例，数组长度不超过3;所有的样例n不超过6
    * 数组中的数字在1，n范围内，存在重复出现的值
    */
   public class Solution1 {
       public static List> permute(int[] nums) {
           List> res = new ArrayList();
           List output = new ArrayList();
           for (int num : nums) {
               output.add(num);
           }
           int n = nums.length;
           backtrack(n, output, res, 0);
           return res;
       }

       private static void backtrack(int n, List output, List> res, int first) {
           if (first == n) {
               res.add(new ArrayList(output));
           }
           for (int i = first; i < n; i++) {
               Collections.swap(output, first, i);
               backtrack(n, output, res, first + 1);
               Collections.swap(output, first, i);
           }
       }

       public static void main(String args[]) {
           Scanner sc = new Scanner(System.in);
           int n = sc.nextInt();
           int[] array = new int[n];
           for (int i = 0; i < n; i++) {
               array[i] = sc.nextInt();
           }

           int cnt = 1; // 排列计数
           List> rank = new ArrayList();

           if (n == 1) {
               System.out.println("1");
               System.out.println("1");
           }
           if (n == 2) {
               System.out.println(2);
               System.out.println("1 2");
               System.out.println("2 1");
           }
           rank = permute(array);
           System.out.println(rank);
       }
   }

2. 操作字符串

   package meituan;

   import java.util.HashMap;
   import java.util.Map;
   import java.util.PriorityQueue;
   import java.util.Scanner;

   /**
    * 字符串处理：
    * 给定字符串和n次操作，有两种操作，由1 2标记，
    * 1 表示往s后插入字符；
    * 2 表示查询和当前位置字符相同的最近的另一个位置，不存在输出-1
    */
   public class Solution2 {
       private static Map> hashmap = new HashMap();

       public static void add(char c, int pos) {
           PriorityQueue queue = hashmap.getOrDefault(c, new PriorityQueue());
           queue.add(pos);
           hashmap.put(c, queue);
       }

       public static void main(String[] args) {
           Scanner sc = new Scanner(System.in);
           // 原字符串
           String s = sc.nextLine();
           int length = s.length();
           // 操作次数
           int n = sc.nextInt();
           // 计数
           for (int i = 0; i < s.length(); i++) {
               char c = s.charAt(i);
               add(c, i + 1);
           }
           // 新增字符
           StringBuilder sb = new StringBuilder(s);
           // 记录添加的次数，用于计算添加后新字符的位置
   //        System.out.println("map:" + hashmap);
           for (int i = 0; i < n; i++) {
               int op = sc.nextInt();
               // 末尾添加字符
               if (op == 1) {
                   char c = sc.next().charAt(0);
                   sb.append(c);
                   length++;
                   add(c, length);
               }
               // 判断最近的同字符位置
               if (op == 2) {
                   int pos = sc.nextInt();
                   if (pos < length) {
                       char cc = sb.charAt(pos - 1);
                       Object[] positions = hashmap.get(cc).toArray();
                       if (positions.length == 1) {
                           System.out.println("-1");
                           break;
                       }
                       int ii = 0; // 优先队列中的位置
                       for (int j = 0; j < positions.length; j++) {
                           if (pos == (int) positions[j]) {
                               ii = j;
                               break;
                           }
                       }
                       if (ii == 0) {
                           System.out.println(Math.abs((int) positions[0] - (int) positions[1]));
                       } else if (ii == positions.length - 1) {
                           System.out.println(Math.abs((int) positions[ii] - (int) positions[ii - 1]));
                       } else {
                           System.out.println(Math.min(Math.abs((int) positions[ii] - (int) positions[ii - 1]), Math.abs((int) positions[ii] - (int) positions[ii + 1])));
                       }

                   }

               }
           }

       }
   }

3. 括号匹配问题

   package meituan;

   import java.util.Scanner;
   import java.util.Stack;

   /**
    * "阔浩"序列-->括号嵌套问题
    * null --> 1
    */
   public class Solution3 {
       public static void main(String args[]) {
           Scanner sc = new Scanner(System.in);
           String s = sc.next();
           int res = 1;
           if (s == null || s.equals("")) System.out.println(1);
           Stack stack = new Stack();
           // 遍历字符串
           for (int i = 0; i < s.length(); i++) {
               if (s.charAt(i) == '(') {
                   stack.push(0);
               } else {
                   int top = stack.peek();
                   top = top == 0 ? 2 : top + 1;
                   stack.pop();
                   if (stack.isEmpty())
                       res *= top;
                   else {
                       int sco = stack.pop();
                       sco *= top;
                       stack.push(sco);
                   }
               }
           }
           System.out.println(res);
       }
   }

4. 数组操作：

   package meituan;

   import java.util.Scanner;

   /**
    * 小美当上了会计。她现在拿到了n个开支数据 a[1],a[2],…,a[n]，现在她想稍微对这些数据做一些统计。
    * 
    * 小美有三种想统计的信息。第一种是她选择一个区间[L,R]，希望知道a[L] + a[L+1] + … + a[R]等于多少，第二种是她选择一个区间[L,R]，希望知道a[L],a[L+1],…,a[R]这些数据的有效值是多少。第三种是她选择一个区间[L,R]，希望知道a[L],a[L+1],…,a[R]的最大值是多少。
    * 
    * 一组数据b[l],b[2],…,b[r]的有效值，定义为
    * 
    * 
    * 输入描述
    * 第一行一个整数n，表示一共有n个数。
    * 
    * 第二行n个整数,a[1],a[2],…,a[n]，表示小美拿到的数据分别是哪些。
    * 
    * 第三行一个整数m，表示一共有m个询问。
    * 
    * 接下来m行，每行三个整数，opt, L, R，当opt=1时表示是第一种询问， opt=2时表示第二种询问，opt=3时表示第三种询问。（1 <= opt <= 3，1 <= L <= R <= n）
    * 
    * 数据保证每个收支数据a[i]满足 -1000 <= a[i] <= 1000。
    * 
    * 统计次数m满足1 <= m <= 500。
    * 
    * 其中，对于60%的数据n满足1 <= n <= 1,000。
    * 
    * 对于100%的数据n满足1 <= n <= 100, 000。
    * 
    * 输出描述
    * 输出m行，每行一个数，表示该行对应询问的答案。
    */
   public class Solution4 {
       public static int sum(int[] nums, int l, int r) {
           int s = 0;
           for (int j = l - 1; j < r; j++) {
               s += nums[j];
           }
           return s;
       }

       public static int maxN(int[] nums, int l, int r) {
           int max = 0;
           for (int j = l - 1; j < r; j++) {
               if (nums[j] > max)
                   max = nums[j];
           }
           return max;
       }

       public static void main(String args[]) {
           Scanner sc = new Scanner(System.in);
           // 数组长度
           int n = sc.nextInt();
           // n 个数据
           int[] nums = new int[n];
           for (int i = 0; i < n; i++) {
               nums[i] = sc.nextInt();
           }
           // 操作数
           int m = sc.nextInt();
           // op标号（123），左右区间

           for (int i = 0; i < m; i++) {
               int op = sc.nextInt();
               int l = sc.nextInt();
               int r = sc.nextInt();
               int s = sum(nums, l, r);
               switch (op) {
                   case 1:
                       System.out.println(s);
                       break;
                   case 2:
                       int temp = 0;
                       for (int j = l - 1; j < r; j++) {
                           temp += (s - nums[j]) * (s - nums[j]);
                       }
                       System.out.println(temp);
                       break;
                   case 3:
                       System.out.println(maxN(nums, l, r));
                       break;
               }
           }
       }
   }