2024小红书5.7暑期实习笔试记录_小红书暑期实习数据开发笔试

第一题 动态规划模拟递归
第一题的坑就是动态规划实现递归，类似于爬台阶，给定a1=a0=1，ai = A*ai-1+B*ai-2，最后要求输出每次查询得到的结果经过取模M后的结果。难点在于直接相乘会溢出，可以把取余放到每一个ai的求解过程中。

import java.util.Scanner;
import java.util.*;
 
public class Main {
Scanner sc = new Scanner(System.in);
int A = sc.nextInt();
        int B = sc.nextInt();
        int M = sc.nextInt();
        int num = sc.nextInt();
        int max = 0;
        int[] nums = new int[num];
        for(int i = 0; i<num; i++){
            int id = sc.nextInt();
            nums[i] = id;
            max = Math.max(max, id);
        }
        int[] dp = new int[max+1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i<=max; i++){
            dp[i] = (dp[i-1] * A)%M + (dp[i-2] * B)%M;
        }
        for(int i=0; i<num; i++){
            System.out.println(dp[nums[i]]%M);
        }
}
}

第二题 贪心解决求切割连续子集后最小值中的最大值
第二题很奇怪。。。。说是给你一个数组，可以对他操作k次，每次可以删除一个连续的子集（保证删除后数组元素数量大于0），求删除子集最小值中的最大值。比如k=1且58 57 62 86 89 24 26 65 42，结果就是58.（看了半天还以为很难，一想删两下，不肯定是输出数组最大值吗，输出一下过了36，然后推算一下，如果k=1，就直接输出头尾最大值。。。）
 

import java.util.Scanner;
import java.util.*;
 
public class Main {
Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] nums = new int[n];
        for(int i = 0; i<n; i++){
            nums[i] = sc.nextInt();
        }
      if(k>2){
        Arrays.sort(nums);
        System.out.println(nums[n-1]);
      }else{
        System.out.println(Math.max(nums[0], nums[n-1]));
}
}

第三题集合解决小球问题
第三题。。给T组测试样例，n是袋子数量，每个袋子第一个数是袋子中球数，剩下是球的编号。
每组测试样例要求满足：每个袋子中球数相等、一个小球要么出现在一个袋子，要不出现在所有袋子，每个袋子里面小球编号两两不同。满足输出Yes以及从小到大公共球的编号、不满足输出No
 

 
import java.util.Scanner;
import java.util.*;
 
public class Main {
    public static Boolean flag1(List<HashSet<Integer>> list, int size){
        HashMap<Integer, Integer> map = new HashMap<>();
        int balls = list.size();
        for(HashSet<Integer> set : list){
            if(set.size()!=size){
                return false;
            }
            for(Integer ball : set){
                map.put(ball, map.getOrDefault(ball, 0)+1);
            }
        }
        for(Map.Entry entry : map.entrySet()){
            if((int) entry.getValue() != 1&&(int)entry.getValue() != balls){
                return false;
            }
        }
        return true;
    }
 
    public static String flag2(List<HashSet<Integer>> list){
        Map<Integer, Integer> map = new TreeMap<>();
//        ArrayList<Integer> res = new ArrayList<>();
        StringBuilder res = new StringBuilder("");
        for(HashSet<Integer> set : list){
            for(Integer ball : set){
                map.put(ball, map.getOrDefault(ball, 0)+1);
            }
        }
        for(Map.Entry entry : map.entrySet()){
            if((int)entry.getValue()==list.size()){
//                res.add((Integer) entry.getKey());
                res.append((int)entry.getKey()).append(" ");
 
            }
        }
        return res.toString();
    }
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for(int i = 0; i<T; i++){//共有多少组测试数据
            List<HashSet<Integer>> list = new ArrayList<>();
            int n = sc.nextInt();
            int stdBall = 0;
            for(int j=0;j<n; j++){//共有几个袋子
                int balls;
                balls = sc.nextInt();//每个袋子共有几个球
                if(j==0){
                    stdBall = balls;
                }
                HashSet<Integer> set = new HashSet<>();
                for(int k=0; k<balls; k++){
                    set.add(sc.nextInt());
                }
                list.add(new HashSet<>(set));
            }
 
            //对每一组测试数据输出
//            System.out.println(list);
            if(flag1(list, stdBall)){
                String combine = flag2(list);
                System.out.println("Yes " + " " + combine);
            }else {
                System.out.println("No");
            }
 
        }
    }
}