[数据结构与算法]美团春招暑期实习笔试——20220312

题目一

• 题目描述
  幸运数字至少满足以下两个特征中的一种
  1.数字是11的数倍
  2.数字中至少包含两个1
  小美现在给你若干的数字，希望你回答这个数字是不是幸运数字。

输入描述：
第一行一个数字n，表示小美有n组询问
接下来每一行一个正整数表示小美询问的数字。
数据保证1<=n<=500,每个询问的数字在【1，1e9】范围内

样例输入：
2
22
1234
样例输出：
yes
no

• Java代码

import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n=in.nextInt();
        while(in.hasNext()){
            int num=in.nextInt();
            if(num%11==0||oneCount(num)>=2){
                System.out.println("yes");
            }else{
                System.out.println("no");
            }
        }
    }
    private static int oneCount(int num) {
        int res=0;
        while (num>0){
            int remain=num%10;
            if(remain==1)res++;
            num=num/10;
        }
        return res;
    }
}

题目二

• 题目描述
  小美现在有一个序列，序列中包含1和-1两种数字。小美现在想要知道，有多少个连续的子序列，序列中的数字乘积为正。

输入描述：
第一行一个正整数n，表示小美手中的序列长度。
第二行n个空格隔开的数字，每个数字只能是1和-1中的一种。
对于80%的数据保证1<=n<=500
对于剩余的20%的数据保证1<=n<=5000

输出描述：
一行一个正整数表示有多少连续的子序列满足题目要求。

样例输入：
4
1 1 -1 -1

样例输出：
6

• 思路：先前缀和数组记录负数的个数，然后循环进行计算
• Java代码

import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        in.nextLine();
        //将输入放入转换为数组
        String s = in.nextLine();
        String[] arrS = s.split(" ");
        int[] nums=new int[n];
        for (int i = 0; i < n; i++) {
            nums[i]=Integer.parseInt(arrS[i]);
        }
        //计算前缀和，所有负数
        int[] preNegative=new int[n+1];
        for (int i = 1; i <= n; i++) {
            if(nums[i-1]==-1)preNegative[i]=preNegative[i-1]+1;
            else preNegative[i]=preNegative[i-1];
        }
        //双层循环计算一红有多少个序列
        int res=0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j <n ; j++) {
                int count=preNegative[j+1]-preNegative[i];
                if(count%2==0)res++;
            }
        }
        System.out.println(res);
    }
}

题目三

• 题目描述：点菜
  小美现在在厨房做饭。小美发现食材现在只够每种菜做一份。
  现在同一时刻（即不分先后顺序）来了n个顾客，每个顾客都有想两份要点的菜。只有当顾客吃到全部自己想要的菜的时候，顾客才会满意。
  现在你的任务是，合理地接取顾客的订单请求，尽可能让更多的顾客满意，并输出最多有多少顾客可以满意。

输入描述：
第一行两个正整数n,m
n表明有多少顾客前来点菜，m表示小美现在能做的菜的编号范围在【1，m】，
接下来的n行，每行两个数字，表明一名顾客的所点的两道菜的编号。
前80%数据保证2<=n<=10,2<=m<=20
剩余的80%数据保证2<=n<=20,2<=m<=40
输出描述：
一行一个正整数表示最多有多少顾客可以满意

样例输入：
3 4
1 2
2 3
3 4

样例输出：
2
解释：最佳方案满足第一个和第三个顾客

• 思路：采用递归的方法
• Java代码

import java.util.Arrays;
import java.util.Scanner;
public class Main{
    public static int res=0;
    public static int[][] arr;
    public static int[] flag;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m=in.nextInt();
        //存储顾客分别想要点的2道菜
        arr=new int[n][2];
        for (int i = 0; i < n; i++) {
            arr[i][0]=in.nextInt();
            arr[i][1]=in.nextInt();
        }
        //标记数字
        flag=new int[m+1];
        Arrays.fill(flag,1);
        int cnt=m/2; //最多可以满意的顾客数
        dfs(0,0,cnt,n);
        System.out.println(res);
    }

    //当前顾客数  已选择的人数
    private static void dfs(int guest, int sum,int cnt,int n) {
        if(sum<=cnt)res=Math.max(res,sum); //更新可选的最大的人数
        else return;
        for (int i = guest; i < n; i++) {
            int x1=arr[i][0],x2=arr[i][1];
            if(flag[x1]==0||flag[x2]==0)continue;
            flag[x1]--;flag[x2]--;
            //选择进行递归
            sum++;
            dfs(guest+1,sum,cnt,n);
            sum--;
            flag[x1]++;flag[x2]++;
        }
    }
}

题目四

• 题目描述
  小美现在打音游。这个音游的玩法是这样的：
  共有n个房间，小美初始拥有一个指针，指在一号房间。
  游戏共持续m秒，每秒会有一个房间产生炸弹，小美的指针不能在这个房间中
  每秒结束的瞬间，小美可以使用一次魔法，把指针切换到另一个房间中，该过程会消耗一个能量，
  你的任务是计算小美无伤通过音游消耗的最小的能量。
  保证第一秒炸弹不发生在一号房间中。

输入描述：
第一行两个正整数n，m，表示房间有n个，游戏持续m秒
第二行m个正整数，每个正整数在1到n的范围内，第i个表示炸弹爆炸的房间

样例输入：
2 4
2 1 1 2
样例输出：
2

样例输入：
3 10
2 3 1 3 2 1 1 2 3 1
样例输出：
3

• 笔者一开始做的时候用的是贪心算法，每次爆炸后用set集合记录爆炸及其之后的房间号，当记录到set的长度等于房间数n的时候再次爆炸，结果是部分样例通过，说明方法有误，代码如下
• Java代码

import java.util.HashSet;
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()){
            String s0 = in.nextLine();
            String[] s00 = s0.split(" ");
            int house=Integer.parseInt(s00[0]);
            int time=Integer.parseInt(s00[1]);
            String s = in.nextLine();
            String[] s1 = s.split(" ");
            //炸弹出现的数组
            int[] nums=new int[time];
            for (int i = 0; i < time; i++) {
                nums[i]=Integer.parseInt(s1[i]);
            }
            int res=0; //表示消耗的能量
            int currenthouse=1;
            HashSet<Integer> set = new HashSet<>();
            for (int i = 0; i < time; i++) {
                if(currenthouse==nums[i]){  //房间要爆炸
                    set.clear();
                    set.add(nums[i]);//爆炸的加进去
                    res++; //必须换房间，换的房间不知道
                    currenthouse=-1;//暂且不确定去哪个
                }
                else if(currenthouse!=nums[i]&&set.size()<house-1){
                    set.add(nums[i]);
                }
                else if(currenthouse!=nums[i]&&!set.contains(nums[i])){
                    set.clear();
                    set.add(nums[i]);//爆炸的加进去
                    res++; //必须换房间，换的房间不知道
                    currenthouse=-1;//暂且不确定去哪个
                }
            }
            System.out.println(res);
        }
    }
}

• 正确的思路是动态规划如下

import java.util.Arrays;
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n=in.nextInt();  //表示共n个房间
        int m=in.nextInt();  //表示游戏共持续m秒
        int[] bomb=new int[m+1];
        for (int i = 1; i <=m; i++) {
            bomb[i]=in.nextInt();
        }
        int[][] dp=new int[m+1][n+1]; //表示游戏持续到第i秒，小美指向j个房间
        for (int i = 0; i <=m; i++) {
            Arrays.fill(dp[i],Integer.MAX_VALUE-10000);
        }

        dp[1][1]=0;//初始，第一秒在第一个房间不消耗
        for (int i = 2; i <=m; i++) {
            for (int j = 1; j <=n; j++) {
                if(bomb[i]==j)continue;
                for (int k = 1; k <=n; k++) {
                    dp[i][j]=Math.min(dp[i-1][k]+(j==k?0:1),dp[i][j]);
                }
            }

        }
        int res=Integer.MAX_VALUE;
        for (int i = 1; i <=n; i++) {
            res=Math.min(res,dp[m][i]);
        }
        System.out.println(res);
    }
}