20220919迅雷笔试（数开）

20220919迅雷笔试

写在前面：题量蛮大的，一个半小时，20道单选、10道多选、3道编程，在这里记录下吧

编程题

1.字典树的题，时间不咋够，暴力写得，过80，最后没时间改了，原题连接在此电话列表不再赘述

2.前缀数组的一个题，dp组成前缀数组，然后双重循环过得，源码如下-->大意就是说给你一个数组，要分成三片，这三片要符合（第一片的和<=第二片的和<=第三片的和）

import java.util.*;

public class Main4 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        ArrayList<Integer> list = new ArrayList<>();
        while(sc.hasNext()){
            list.add(sc.nextInt());
        }
        Integer[] data = new Integer[list.size()];
        data = list.toArray(data);
//        int[] data = new int[]{1,2,2,2,5,0};
        int[] dp = new int[data.length];
        dp[0] = data[0];
        for(int i = 1;i<dp.length;++i){
            dp[i] = data[i]+dp[i-1];//获取前缀数组
        }
        int res = 0;
        for(int i = 0;i<data.length;++i){
            for(int j = i+1;j<data.length;++j){
                if(dp[i]<=dp[j]-dp[i]&&dp[j]-dp[i]<=dp[data.length-1]-dp[j]) {
                    ++res;
                }
            }
        }
        System.out.println(res);
    }
}

3.力扣2139-->得到目标值的最少行动次数，先是用贪心（先乘后加）尝试，过28，后改变策略，只在偶数上贪心，奇数需要先行变成偶数（反向思维-->原题可以变为“如何用最少的操作次数将target转化为1”），过了，源码在此

import java.util.Scanner;

public class Main5 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String seq = sc.next();
        String[] segs = seq.split(",");
        int target = Integer.parseInt(segs[0]);
        int maxDoubles = Integer.parseInt(segs[1]);
        int count = 0;
        while(target>1){
            if(target%2==1){
                --target;
                ++count;
            }
            if(maxDoubles!=0){
                target /= 2;
                --maxDoubles;
                ++count;
            }
            if(maxDoubles==0){
                count = count+target-1;
                target = 1;
            }
        }
        System.out.println(count);

    }

}

以上
希望对大家有所帮助