字节后端0828笔试 题目讨论

后端笔试代码讨论，出于时间关系，代码逻辑不够精简，仅供参考

第一题

思路：输入数组全为2的幂，所以将乘积最大值处理为指数和最大值，避免溢出，双指针遍历即可。
特殊用例：1 1 输出结果应该为 1 1
代码

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        for(int i=0;i<11;i++){
            map.put((int)(Math.pow(2, i)), i);
        }
        int t = scanner.nextInt();
        while(t > 0){
            int n = scanner.nextInt();
            int[] nums = new int[n];
            for (int i=0;i<n;i++){
                nums[i] = map.get(scanner.nextInt());
            }
            int max = 0;
            int resL = 0;
            int resR = 0;
            int r = 0;
            int l = 0;
            int temp = 0;
            while(r < n){
                while(r<n && nums[r] != -1){
                    temp+=nums[r];
                    r++;
                }
                if(temp > max){
                    max = temp;
                    resL = l-1;
                    resR = r;
                }
                temp = 0;
                while(r<n && nums[r] == -1){
                    r++;
                }
                l = r;
            }
            System.out.println(String.valueOf(resL) + " " + String.valueOf(resR));
            t--;
        }
    }

}

第二题

思路：拓扑排序，使用数组记录每个节点出度，使用map记录每个节点被其他节点的依赖情况

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.nextLine();
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        int[] d = new int[10];
        String str = scanner.nextLine();
        String[] strs = str.split(" ");
        int[] check = new int[strs.length];
        for(int i=0;i<strs.length;i++){
            check[i] = Integer.parseInt(strs[i]);
        }

        while(n > 1){
            str = scanner.nextLine();
            strs = str.split(" ");
            int[] nums = new int[strs.length];
            for(int i=0;i<strs.length;i++){
                nums[i] = Integer.parseInt(strs[i]);
            }
            d[nums[0]] += nums.length-1;
            for(int i=1;i<nums.length;i++){
                List<Integer> list = map.getOrDefault(nums[i], new ArrayList<Integer>());
                list.add(nums[0]);
                map.put(nums[i], list);
            }
            n--;
        }

        Deque<Integer> deque = new ArrayDeque<>();
        for(int i = 1;i<10;i++){
            if(d[i] == 0){
                deque.offerLast(i);
            }
        }

        while(!deque.isEmpty()){
            int cur = deque.pollFirst();
            List<Integer> list = map.getOrDefault(nums[i], new ArrayList<Integer>());
            for(int num : list){
                d[num]--;
                if(d[num] == 0){
                    deque.offerLast(num);
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int c : check){
            if(d[c] == 0){
                sb.append(" ");
                sb.append(1);
            }
            else {
                sb.append(" ");
                sb.append(0);
            }
        }

        String res = sb.toString().substring(1, sb.length());
        System.out.println(res);
    }
}

第三题

思路：基于前缀和与后缀和，预处理数组，设分割点下标为i，计算从0到i，与从i+1 到n的内部子数组最大值，枚举i，找出最大结果即可

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] nums = new int[n+2];
        for(int i=1;i<=n;i++){
            nums[i] = scanner.nextInt();
        }

        int[] sum = new int[n+2];

        int[] l = new int[n+2];
        for(int i=1;i<=n;i++){
            sum[i] = Math.max(sum[i-1], 0) + nums[i];
            l[i] = Math.max(l[i-1], sum[i]);
        }


        int[] r = new int[n+2];
        for(int i=n;i>=1;i--){
            sum[i] = Math.max(sum[i+1], 0) + nums[i];
            r[i] = Math.max(r[i+1], sum[i]);
        }

        // int res = l[n];
        int res = Integer.MIN_VALUE;
        for(int i=1;i<n;i++){
            res = Math.max(res, l[i] + r[i+1]);
        }
        System.out.println(res);
    }
}

第四题

思路：分别计算每个窗口的和与每个窗口内最小值，每个窗口的和—最小值，即我们要找的目标值，找出最大目标值即可，计算窗口最小值可使用单调队列。

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[] nums = new int[n];
        for(int i=0;i<n;i++){
            nums[i] = scanner.nextInt();
        }
        long[] sum = getSum(nums, n, k+1);
        int[] min = getMin(nums, n, k+1);

        long res = Long.MIN_VALUE;
        n = sum.length;

        for(int i=0;i<n;i++){
            res = Math.max(res, sum[i]-min[i]);
        }
        System.out.println(res);

    }

    public static long[] getSum(int[] nums, int n, int k){
        long[] sum = new long[n-k+1];
        long cnt = 0;
        for(int i=0;i<n;i++){
            cnt += nums[i];
            if(i >= k){
                cnt -= nums[i-k];
            }
            if(i >= k-1){
                sum[i-k+1] = cnt;
            }
        }

        return sum;

    }

    public static int[] getMin(int[] nums, int n, int k){
        int[] res = new int[n-k+1];
        Deque<Integer> deque = new ArrayDeque<>();
        for(int i=0;i<n;i++){
            while (!deque.isEmpty() && nums[deque.peekLast()] > nums[i]){
                deque.pollLast();
            }
            deque.offerLast(i);
            if(i - deque.peekFirst() + 1 > k){
                deque.pollFirst();
            }
            if(i >= k-1){
                res[i-k+1] = nums[deque.peekFirst()];
            }
        }
        return res;
    }
}