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;
}
}