腾讯数据与算法提前批笔试题目参考代码

1 2 3 5题是100%；第4题，当时读题读的太费劲没做出来，等读明白题就要结束了

1. n个检查点通过n-1个

贪心，5种情况，应该还可以缩减没细想

1. 起始点比最小值小

2. 起始点比最大值大

3.起始点在最大值和次大值之间

4.起始点在最小值和次小值之间

5.other

后3种情况要么舍弃最小值，要么舍弃最大值。具体情况不分析了

//package Tencent0310.Test1;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        if (n == 1){
            System.out.println(0);
            return;
        }
        int start = sc.nextInt();
        int []arr = new int[n];
        for (int i = 0; i < n; i++){
            arr[i] = sc.nextInt();
        }
        Arrays.sort(arr);
        int min1 = arr[0], min2 = arr[1], max1 = arr[n-1], max2 = arr[n-2];
        if (start <= min1) System.out.println(max2 - start);
        else if(start >= max1) System.out.println(start - min2);
        else if (start > min1 && start <= min2){
            int res = Math.min(max1 - start, max2 - start + 2 * (start - min1));
            System.out.println(res);
        }
        else if (start < max1 && start >= max2){
            int res = Math.min(start - min1, start - min2 + 2 * (max1 - start));
            System.out.println(res);
        }
        else {
            int res1 = Math.min(2 * (max1-start) + start - min2, 2 * (start-min1) + max2 - start);
            int res2 = Math.min(max1-start + 2 * (start - min2), start-min1 + 2 * (max2 - start));
            System.out.println(Math.min(res1, res2));
        }
        //System.out.println(max1 + ";" + max2 + ";" + min1 + ";" + min2);
    }
}

2. 登塔

动态规划，每一步记录两个状态，一个是如果该层是爬上来的最短时间，一个是该层是跳上来的最短时间

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int []arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = sc.nextInt();
        int [][]dp = new int[n][2];
        dp[0][0] = 0; dp[0][1] = arr[0];
        if (n <= 2){
            System.out.println(0);
            return;
        }
        dp[1][0] = 0; dp[1][1] = Math.min(dp[0][0], dp[0][1]) + arr[1];
        for (int i = 2; i < n; i++){
            dp[i][0] = Math.min(dp[i-2][1], dp[i-1][1]);
            dp[i][1] = Math.min(dp[i-1][0], dp[i-1][1]) + arr[i];
        }
        System.out.println(Math.min(dp[n-1][0], dp[n-1][1]));

    }
}

3. 出队顺序

这个不贴代码了，用队列模拟就可以了，代码找不到了，简单写一下，可能与我提交的有出入，单应该这个思路

for（int i = 1; i <= n; i++)
    queue.offer(i);
while(!queue.isEmpty()){
    System.out.println(queue.poll()); //格式先不管了
    if (!queue.isEmpty())
        queue.offer(queue.poll()))
}

4. 黑白块

计算黑块有多少个
1 涂成白色黑块总数减去该区域所有黑块数
2 涂成黑色黑块总数加上该区域所有白块数
3 重合的部分所有白色变成黑色，初始状态是白色变成黑色的不用计算了（2中已经计算），需要加上的就是最初状态是黑色，在1中被涂成了白色的数量，也就是黑块总数加上重叠区域最初的黑块数目

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while(T-- > 0){
            int n = sc.nextInt(), m = sc.nextInt();
            int xa1 = sc.nextInt(), ya1 = sc.nextInt();
            int xa2 = sc.nextInt(), ya2 = sc.nextInt();
            int xb1 = sc.nextInt(), yb1 = sc.nextInt();
            int xb2 = sc.nextInt(), yb2 = sc.nextInt();
            int blackCnt = blackCount(1, 1, n, m);
            blackCnt -= blackCount(xa1, ya1, xa2, ya2);
            blackCnt += (xb2 - xb1 + 1) * (yb2 - yb1 + 1) - blackCount(xb1, yb1, xb2, yb2);
            blackCnt += overlayBlackCount(xa1, ya1, xa2, ya2, xb1, yb1, xb2, yb2);
            System.out.println((n * m - blackCnt) + " " + blackCnt);
        }
    }
    private static int overlayBlackCount(int xa1, int ya1, int xa2, int ya2,
                                         int xb1, int yb1, int xb2, int yb2){
        int x1 = Math.max(xa1, xb1);
        int y1 = Math.max(ya1, yb1);
        int x2 = Math.min(xa2, xb2);
        int y2 = Math.min(ya2, yb2);
        if (x1 <= x2 && y1 <= y2){
            return blackCount(x1, y1, x2, y2);
        }
        return 0;
    }
    private static int blackCount(int x1, int y1, int x2, int y2){
        /*
        |-------|-------|
        |   a   |   b   |
        |-------|-------|
        |   c   |   d   |
        |-------|-------|
        左上角(1, 1) 右下角坐标(x, y) 的矩形中黑块数为(x * y) / 2;
        设整个大矩形区域内有 x 个
        d = x - (a + c) - (a + b) + a;  a + c 和 a + b 和 a 都可以直接算出           */
        return ((x2 * y2) >> 1)
                - (((x1 - 1) * y2) >> 1)
                - ((x2 * (y1 - 1)) >> 1)
                + (((x1 - 1) * (y1 - 1)) >> 1);
    }
}

5. 最小差值

这个不用说了吧，就相当于对前面的数据进行二分查找

//package Tencent0310.Test5;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        TreeMap<Integer, Integer> map = new TreeMap<>();
        int n = sc.nextInt();
        //int []arr  = new int[n];
        for (int i = 1; i <=n ; i++){
            int tmp = sc.nextInt();
            //arr[i-1] = tmp;
            if (i >= 2){
                Map.Entry<Integer, Integer> e1 = map.floorEntry(tmp);
                Map.Entry<Integer, Integer> e2 = map.ceilingEntry(tmp);
                int min = Integer.MAX_VALUE, p = -1;
                if (e1 != null){
                    min = Math.abs(tmp-e1.getKey());
                    p = e1.getValue();
                }
                if (e2 != null){
                    if (Math.abs(tmp- e2.getKey()) < min){
                        min = Math.abs(tmp-e2.getKey());
                        p = e2.getValue();
                    }
                }
                System.out.println(min + " " + p);
            }

           map.put(tmp, i);
        }
    }
}

#笔试题目##提前批##腾讯#