hulu笔试3.15 通过了2.8

1

// 本题为考试单行多行输入输出规范示例，无需提交，不计分。
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        int res = fun(nums);
    }

    private static int fun(int[] nums) {
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == -1) {
                continue;
            }
            int left = i * 2 - 1, right = i * 2;
            boolean l = left >= nums.length || nums[left] == -1;
            boolean r = right >= nums.length || nums[right] == -1;
            if (l && r) {
                res ++;
            }
        }
        return res;
    }

}

2

// 本题为考试单行多行输入输出规范示例，无需提交，不计分。
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        scanner.nextLine();
        char[][] matrix = new char[m][n];
        for (int i = 0; i < m; i++) {
            String str = scanner.nextLine();
            for (int j = 0; j < n; j++) {
                matrix[i][j] = str.charAt(j);
            }
        }
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        scanner.nextLine();
        char[][] image = new char[a][b];
        for (int i = 0; i < a; i++) {
            String str = scanner.nextLine();
            for (int j = 0; j < b; j++) {
                image[i][j] = str.charAt(j);
            }
        }
        int res = fun(matrix, image);
        System.out.println(res);
    }

    private static int fun(char[][] matrix, char[][] image) {
        int n = matrix.length;
        int m = matrix[0].length;
        int a = image.length;
        int b= image[0].length;
        int res = 0;
        for (int i = 0; i <= n - a; i++) {
            for (int j = 0; j <= m - b; j++) {
                if (isValid(matrix, image, i, j)) {
                    res ++;
                }
            }
        }
        return res;
    }

    private static boolean isValid(char[][] matrix, char[][] image, int i, int j) {
        int a = image.length;
        int b= image[0].length;
        for (int p = 0; p < a; p++) {
            for (int q = 0; q < b; q++) {
                if (matrix[i + p][j + q] != image[p][q]) {
                    return false;
                }
            }
        }
        return true;
    }

}

3

暴力O(N^2)只过了82%

// 本题为考试单行多行输入输出规范示例，无需提交，不计分。
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        long k = scanner.nextLong();
        long[] nums = new long[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextLong();
        }
        long res = fun1(nums, m, k);
        System.out.println(res);
    }

    private static long fun1(long[] nums, int m, long k) {
        int len = nums.length;
        long res = 0;
        for (int i = 0; i < len; i++) {
            long sum = 0;
            int negatives = 0;
            for (int j = i; j < len; j++) {
                sum += nums[j];
                // [i, j]
                if (nums[j] < 0) {
                    negatives ++;
                }
                if (negatives > m) {
                    break;
                }
                if (sum > k) {
                    continue;
                }
                res = Math.max(res, sum);
                if (res == k) {
                    return k;
                }
            }
        }
        return res;
    }
}

尝试将上面的复杂度降低为O(NlogN)，测试用例通过了，不知道是否正确。参考 https://blog.csdn.net/u010900754/article/details/60457594

// 本题为考试单行多行输入输出规范示例，无需提交，不计分。
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        long k = scanner.nextLong();
        long[] nums = new long[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextLong();
        }
        long res = fun(nums, m, k);
        System.out.println(res);
    }

    /**
     * 计算负数个数不超过m，总收益不超过k的最大子数组和
     * @param nums
     * @param m
     * @param k
     * @return
     */
    private static long fun(long[] nums, int m, long k) {
        int len = nums.length;
        // [i] [0,i-1]之间的子数组和
        long[] preSum = new long[len + 1];
        for (int i = 0; i < nums.length; i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }
        long res = 0;
        TreeMap<Long, Integer> treeMap = new TreeMap<>();
        int l = 0, r = 0;
        int negatives = 0;
        treeMap.put(0L, 0);
        while (r < len){
            // 更新r的信息
            if (nums[r] < 0) {
                negatives ++;
            }
            treeMap.put(preSum[r + 1], r);
            while (negatives > m) {
                if (nums[l] < 0) {
                    negatives --;
                }
                if (treeMap.get(nums[l]) == l) {
                    treeMap.remove(nums[l]);
                }
                l ++;
            }
            // [l, r]中负数<=m
            Map.Entry<Long, Integer> entry = treeMap.ceilingEntry(preSum[r + 1] - k);
            res = Math.max(res, preSum[r + 1] - entry.getKey());
            r ++;
        }
        return res;
    }

}

#hulu笔试##笔经##hulu#