0913 滴滴笔试 java

比较简单，两题编程。

选择题好像是 20 题，有部分不确定，有 C++的几题。

题目记不清了，凭印象写一下。

编程题

第一题 充电

第一题：n个玩具，m 电量，尽可能让一个大的区间内的玩具的电量充满。输出充满电的玩具个数 。

双指针+滑动窗口。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        new Main().run();
    }

    // n个玩具，m 电量，尽可能让一个大的区间内的玩具的电量充满。既然是连续的，那直接维护m即可。如果电量不足，则排出头部元素，补充电量。

    public void run(){
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        long m = sc.nextLong();
        int[] charge = new int[n];
        for(int i = 0; i < n; i++) charge[i] = sc.nextInt();

        // 双指针
        int ans = 0;
        int idx = 0;  // 头部元素
        for(int i = 0; i < n; i++){

            while(m < charge[i]){
                m += charge[idx++];
            }

            if(m >= charge[i]){
                m -= charge[i];
            }

            ans = Math.max(ans, i - idx + 1);
        }
        System.out.println(ans);
    }
}

第二题 变化排行榜

题意：有一个排行榜，长度是 n，然后现在可以接收 n 个 op，如果是 1 则需要调低这首歌的位置，如果是 0 则不变，如果是 -1 则需要调高这个歌的位置。如果有冲突则不行，输出 NO，否则输出 YES。

可能是样例比较弱，有些情况没考虑也过了。写的丑了点，还能优化其实。

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        new Main().run();
    }
    Scanner sc = new Scanner(System.in);
    public void run(){
        int T = sc.nextInt();
        while(T --> 0){
            solve();
        }
    }

    // 有一个排行榜，长度是 n，然后现在可以接收 n 个 op，如果是 1 则需要调低这首歌的位置，如果是 0 则不变，如果是-1则需要调高这个歌的位置。
    // 如果有冲突则不行，输出 NO，否则输出 YES
    public void solve() {
        int n = sc.nextInt();

        boolean[] cantMove = new boolean[n + 1];   // 从第一名开始
        List<Integer> up = new ArrayList<>();   // 记录需要调高的位置（即op 为-1
        List<Integer> down = new ArrayList<>();  // 需要调低的,op 为 1

        for(int i = 0; i < n; i++){
            int op = sc.nextInt();
            int pos = sc.nextInt();

            if(op == 1) down.add(pos);
            else if(op == -1) up.add(pos);
            else cantMove[pos] = true;  // 表示不能动了
        }


//        System.out.println(Arrays.toString(cantMove));

        // 还有一点需要注意，如果对于同一首歌有不同的请求，那应该也要输出 NO，存在冲突了。

        // 对于需要上升的歌，需要从最高的位置（从小到大）开始判断存不存在可以调换的歌（前面有可以移动的)。如果存在则说明当前他的位置不用管，然后把那个可以被移动的歌的位置更新为不可动，防止后续判断出错
        up.sort((a, b) -> a - b);
        for(int pos : up){
            boolean flag = false;  // 标记当前数前面是否存在可移动到的位置
            for(int i = 1; i < pos; i++){
                if(!cantMove[i]){
                    // 可以被移动过来
                    cantMove[i] = true;
                    flag = true;
                    break;
                }
            }
            if(!flag) {
                System.out.println("NO");
                return;
            }
        }

//        System.out.println(up);

        // 到达这里说明上升没问题，同理如果需要下降的歌得判断后面的歌是否能被替换
        down.sort((a, b) -> b - a);

        for(int pos : down){
            boolean flag = false;

            // 注意边界，当前位置肯定能放啊，所以不能取 pos
            for(int i = n; i > pos; i--){
                if(!cantMove[i]){
                    cantMove[i] = true;
                    flag = true;
                    break;
                }
            }
            if(!flag) {
                System.out.println("NO");
                return;
            }
        }

//        System.out.println(down);

        // 左右都可以移动，不冲突
        System.out.println("YES");
    }
}