4.11百度度小满java笔试16:00-17:30

20道选择 2道编程(没想到还有选择 甚至还有多选

选择题

计网(ip地址)、OS(死锁)、算法知识(dp，prim算法)、java知识

编程题

1、n个灯 都开着 给m个数 每个数代表关闭i-n号灯
求每个灯的第一次关闭时间

简单题，因为求第一次关掉的时间，非常简单，每次更新最小值即可

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
    int[] nums = new int[m];
    int[] time = new int[n + 1];
    for (int i = 0; i < m; i++) {
        nums[i] = sc.nextInt();
    }
    int min = n + 1;
    for (int i = 0; i < m; i++) {
        if (nums[i] < min) {
            for (int j = nums[i]; j < min; j++) {
                time[j] = i + 1;
            }
            min = nums[i];
        }
    }
    for (int i = 1; i <= n; i++) {
        if (i == n) System.out.print(time[i]);
        else System.out.print(time[i] + " ");
    }
}

2、给定一个长度为n的字符串，求其中最长重复字符序列长度，同时有k次机会更改字符串
即 aaabbbccc k = 1
则输出 4
aaabaaac k = 1
输出 7 (b改为a)

滑动窗口即可

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int k = sc.nextInt();
    String s = sc.next();
    int startIndex = 0, maxLen = 0, maxTimes = 1;
    int[] times = new int[128];
    times[s.charAt(0)]++;
    for (int i = 1; i < n; i++) {
        char c = s.charAt(i);
        times[c]++;
        maxTimes = Math.max(times[c], maxTimes);
        int windowLen = i - startIndex + 1;
        if (windowLen > maxTimes + k) {
            times[s.charAt(startIndex)]--;
            startIndex++;
        } else {
            maxLen = Math.max(maxLen, windowLen);
        }
    }
    System.out.println(maxLen);
}